C++ Program to Implement a Stack Using Linked List

A stack is a fundamental data structure that operates on a Last In First Out (LIFO) principle. In this structure, elements are added (pushed) and removed (popped) from the top of the stack. This article explores how to implement a stack using a linked list in C++, providing multiple examples to demonstrate various operations and their outputs.

Prerequisites

Before diving into the implementation, you should have:

1. Basic understanding of C++ programming.
2. Familiarity with pointers and dynamic memory allocation.
3. Knowledge of linked lists and basic stack operations.

With these prerequisites, you will be able to grasp the concepts and code implementations discussed here.

1. Basic Stack Implementation Using Linked List

1.1 Node Structure and Stack Initialization

Let’s start by defining the structure of a node and initializing the stack.

#include <iostream>

struct Node {
    int data;
    Node* next;

    Node(int val) : data(val), next(nullptr) {}
};

class Stack {
public:
    Stack() : top(nullptr) {}

    void push(int data) {
        Node* newNode = new Node(data);
        newNode->next = top;
        top = newNode;
    }

    void pop() {
        if (top == nullptr) {
            std::cout << "Stack is empty" << std::endl;
            return;
        }
        Node* temp = top;
        top = top->next;
        delete temp;
    }

    void display() {
        if (top == nullptr) {
            std::cout << "Stack is empty" << std::endl;
            return;
        }
        Node* temp = top;
        while (temp != nullptr) {
            std::cout << temp->data << " ";
            temp = temp->next;
        }
        std::cout << std::endl;
    }

private:
    Node* top;
};

int main() {
    Stack stack;
    stack.push(10);
    stack.push(20);
    stack.push(30);
    stack.push(40);

    std::cout << "Stack: ";
    stack.display();

    return 0;
}

1.2 Output Explanation

In this example, the stack is structured as follows:

Top -> 40 -> 30 -> 20 -> 10

The output will display: Stack: 40 30 20 10

2. Advanced Stack Operations

2.1 Push and Pop Operations

Let’s demonstrate the push and pop operations with more details.

int main() {
    Stack stack;
    stack.push(10);
    stack.push(20);
    stack.push(30);
    stack.push(40);

    std::cout << "Stack after pushing 10, 20, 30, 40: ";
    stack.display();

    stack.pop();
    std::cout << "Stack after popping one element: ";
    stack.display();

    stack.pop();
    std::cout << "Stack after popping another element: ";
    stack.display();

    return 0;
}

2.2 Output Explanation

In this example, the stack undergoes the following transformations:

• After pushing 10, 20, 30, 40:Top -> 40 -> 30 -> 20 -> 10 The output will display: Stack after pushing 10, 20, 30, 40: 40 30 20 10
• After popping one element:Top -> 30 -> 20 -> 10 The output will display: Stack after popping one element: 30 20 10
• After popping another element:Top -> 20 -> 10 The output will display: Stack after popping another element: 20 10

3. Handling Edge Cases

3.1 Pop from an Empty Stack

Let’s handle the edge case where a pop operation is attempted on an empty stack.

int main() {
    Stack stack;

    stack.pop();  // Attempting to pop from an empty stack

    stack.push(10);
    stack.push(20);

    stack.pop();
    stack.pop();
    stack.pop();  // Attempting to pop from an empty stack again

    return 0;
}

3.2 Output Explanation

In this example, attempting to pop from an empty stack will produce the following output:

Stack is empty
Stack is empty

This ensures that the program handles edge cases gracefully without crashing.

Conclusion

A C++ program to implement a stack using a linked list involves defining the node structure and implementing various operations such as push, pop, and display. This article provided a detailed implementation of these operations along with multiple examples to illustrate their functionality