Stack implementation in C++

Last Updated : 27 May, 2024

Stack is the fundamental data structures used in the computer science to the store collections of the objects. It can operates on the Last In, First Out (LIFO) principle where the most recently added the object is the first one to be removed. It can makes the stacks highly useful in the situations where you to the reverse a series of the operations or repeatedly undo operations.

In this article, we will learn how to implement the stack data structure in C++ along with the basic stack operations.

Stack Data Structure in C++

A stack can be visualized as the vertical stack of the elements, similar to the stack of the plates. We can only add or remove the top plate. Similarly, in the stack data structures, elements can added to and removed from the top of the stack.

Stacks can be implemented using the arrays or linked lists:

Array-based implementation: It can uses the simple array to the store the elements of the stack. The pointer is used to the keep of the top of the stack.
Linked List based implementation: Each element in the stack is the node in a linked list. The top of the stack is simply the head of the linked list.

Basic Operations on Stack in C++

Following are some basic operations in the stack that make it easy to manipulate the stack data structure:

Operation	Description	Time Complexity	Space Complexity
Push	Add the element to the top of the stack.	O(1)	O(1)
Pop	Remove the element on the top of the stack.	O(1)	O(1)
Peek	Returns the element at the top of the stack without removing it.	O(1)	O(1)
IsEmpty	Checks if the stack is empty.	O(1)	O(1)

C++ Program for the Implementation of Stack

This example that implements the stack using arrays and demonstrates the basic stack operations:

C++

#include <iostream> using namespace std; // Define Stack class class Stack { private:  // Index of the top element in the stack  int top;  // Array to store stack elements, with a capacity of 100  // elements  int arr[100]; public:  // Constructor to initialize an empty stack  Stack() { top = -1; }  // Function to add an element x to the top of the stack  void push(int x)  {  // If the stack is full, print "Stack overflow" and  // return  if (top >= 99) {  cout << "Stack overflow" << endl;  return;  }  // Add element to the top of the stack and increment  // top  arr[++top] = x;  cout << "Pushed " << x << " to stack\n";  }  // Function to remove the top element from the stack  int pop()  {  // If the stack is empty, print "Stack underflow"  // and return 0  if (top < 0) {  cout << "Stack underflow" << endl;  return 0;  }  // Remove the top element from the stack and  // decrement top  return arr[top--];  }  // Function to return the top element of the stack  int peek()  {  // If the stack is empty, print "Stack is empty" and  // return 0  if (top < 0) {  cout << "Stack is empty" << endl;  return 0;  }  // Return the top element of the stack  return arr[top];  }  // Function to check if the stack is empty  bool isEmpty()  {  // Return true if the stack is empty (i.e., top is  // -1)  return (top < 0);  } }; // Main function int main() {  // Create a stack  Stack s;  // Push elements into the stack  s.push(10);  s.push(20);  s.push(30);  // Print the top element of the stack  cout << "Top element is: " << s.peek() << endl;  // Print all elements in the stack  cout << "Elements present in stack : ";  // While the stack is not empty  while (!s.isEmpty()) {  // Pop the top element from the stack and print it  cout << s.pop() << " ";  }  return 0; }

Output

Pushed 10 to stack Pushed 20 to stack Pushed 30 to stack Top element is: 30 Elements present in stack : 30 20 10

Applications of the Stack in C++

It can applies on the Expression Evaluation and it can evaluates the prefix, postfix and infix expressions.
It can applies on the Function calls and recursion.
It can applies in text editors for undo mechanisms functionalities.
It can applies on syntax parsing and syntax checking.