How To Implement Stack Using Linked List With C++ Program Example

In the implementation of a stack using linked list in C++, one must understand that a stack consists of a top pointer which is called the head.

The key operations such as push() and pop() take place at the head. In the link field, the first node has a null value while the second node contains the address of the first node in its link field.

One of the main advantages of a stack using linked list over arrays is that it is feasible to make a stack grow or shrink as per the needs of the user. However, in an array, a constraint is fixed to restrict the maximum capacity to which the stack can overflow.

stack using linked list

Here is the C++ Program For Implementing Queue Using Linked List

// C++ Code For Implementing Stack Using Linked List
#include <iostream>
using namespace std;

//Defining Structure
struct Node
{
  int data;
  Node *next;
};

//Defining Class
class Stack
{
  Node *top;
  public:
    Stack();
    bool isEmpty();
    void push(int value);
    void pop();
    void ShowTop();
};

Stack::Stack()
{
  top=NULL;
}
// Defining Push Function
void Stack::push(int value)
{
  Node *ptr=new Node();
  cout<<"Enter The Value You Want To Insert In Node\n";
  cin>>value;
  ptr->data=value;
  ptr->next=top;
  top=ptr;
}

// Defining IsEmpty() Function
bool Stack::isEmpty()
{
  if(top==NULL)
  {
    return true;
  }
  else
  {
    return false;
  }
}

//Defining Pop Function
void Stack::pop()
{
  if(isEmpty())
  {
    cout<<"Stack Is Empty\n";
  }
  else
  {
    struct Node *temp=top;
    top=top->next;
    delete(temp);
  }
}

//Defining ShowTop Function
void Stack::ShowTop()
{
  if(isEmpty())
  {
    cout<<"Stack Is Empty\n";
  }
  else
  {
    cout<<top->data;
  }
}

int main()
{
  Stack obj;
  int choice;
  int value;
  do{
    cout<<"Choose The Operation You Want To perform\n";
    cout<<"\n 1:Push\n 2:Pop\n 3:Show The Top Element\n";
    cin>>choice;
    switch(choice)
    {
      case 1:
        obj.push(value);
        cout<<"Element Pushed Into The Stack\n";
        break;
      case 2:
          obj.pop();
          cout<<"Element Popped Out Of The Stack\n";
        break;
      case 3:
        cout<<"Element At The Top Of The Stack Is: ";
          obj.ShowTop();
          cout<<"\n";
        break;
      default:
          cout<<"Choose Corrent Option\n";            
    }
  }while(choice!=4);
}

Let’s Quickly Understand The Stack Data Structure

A stack is an abstract data type or data structure that can be represented by physically represented by a real-life object such as “A stack of plates/books in a cupboard” where the insertion and removal of items take place only at one end i.e “Top”.
Stacks work on the principle of Last In First Out (LIFO), wherein new elements are added to the stack at one end only. In this case, only the top end. You might wonder why not the bottom end. Here’s the explanation.
Picturise stack like a deck of cards. You can either add a card or remove one, only at one end. While adding or removing a card at the top end is easy, doing so at the bottom end requires you to traverse through the entire deck of cards until you reach the bottom-most card.
Consider the timing involved in this process. Removing or adding a card at the top end will be done fast, whereas doing so at the bottom end would extend the timeline in concordance with the total number of cards available in the deck.
Similarly, in a stack, all data operations are performed only at one end. If we access the data elements at the top end, then it would take constant time or 0(1) to execute the action. But accessing data at the bottom end would take 0(n) time which is not feasible. This is why all operations are performed only at the top end of the stack in the linked list.

Key Operations of Stack Data Structure

Generally, there are two important functions as far as stacks are concerned: push and pull. These two operations govern the LIFO principle. Further, to use stacks efficiently, we also have operations such as peek, display, isFull, and isEmpty. These operations are used to check out the status of the stack.

1. push()

Used to add a new element to the top end of the stack. This newly added element becomes the top node of the linked list.

void Stack::push(int value)
{
Node *ptr=new Node();
cout<<"Enter The Value You Want To Insert In Node\n"; cin>>value;
ptr->data=value;
ptr->next=top;
top=ptr;
}

2. pop()

Used to remove the top node from the linked list.

//Defining Pop Function
void Stack::pop()
{
  if(isEmpty())
  {
    cout<<"Stack Is Empty\n";
  }
  else
  {
    struct Node *temp=top;
    top=top->next;
    delete(temp);
  }
}

3. peek()

Used to access the top node of the stack without deleting it.

//Defining ShowTop Function
void Stack::ShowTop()
{
  if(isEmpty())
  {
    cout<<"Stack Is Empty\n";
  }
  else
  {
    cout<<top->data;
  }
}

4. isFull()

Used to check if the stack is full.

bool Stack::isFull()
{
  if(top!=NULL)
  {
    return true;
  }
  else
  {
    return false;
  }
}

5. isEmpty()

Used to check if the stack is empty

bool Stack::isEmpty()
{
  if(top==NULL)
  {
    return true;
  }
  else
  {
    return false;
  }
}

Understanding Push() And Pop() Operations With Examples

Steps In Push() Operation in Stack Using Linked List

  • Create a new node and allocate it a memory
  • In case the list is empty, the item that is to be pushed would become the head node of the stack
  • To the newly created node, assign the item value to the data field, and assign null to the next field which has the address
  • In case the list already has some nodes, we would still have to add the newly created node to the top end of the stack so as to maintain the LIFO working procedure of stacks
  • So here, we would assign the address of the first element in the existing list to the new node’s address field and assign the item value to the new node’s data field
  • Thus, this newly created node would become the head node of the linked list

Steps In Pop() Operation in Stack Using Linked List

  • Check if the list is empty first
  • This process is called checking for underflow conditions.
  • As you check, when the head node points to null in the linked list, you can derive that the list is empty and that no element can be popped from the stack
  • If the list has some existing values, then you can pop out the topmost element.
  • So, here you delete the head node and free it.
  • Then the second node now becomes the head node.

Examples Of Push() And Pop() In Stack Using Linked List

Here are the examples of Push() and Pop() operation, We have shown each step of pushing an element into the stack and then removing it.

Inserting An Element In Stack

For a real-world use case, let us now consider an example.

stack using singly linked list

In the above linked list, the stack consists of three elements: 10, 20, 30, whose addresses are 100, 200, and 300 respectively.

Note that in the above image, the second node’s address is assigned in the first node’s address field. Similarly, the tail node’s (Last Node) address is assigned to the address field of the second node, and therefore the address field of the tail node is null.

Let us now assume that we are going to push a new node whose value is 40 and the address is 400 to the existing linked list.

inserting an element in stack using linked list

In order to now insert the new node to the linked list, we need to build two links. First, a new link must be built between the new node and the head node as shown below.

inserting an element in stack using linked list

To the new node, we assign the address of the head node to the address field of the new node. Then we break the link between the head and the current head node as depicted below.

inserting an element in stack using linked list

After this, we link the head to the new node and assign the address of the new node to the head.

inserting an element in stack using linked list

This is how we perform push() in a linked list.

Deleting An Element From Stack

Here, we need to first delete the link between the head and the new node.

deletion operation in stack using linked list

Then we build the link between the head and the second node and assign the second node’s address to the head.

deletion operation in stack using linked list

Now the memory allocated to the new node can be deleted. And with the established link, the second node now becomes the head node.

deletion operation in stack using linked list

Explanation Of Queue Using Linked List C++ Program

In a nutshell, the program defines the necessary structure, class, and functions so as to perform the three important implementations we’ve learned in this article:

  •  push()
  •  pop()
  • ShowTop()

So, we start by defining a structure called Node. This is where we initialize the integer datatype data and the node datatype *next. They would act as the containers that hold the value you push and its corresponding address respectively.

Next, we define a class called Stack, wherein under private access we are declaring a node datatype called *Top, which as a global variable has been initialized as NULL. Then in public access we declare the functions such as isEmpty(), push(), pop(), and ShowTop().

Then we define each of the functions.

In the push function, whatever element you enter would be stored in the top node. Following this, we define the isEmpty function. The role of this function is to let you know that the stack is empty once you’ve popped all nodes or are inserting the head node.

With the pop function, you would be able to pop the top-most node. Then finally, with the ShowTop function, you can see which value exists at the topmost node or the head node.

In order to access all these functions under one hub, we then define a switch statement. Choice 1 let you push an element, choice 2 let you pop an element, and choice 3 lets you view the topmost element of the linked list.

I hope this explains the code well. In case you have any doubts, feel free to drop them in the comments. Until then, keep geeking!

See More:

Leave a Comment