Stack Data Structure in C++

 

A stack is a linear data structure that follows the Last-In-First-Out (LIFO) principle. This means that the last element added to the stack will be the first one to be removed. Stack data structures are commonly used in a variety of computer science applications such as programming languages, compilers, and operating systems. In this article, we will discuss the implementation of stack data structures in C++ and their various uses and applications.

The basic operations of a stack are push, pop, peek, and isEmpty. The push operation adds an element to the top of the stack, the pop operation removes the top element from the stack, the peek operation returns the top element without removing it, and the isEmpty operation checks if the stack is empty.

In C++, stack data structures can be implemented using arrays, linked lists, and STL (Standard Template Library). The implementation of stack data structures using arrays is the most basic and straightforward method. The array-based implementation of stack data structures in C++ is shown below:

#include <iostream> 
using namespace std;
 const int MAX = 100; 
 class Stack {
    int top;
 int arr[MAX];
 public:
 Stack() {
        top = -1;
 } 
 bool isEmpty() { 
 return top == -1;
 } 
 bool isFull() {
 return top == MAX - 1; 
 } 
 void push(int x) { 
 if (isFull()) {
 cout << "Error: Stack overflow" << endl; 
 return;
 } 
 arr[++top] = x;
 }

    int pop() 
 {
 if (isEmpty()) {
 cout << "Error: Stack underflow" << endl;
 return 0;
 } 
 return arr[top--];
 } 
 int peek() {
 if (isEmpty()) {
 cout << "Error: Stack underflow" << endl;
 return 0; 
 } 
 return arr[top];
 }
 };

In this example, the stack data structure is implemented using an array of size MAX, where MAX is a constant defined by the user. The class Stack has four member functions, isEmpty(), isFull(), push(), and pop(). The isEmpty() function returns true if the stack is empty and false otherwise. The isFull() function returns true if the stack is full and false otherwise. The push() function adds an element to the top of the stack and the pop() function removes the top element from the stack.

The implementation of stack data structures using linked lists is slightly more complex than the array-based implementation. The linked list-based implementation of stack data structures in C++ is shown below:

#include <iostream> 
 using namespace std;
 class Node {
 int data; 
 Node* next;
 public:
 Node(int x) {
 data = x;
 next = NULL;
 }

     
int getData() { 
 return data; 
} 
 Node* getNext() {
 return next;
 }
 void setNext(Node* n) {
 next = n; 
 } 
};
 class Stack { 
 Node* top; 
 public:
 Stack() {
        top = NULL;
 } 
 bool isEmpty() {
 return top == NULL