Implementation of Stack in C++ (Introduction)

A stack is a linear data structure that follows the Last In First Out (LIFO) principle. You can insert (push) and remove (pop) elements only from the top of the stack.

This implementation uses a singly linked list, where each element (node) contains two parts:

• data: The value of the stack element.
• next: A pointer to the next node in the stack.

The top of the stack is represented by the head (i.e., the first node) of the linked list.

C++ Code: Linked List-based Stack Implementation

#include<iostream>
using namespace std;

// Node structure
struct Node {
    int data;
    Node* next;
    
    Node(int value) {
        data = value;
        next = nullptr;
    }
};

// Stack class using Linked List
class Stack {
private:
    Node* top;  // Top of the stack

public:
    Stack() {
        top = nullptr;
    }

    // Push operation
    void push(int value) {
        Node* newNode = new Node(value);
        newNode->next = top;
        top = newNode;
        cout << value << " pushed to stack\n";
    }

    // Pop operation
    void pop() {
        if (isEmpty()) {
            cout << "Stack Underflow\n"; return; } Node* temp = top; top = top->next;
        cout << "Popped element: " << temp->data << endl;
        delete temp;
    }

    // Peek operation
    int peek() {
        if (isEmpty()) {
            cout << "Stack is empty\n"; return -1; } return top->data;
    }

    // Check if the stack is empty
    bool isEmpty() {
        return top == nullptr;
    }

    // Display stack elements
    void display() {
        Node* current = top;
        cout << "Stack elements: ";
        while (current != nullptr) {
            cout << current->data << " "; current = current->next;
        }
        cout << endl;
    }

    // Destructor to free memory
    ~Stack() {
        while (!isEmpty()) {
            pop();
        }
    }
};

// Driver code
int main() {
    Stack s;

    s.push(10);
    s.push(20);
    s.push(30);
    s.display();

    cout << "Top element is: " << s.peek() << endl;

    s.pop();
    s.display();

    return 0;
}

Output:

10 pushed to stack
20 pushed to stack
30 pushed to stack
Stack elements: 30 20 10 
Top element is: 30
Popped element: 30
Stack elements: 20 10

Time Complexity

• push() – O(1)
• pop() – O(1)
• peek() – O(1)
• isEmpty() – O(1)
• display() – O(n)

Space Complexity

• O(n) for storing n elements in the stack (each node holds data + pointer).

Explanation of the given Code

1. Each element in the stack is a node that stores the value (data) and a pointer to the next node. These nodes are created using the Node structure.
2. The Stack class keeps track of the top of the stack using a pointer called top. Initially, this is set to nullptr (empty stack).
3. The push() function adds a new element to the top. It creates a new node, connects it to the current top, and then updates the top pointer to this new node.
4. The pop() function removes the top element. It checks if the stack is empty. If not, it deletes the top node and moves the top pointer to the next node.
5. The peek() function shows the top value without removing it. If the stack is empty, it returns -1 and shows a message.
6. The display() function prints all elements from top to bottom by looping through the linked list. The isEmpty() function checks if the stack has any elements.