Stack Implementation in C++ using Linked List

In this article, we will see how to implement stack in C++ using linked list.

Stack as an Abstract data Type

Stack is an ordered data structure to store datatypes in LIFO (Last In First Out) order. That means the element which enters last are first to exit(processed). It’s like a bunch of concentric rings kept one by one over others. Of course, the last one would be picked first when we start moving them out one by one (Tower of Hanoi). Stack is a similar data type where both insertion and deletion are done on the same side, namely top. Stack only hold similar datatypes.

The insertion process is named as Push

The deletion process is named as Pop

Operations on Stack

Type_t =any datatype

Basic operations:

Push(Type_t data): It inserts data of datatype Type_t to the stack

Type_t Pop(): Removes the topmost element from stack and returns it

Other operations:

Type_t top(): Returns topmost element

bool isEmpty(): returns true if stack is empty, else returns false

bool isFull(): returns false if stack is full, else returns false

int size(): Returns size of the stack

Stack Implementation using single linked list

A linked list is itself a data structure where every element has data and a pointer(next) to point the next element.

Each node like the above is a stack element

class stackNode {
//class for stack element which is SLL
  public:
    int data; //data
    stackNode *next; //next pointer
    stackNode(int a) { //constructor
        data = a;
        next = NULL;
    }
};

Pre-requisites

1. Single Linked List class/struct
2. top pointer

Let’s check an example to understand push and pop implementation

Example:

Let the elements inserted are

1, 2, 3

So to implement a stack with linked list,

When we push an element we actually do, inserting element at the head single linked list.

When we pop an element we actually do, deleting element from the head of single linked list.

C++ implementation:

#include <bits/stdc++.h>
using namespace std;

class stackNode { 
//class for each node which is a single stack element
  public:
    int data;
    stackNode *next;
    stackNode(int a) { //constructor
        data = a;
        next = NULL;
    }
};

stackNode *top=NULL; //top of stack initialized to NULL
int size=0;// size of stack initialized to 0

void push(int x) { //push operation

    stackNode* node=(stackNode*)(malloc(sizeof(stackNode)));
    node->data=x;
    node->next=top;
    top=node;
    cout<<x<<" is pushed\n";
    size++;
}

bool isEmpty(){ //isEmpty function
  if(top==NULL && size==0)
  return true;
  else
  return false;
}

int pop() { //pop operation

    if(isEmpty()){
      cout<<"stack is empty\n";
      return INT_MIN;
    }
    else{
        size--;
        int temp=top->data;
        stackNode* tempNode=top;
        top=top->next;
        free(tempNode);
        return temp;
    }
}

int top_stack(){ //top() operation
  if(isEmpty()){
    cout<<"stack is empty\n";
    return INT_MIN;
  }
  else{
    return top->data;
  }

}

//main function
int main(){

  //menu for operations
  //press 1 for push (with data)
  //press 2 for pop()
  //press 3 for top()
  //press 4 for size()
  //press 0 to exit()

  cout<<"press 1 for push\n";
  cout<<"press 2 for pop()\n";
  cout<<"press 3 for top()\n";
  cout<<"press 4 for size()\n";
  cout<<"press 0 for exit\n";

  int choice;
  cout<<"press your choice\n";
  cin>>choice;
  while(choice){
    if(choice==1){
      int data;
      cout<<"Enter element\n";
      cin>>data;
      push(data);
    }
    else if(choice==2){
      int item=pop();
      if(item==INT_MIN){}
      else
      cout<<"Popped element: "<<item<<endl;
    }
    else if(choice==3){
      int item=top_stack();
      if(item==INT_MIN){}
      else
      cout<<"Top element: "<<item<<endl;
    }
    else if(choice==4){
      cout<<"Size is: "<<size<<endl;
    }
    else
    cout<<"Invalid number, try again!\n";
    cout<<"press your choice\n";
    cin>>choice;

  }

  cout<<"Exiting...\n";
  return 0;
}

Output:

That’s all about Stack Implementation in C++ using Linked List