Design & Implement Stack in C++ [without C++ STL]

In this article, we have explained how to implement Stack Data Structure in C++ without using C++ STL. We have implemented using both C++ Class (OOP) and C++ Struct and demonstrated implementing Stack using 1D array and Linked List internally.

Table of contents:

  1. Introduction to Stack data structure
  2. Implementation of stack using 1d-arrays (using Class)
  3. Implementation of Stack using linked list (using Struct)

Let us get started to implement Stack in C++ without using C++ STL.

Introduction to Stack data structure

The linear lists and linear arrays allows us to insert and delete elements at any place in the list – at the beginning, at the end or in the middle.

There are certain situations when we may want to restrict insertions and deletions so that they can take place only at the beginning or at the end of the list; not in the middle. One of the data structures that is useful in such situations is stack.

A stack is a linear data structure in which all the insertion and deletion operations are performed only at one end, called the top of the stack. It works on the principle of Last In First Out (LIFO). This means that the last item put on the stack is the first item that can be taken off.

There are many real-life examples of a stack. One such example is plates stacked over one another in the canteen. The plate which is at the top gets removed first, i.e. the plate which has been placed at the bottommost position remains in the stack for the longest period of time.

LIFO

The fundamental operations on stack are:

  • PUSH - To add an element to the top of the stack.
  • POP - To remove an element from the top of the stack.
  • PEEK - To see the topmost element of stack.

A stack can be implemented in the following ways:

  • Using one-dimensional arrays.
  • Using linked lists.

Note: When implemented using linked lists, the size of the stack never becomes full.

Implementation of stack using 1d-arrays (using Class)

We will implement stack with the help of following functions:

  1. Stack initialization.
  2. Push operation.
  3. Pop operation.
  4. Check for empty.
  5. Check for full.
  6. Display

The code snippet for the implementation is as follows:

We start by defining the class STACK which defines the structure of the stack data type. This includes all the related functions and data members. The data members are num which is an array to store the stack elements, and top which is used to store the position of the topmost element of the array. The functions as used have been defined and explained below.
The constructor STACK is used to initialize top to -1 to indicate that the stack is initially empty.

#include<iostream>
#define SIZE 100
using namespace std;
 
class STACK
{
    private:
        int num[SIZE];
        int top;
    public:
        STACK();
        int push(int);
        int pop();
        int isEmpty();
        int isFull();
        void displayItems();
};
STACK::STACK()
{
    top=-1;
}

The function isEmpty is used to check if the stack is empty or not, so that if the user tries to delete an element from an empty stack, he will get an error message. It checks the value of top and determines if the stack has any more elements left.

int STACK::isEmpty()
{
    if(top==-1)
        return 1;
    else
        return 0;   
}

The function isFull is used to check if the stack is full or not(by checking if location of the topmost element is the same as the size of the element), so that if the user tries to insert an element to a stack which does not have any space left, he will get an error message.

int STACK::isFull()
{
    if(top==(SIZE-1))
        return 1;
    else
        return 0;
}

The push function is used to add an element to the top of the stack. It first calls the isFull function to check if the stack has space to accomodate another element. If it receives a positive value from the isFull function, then it updates the top of the stack and adds the element to the top.

int STACK::push(int n)
{
    if(isFull())
    {
        return -9999;
    }
    ++top;
    num[top]=n;
    return n;
}

The pop function is used to delete an element to the top of the stack. It first calls the isEmpty function to check if the stack has any element in it. If it receives a positive value from the isEmpty function, then it deletes the element and decrrements the top of the stack.

int STACK::pop()
{
    int temp;
    if(isEmpty())
        return -9999;
    temp=num[top];
    --top;
    return temp;
 }

The displayItems() function prints all the elements in the stack.

void STACK::displayItems()
{
    int i; 
    cout<<"STACK is: ";
    for(i=(top); i>=0; i--)
        cout<<num[i]<<" ";
    cout<<endl;
}

The main function as it suggests is the most important part of the program that drives the stack operations. There are different choices to execute different operations such as push, pop, and dispaly, and once we provide the computer with our choice, it executes the coressponding function and gives us the output or returns a failure message if the choice is invalid or the function cannot be performed.

int main()
{
    STACK stk;
    int choice, n, temp;
     
    do
    {
        cout<<endl;
        cout<<"0 - Exit."<<endl;
        cout<<"1 - Push Item."<<endl;
        cout<<"2 - Pop Item."<<endl;
        cout<<"3 - Display Items (Print STACK)."<<endl;
         
        cout<<"Enter your choice: ";
        cin>>choice;
         
        switch(choice)
        {
            case 0: break;
             
            case 1:
                cout<<"Enter item to insert: ";
                cin>>n;
                temp=stk.push(n);
                if(temp==-9999)
                    cout<<"STACK OVERFLOW - STACK IMPLEMENTATION ERROR"<<endl;
                else
                    cout<<temp<<" inserted."<<endl;
                break;
                 
            case 2:
                temp=stk.pop();
                if(temp==-9999)
                    cout<<"STACK UNDERFLOW - STACK ADT ERROR"<<endl;
                else
                    cout<<temp<<" is removed (popped)."<<endl;
                break;
             
            case 3:
                stk.displayItems();
                break;
             
            default:
                cout<<"An Invalid choice."<<endl;
        }   
    }while(choice!=0);
 
 return 0;
}

Implementation of Stack using linked list (using Struct)

The advantage of implementation using linked lists is that there is no limit on the number of elements that can be pushed onto the stack.

We will implement stack with the help of following functions:

  1. Push operation.
  2. Pop operation.
  3. Display

The code snippet for the implementation is as follows:

We start by defining the structure Node which is used to create the linked list that is implemented as a stack. It contains the data item and a pointer variable to point to the next node.

#include <iostream>
using namespace std;
struct Node 
{ 
   int data; 
   struct Node *next; 
}; 
struct Node* top = NULL;

The push() function takes the value to be pushed into the stack as an argument. Then a new node is created and the value is inserted into the data part. This node is added to the front of the linked list and top points to it.

void push(int val) 
{
   struct Node* newnode = (struct Node*)malloc(sizeof(struct Node)); 
   newnode->data = val; 
   newnode->next = top; 
   top = newnode; 
}

The pop() function deletes the topmost value of the stack, if there is any value. If the stack is empty then underflow is printed.

void pop() 
{
   if(top==NULL)
      cout<<"Stack Underflow"<<endl;
   else 
   {
      cout<<"The popped element is "<< top->data <<endl;
      top = top->next;
   }
}

The display() function displays all the elements in the stack.

void display() 
{
   struct Node* ptr;
   if(top==NULL)
      cout<<"stack is empty";
   else 
   {   
      ptr = top; 
      cout<<"Stack elements are: ";
      while (ptr != NULL) 
      { 
         cout<< ptr->data <<" "; 
         ptr = ptr->next; 
      } 
   }
   cout<<endl;
}

The function main() gives a choice to the user if they want to push, pop or display the stack. According to the user response, the appropriate function is called using switch. If the user enters an invalid response, then that is printed.

int main() 
{
   int ch, val; 
   cout<<"1) Push in stack"<<endl;
   cout<<"2) Pop from stack"<<endl;
   cout<<"3) Display stack"<<endl;
   cout<<"4) Exit"<<endl;
   do 
   {
      cout<<"Enter choice: "<<endl;
      cin>>ch;
      switch(ch) 
      {
         case 1: 
         {   
            cout<<"Enter value to be pushed:"<<endl;
            cin>>val;
            push(val);
            break;
         }
         case 2: 
         {
            pop();
            break;
         }
         case 3: 
         {
            display();
            break;
         }
         case 4: 
         {
            cout<<"Exit"<<endl;
            break;
         }
         default: 
         {
            cout<<"Invalid Choice"<<endl;
         }
      }
   }while(ch!=4); 
      return 0;
}

Note: For all the standard stack operations (push, pop, IsEmpty, IsFull), the worst-case run-time complexity
is O(1).

Applications of Stack:

Some applications of stack are listed below:

  • Recursive function
  • Function call
  • Expression evaluation
  • Expression conversion
    -Infix to prefix
    -Infix to postfix
    -Postfix to infix
    -Prefix to infix
  • Towers of Hanoi

Stack structures are also suitable for applications where information is required to be saved and later retrieved in a reverse order for further processing.

With this article at OpenGenus, you must have a strong idea of implementing Stack Data Structure in C++ Programming Language.