Stack Implementation using Linked List | C++ Code

You can implement the Stack data structure using a singly Linked List but you have to keep in mind that you have to perform all the Stack operations by following the LIFO (Last In First Out) principle. You also have to remember that all the Stack operations like push(), pop(), pee(), and isempty() must be performed under the constant time complexity of O(1).  

Stack operations using Linked List:

To implement a stack using a linked list, you have to create one top pointer that will always point to the head of the linked list or you can say the topmost node of the stack. Because here, in this case, you are not just going to store the variable inside the stack instead you are going to store the node of the list. All your important operations like push and pop are going to perform from the beginning of the list or you can say at the head (top) of the list. 

Push Operation into Stack

push(): To perform the insert operation into the stack, you have to insert an element at the beginning of the list. When your head (top) is pointing to NULL it means your stack is empty so to insert an element into the stack you have to create one new node with that element and assign the address of this node to the head (top). And whenever you want to add one new element, you can perform insert at the beginning operation on the list. 

Pop operation on Stack.

pop(): To remove the top element of the stack, you can simply delete the first node of the list because it is the topmost element present in the stack and as you know that the head (top) always points to the beginning of the list. After deleting the first node, the head (top) will start pointing to the second node which is now the top element of the stack.

peek(): To get the information about the top element of the stack, you can simply return what value is present in the first node of the list which is pointed by the head (top) pointer. If the head (top) is pointing to NULL it means no element is present in the stack.

isempty(): It is very simple to know if the stack is empty or not, if your head contains a NULL value it means your stack is empty.

There is no condition when the stack gets full when you are implementing Stack using Linked List because the size of the Linked List can increase or decrease at runtime.

Example: C++ code for the Implementation of Stack using Singly Linked List.

#include <bits/stdc++.h>
using namespace std;
class ListNode
{
public:
    int data;
    ListNode *next;
    // constructor
    ListNode(int data)
    {
        this->data = data;
        this->next = NULL;
    }
    // destructor
    ~ListNode()
    {
        int value = this->data;
        if (this->next != NULL)
        {
            delete next;
            this->next = NULL;
        }
        cout << "Pop a Node with value " << value << endl;
    }
};
// function to push element into stack
void push(ListNode *&top, int num)
{
    ListNode *temp = new ListNode(num);
    temp->next = top;
    top = temp;
}
// function to pop element from the stack
void pop(ListNode *&top)
{
    if (top == NULL)
    {
        cout << "Stack is Empty" << endl;
    }
    else
    {
        ListNode *temp = top;
        top = top->next;
        temp->next = NULL;
        delete temp;
    }
}
// function to check topmost element of stack
int peek(ListNode *&top)
{
    if (top == NULL)
    {
        cout << "Stack is Empty" << endl;
        return -1;
    }
    else
    {
        return top->data;
    }
}
// function to print all the element of stack
void printStack(ListNode *&top)
{
    ListNode *temp = top;
    while (temp != NULL)
    {
        cout << temp->data << endl;
        temp = temp->next;
    }
}
// function to check stack is empty or not
bool isEmpty(ListNode *&top)
{
    if (top == NULL)
    {
        return true;
    }
    return false;
}
int main()
{
    ListNode *top = NULL;
    // push elements into stack
    push(top, 20);
    push(top, 30);
    push(top, 40);
    push(top, 50);
    cout << "Element present at the top of stack :";
    cout << peek(top) << endl;
    pop(top);
    cout << "New top after deleting topmost element :";
    cout << peek(top) << endl;
    cout << "Elements present in the stack :" << endl;
    printStack(top);
    if (isEmpty(top))
    {
        cout << "Stack is Empty" << endl;
    }
    else
    {
        cout << "Stack is not Empty" << endl;
    }
}

Element present at the top of stack :50   
Pop a Node with value 50
New top after deleting topmost element :40
Elements present in the stack :
40
30
20
Stack is not Empty