Stack Using Linked List

Let us see in the below program how stack can be implemented using Linked List.

#include <iostream>
using namespace std;

typedef struct node
{
     int data;
     struct node* next;
 }Node;

class stack
{
private:
    Node* head;
public:
    stack()
    {
        head = NULL;
    }
    ~stack()
    {
        while (NULL != head)
        {
            Node* temp = head;
            head = head ->next;
            delete temp;
         }
    }

    void  push(int data)
    {
        Node* temp = new Node;
        temp->data = data;
        if (NULL == head)
       {
            head = temp;
            head->next = NULL;
            return;
        }
        temp->next = head;
        head = temp;
    }

    int pop()
    {
        if (NULL == head)
        {
            return -1;
        }
        Node* temp = head;
        head = head->next;
        int data = temp->data;
        delete temp;
        return data;
    }
    
    bool isEmpty()
    { 
        return (NULL == head);
    }
    void display()
    {
        if (NULL == head)
        {
            cout <<"Stack is empty" << endl;
            return;
        }
        Node* temp = head;
        while (NULL != temp)
        {
            cout << "Element: " << temp->data << endl;
            temp = temp->next;
        }
    }
};

int main()
{
    stack s1;
    s1.push(2);
    s1.push(4);
    s1.push(6);
    s1.push(8);
    cout << "Element: "<< s1.pop() << endl;
    cout << "Element: "<< s1.pop() << endl;
    s1.display();
    cout << "Element: "<< s1.pop() << endl;
    cout << "Element: "<< s1.pop() << endl;
    s1.display();
    return 0;
 }

Output:
Element: 8
Element: 6
Element: 4
Element: 2
Element: 4
Element: 2
Stack is empty

Linked List Node is defined using struct. It has two members:
1) integer data to store the data
2) Node pointer to store address of next Node

stack class is created with Node pointer as its data member which will hold the address of first Node of Linked List.

In the constructor, head is initialized to NULL to indicate that stack is empty

In the destructor, memory is freed by deleting the Nodes if any.

In the push function, Node is created using new and data is assigned to the node. Then, head is checked against NULL in order to check whether any element is present or not. if not, node is assigned to head otherwise, next pointer of new node is assigned with head and make this new node as head. In other words, every time element is pushed, it becomes the head Node.

In the pop function, first head is checked against NULL . if NULL that mean stack is empty and return. Otherwise, read the head Node data and move the head to next Node and delete the node to avoid memory leak.

display function is used to show the elements present in the stack.

Advantages Over Fixed Size Array Implementation.

There is no upper limit using linked list unlike the case of Stack with Fixed Array

Once the element is pop, memory is freed. So this way, no extra memory is retained.

As and when required, memory is allocated for each element unlike fixed array size where memory is allocated for the all the elements before pushing any element.

No contiguous memory is needed as memory is allocated when push is called.