Stack Using Linked List in C++

Introduction

A Stack is a linear data structure that follows the LIFO (Last In First Out) principle. The last element inserted into the stack is the first one to be removed. Unlike an array-based stack, a Linked List Stack can grow and shrink dynamically during program execution because memory is allocated as needed.

In this tutorial, we will learn how to implement a Stack using a Linked List in C++. The program performs the basic stack operations including Push, Pop, Peek, and Display using dynamically allocated nodes. This approach eliminates the fixed-size limitation of arrays and is widely used in Data Structures and Algorithms (DSA).

---

Table of Contents

• Algorithm
• C++ Program
• Input
• Sample Output
• Output
• Explanation
• Dry Run
• Flow of Execution
• Time Complexity
• Space Complexity
• Applications
• Key Points
• Interview Questions
• Frequently Asked Questions
• Keywords
• Conclusion

---

Algorithm

1. Start the program.
2. Create a structure Node containing data and next pointer.
3. Initialize the top pointer as NULL.
4. Display the menu to the user.
5. Read the user's choice.
6. If the choice is Push, create a new node, store the value, link it with the current top, and update the top pointer.
7. If the choice is Pop, check whether the stack is empty. If not, remove the top node and update the top pointer.
8. If the choice is Peek, display the value stored in the top node.
9. If the choice is Display, traverse the linked list from top to bottom and print every element.
10. If the choice is Exit, terminate the program.
11. Otherwise, display an invalid choice message.
12. Repeat the menu until the user selects Exit.
13. Stop the program.

---

C++ Program

#include <iostream>
using namespace std;

// Node structure
struct Node
{
    int data;
    Node *next;
};

// Top pointer
Node *top = NULL;

// Push operation
void push(int value)
{
    Node *newNode = new Node;

    newNode->data = value;
    newNode->next = top;
    top = newNode;

    cout << value << " pushed into stack.\n";
}

// Pop operation
void pop()
{
    if (top == NULL)
    {
        cout << "Stack Underflow! Stack is empty.\n";
        return;
    }

    Node *temp = top;
    cout << "Popped element: " << temp->data << endl;

    top = top->next;
    delete temp;
}

// Peek operation
void peek()
{
    if (top == NULL)
    {
        cout << "Stack is empty.\n";
    }
    else
    {
        cout << "Top element: " << top->data << endl;
    }
}

// Display operation
void display()
{
    if (top == NULL)
    {
        cout << "Stack is empty.\n";
        return;
    }

    cout << "Stack elements are:\n";

    Node *temp = top;

    while (temp != NULL)
    {
        cout << temp->data << " ";
        temp = temp->next;
    }

    cout << endl;
}

int main()
{
    int choice, value;

    do
    {
        cout << "\n===== STACK USING LINKED LIST =====\n";
        cout << "1. Push\n";
        cout << "2. Pop\n";
        cout << "3. Peek\n";
        cout << "4. Display\n";
        cout << "5. Exit\n";
        cout << "Enter your choice: ";
        cin >> choice;

        switch (choice)
        {
            case 1:
                cout << "Enter value to push: ";
                cin >> value;
                push(value);
                break;

            case 2:
                pop();
                break;

            case 3:
                peek();
                break;

            case 4:
                display();
                break;

            case 5:
                cout << "Exiting program...\n";
                break;

            default:
                cout << "Invalid choice!\n";
        }

    } while (choice != 5);

    return 0;
}

---

Input

The program accepts the user's choice from the menu. Depending on the selected option, the user may enter an integer value to push into the stack.

1
10
1
20
1
30
4
3
2
4
5

---

Sample Output

===== STACK USING LINKED LIST =====
1. Push
2. Pop
3. Peek
4. Display
5. Exit
Enter your choice: 1

Enter value to push: 10
10 pushed into stack.

===== STACK USING LINKED LIST =====
1. Push
2. Pop
3. Peek
4. Display
5. Exit
Enter your choice: 1

Enter value to push: 20
20 pushed into stack.

===== STACK USING LINKED LIST =====
1. Push
2. Pop
3. Peek
4. Display
5. Exit
Enter your choice: 1

Enter value to push: 30
30 pushed into stack.

===== STACK USING LINKED LIST =====
1. Push
2. Pop
3. Peek
4. Display
5. Exit
Enter your choice: 4

Stack elements are:
30 20 10

===== STACK USING LINKED LIST =====
1. Push
2. Pop
3. Peek
4. Display
5. Exit
Enter your choice: 3

Top element: 30

===== STACK USING LINKED LIST =====
1. Push
2. Pop
3. Peek
4. Display
5. Exit
Enter your choice: 2

Popped element: 30

===== STACK USING LINKED LIST =====
1. Push
2. Pop
3. Peek
4. Display
5. Exit
Enter your choice: 4

Stack elements are:
20 10

===== STACK USING LINKED LIST =====
1. Push
2. Pop
3. Peek
4. Display
5. Exit
Enter your choice: 5

Exiting program...

---

---

Output

The program allows the user to perform various stack operations through a menu-driven interface. Depending on the selected option, it can insert a new element into the stack, remove the top element, display the top element, or print all stack elements from top to bottom. If the user attempts to remove or view an element from an empty stack, the program displays an appropriate error message.

---

Explanation

Step 1

Include the required header file and use the standard namespace.

#include <iostream>
using namespace std;

• #include <iostream> provides input and output functions.
• using namespace std; allows us to use cout and cin without writing std::.

---

Step 2

Create a node structure for the linked list.

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

• data stores the stack element.
• next stores the address of the next node.
• Each node represents one element in the stack.

---

Step 3

Declare the top pointer.

Node *top = NULL;

• The top pointer always points to the topmost element of the stack.
• Initially, the stack is empty, so top is initialized to NULL.

---

Step 4

Implement the Push operation.

void push(int value)
{
    Node *newNode = new Node;

    newNode->data = value;
    newNode->next = top;
    top = newNode;

    cout << value << " pushed into stack.\n";
}

• Create a new node dynamically.
• Store the given value in the node.
• Link the new node with the current top node.
• Update the top pointer to the newly created node.
• The new node becomes the top element of the stack.

---

Step 5

Implement the Pop operation.

void pop()
{
    if (top == NULL)
    {
        cout << "Stack Underflow! Stack is empty.\n";
        return;
    }

    Node *temp = top;
    cout << "Popped element: " << temp->data << endl;

    top = top->next;
    delete temp;
}

• Check whether the stack is empty.
• If empty, display Stack Underflow.
• Otherwise, store the current top node in a temporary pointer.
• Display the top element.
• Move the top pointer to the next node.
• Delete the removed node to free memory.

---

Step 6

Implement the Peek operation.

void peek()
{
    if (top == NULL)
    {
        cout << "Stack is empty.\n";
    }
    else
    {
        cout << "Top element: " << top->data << endl;
    }
}

• Check whether the stack is empty.
• If the stack is empty, display an appropriate message.
• Otherwise, display the value stored in the top node.
• The Peek operation does not remove any element.

---

Step 7

Implement the Display operation.

void display()
{
    if (top == NULL)
    {
        cout << "Stack is empty.\n";
        return;
    }

    Node *temp = top;

    while(temp != NULL)
    {
        cout << temp->data << " ";
        temp = temp->next;
    }
}

• Check whether the stack is empty.
• Create a temporary pointer pointing to the top node.
• Traverse the linked list until NULL is reached.
• Print every node during traversal.
• The elements are displayed from top to bottom.

---

Step 8

Implement the main function.

int main()
{
    int choice, value;

    do
    {
        ...
    }
    while(choice != 5);

    return 0;
}

• The program repeatedly displays the menu.
• The user enters a choice.
• A switch statement performs the selected stack operation.
• The loop continues until the user selects Exit.

---

Dry Run

Input

Push 10
Push 20
Push 30
Display
Peek
Pop
Display

Processing

Operation	Stack (Top → Bottom)	Explanation
Initially	Empty	Stack contains no elements.
Push(10)	10	10 becomes the top node.
Push(20)	20 → 10	20 is inserted at the top.
Push(30)	30 → 20 → 10	30 becomes the new top node.
Display	30 20 10	Elements are printed from top to bottom.
Peek	30	Top element is displayed without removing it.
Pop	20 → 10	30 is removed from the stack.
Display	20 10	Remaining elements are displayed.

Output

30 20 10

Top element: 30

Popped element: 30

20 10

---

Flow of Execution

                    Start
                      │
                      ▼
            Initialize Top = NULL
                      │
                      ▼
               Display Menu
                      │
                      ▼
             Read User Choice
                      │
      ┌───────────────┼────────────────┐
      ▼               ▼                ▼
    Push            Pop             Peek
      │               │                │
      └───────────────┼────────────────┘
                      ▼
                  Display
                      │
                      ▼
             Exit Selected?
              │            │
             No            Yes
              │             │
              └──────► Stop

---

Time Complexity

Operation	Complexity
Push	O(1)
Pop	O(1)
Peek	O(1)
Display	O(n)

Best Case: O(1)

Average Case: O(n)

Worst Case: O(n)

Overall Time Complexity:

• Push: O(1)
• Pop: O(1)
• Peek: O(1)
• Display: O(n)

Push, Pop, and Peek operations access only the top node, so they execute in constant time. The Display operation traverses every node in the linked list, resulting in linear time complexity.

---

Space Complexity

• Each inserted element requires one dynamically allocated node.
• Each node stores one integer and one pointer.
• No extra data structure is used except a temporary pointer during traversal.

Auxiliary Space Complexity: O(1)

Total Space Complexity: O(n)

The stack grows dynamically based on the number of elements inserted. Therefore, the total memory required is proportional to the number of nodes stored in the linked list.

---

---

Applications

• Implementing dynamic stack data structures without fixed size limitations.
• Function call management and recursion handling.
• Expression evaluation such as postfix and prefix expressions.
• Parentheses balancing in compilers and syntax checking.
• Undo and Redo operations in text editors.
• Backtracking algorithms such as maze solving and depth-first search (DFS).
• Browser history navigation.
• Memory-efficient stack implementation where the maximum size is unknown.
• Compiler design and parsing algorithms.
• Data Structures and Algorithms (DSA) interview preparation.

---

Key Points

• A Stack follows the LIFO (Last In First Out) principle.
• A Linked List implementation allows the stack to grow dynamically.
• The top pointer always points to the topmost node.
• Push() inserts a new node at the beginning of the linked list.
• Pop() removes the top node and updates the top pointer.
• Peek() displays the top element without removing it.
• Display() traverses the linked list from top to bottom.
• No predefined stack size is required.
• Memory is allocated dynamically using the new operator.
• Removed nodes are released using the delete operator.
• Push, Pop, and Peek operations execute in constant time O(1).
• Display operation requires traversal, resulting in O(n) time complexity.
• The implementation efficiently avoids stack overflow caused by fixed-size arrays, provided sufficient heap memory is available.

---

Interview Questions

1. What is a Stack in Data Structures?
2. What does LIFO stand for?
3. Why is a Linked List preferred over an array for implementing a dynamic stack?
4. What is the purpose of the top pointer?
5. What happens during the Push operation?
6. What is Stack Underflow?
7. How does the Pop operation work?
8. Does the Peek operation remove an element from the stack?
9. What is the time complexity of Push, Pop, Peek, and Display operations?
10. What is the space complexity of a stack implemented using a linked list?
11. Why do we use dynamic memory allocation in this program?
12. What happens if memory allocation fails while performing Push?
13. Can multiple top pointers exist for a single stack?
14. How does a linked list stack differ from an array stack?
15. Where are Linked List Stacks commonly used in real-world applications?

---

Frequently Asked Questions (FAQs)

1. What is a Stack?

A Stack is a linear data structure that follows the Last In First Out (LIFO) principle, where the last inserted element is the first one to be removed.

2. Why implement a Stack using a Linked List?

A Linked List allows the stack to grow and shrink dynamically without requiring a fixed-size array, making memory usage more flexible.

3. What is the purpose of the top pointer?

The top pointer always points to the topmost node of the stack and is used to perform Push, Pop, and Peek operations efficiently.

4. What is Stack Overflow?

Stack Overflow occurs when attempting to insert an element into a full stack. In a linked list implementation, this situation generally occurs only if the system runs out of heap memory.

5. What is Stack Underflow?

Stack Underflow occurs when the user tries to remove or access an element from an empty stack.

6. What is the time complexity of the Push operation?

The Push operation has a time complexity of O(1) because insertion always occurs at the beginning of the linked list.

7. What is the time complexity of the Pop operation?

The Pop operation also takes O(1) time since only the top node is removed.

8. What is the time complexity of the Display operation?

Display requires traversing every node in the linked list, resulting in a time complexity of O(n).

9. Why do we use the new operator?

The new operator dynamically allocates memory for a new node during the Push operation.

10. Why is the delete operator used?

The delete operator releases the memory occupied by the removed node, preventing memory leaks.

---

Keywords

Stack Using Linked List in C++, Stack Implementation Using Linked List, Dynamic Stack in C++, Push Operation in Stack, Pop Operation in Stack, Peek Operation in Stack, Display Stack Elements, Linked List Stack Program, Stack Using Dynamic Memory Allocation, Data Structures in C++, Stack Interview Programs, C++ DSA Programs, Linked List Data Structure, Stack Operations in C++, LIFO Data Structure.

---

Conclusion

In this tutorial, we learned how to implement a Stack using a Linked List in C++. The program demonstrates all fundamental stack operations, including Push, Pop, Peek, and Display. Since memory is allocated dynamically, the stack can expand as needed without the size limitations of an array-based implementation. Push, Pop, and Peek operations execute in constant time, making the linked list implementation highly efficient for dynamic applications. Understanding this implementation provides a strong foundation for learning advanced data structures and solving interview problems involving stacks.

---