Create Stack in C++ with Push, Pop etc

Implementing a Stack in C++: A Comprehensive Guide

Learn how to create a custom Stack data structure in C++ using a linked list, complete with essential operations like push, pop, peek, and checking for emptiness.

The Stack is a fundamental linear data structure that follows the Last-In, First-Out (LIFO) principle. Imagine a stack of plates: you can only add a new plate to the top, and you can only remove the topmost plate. This article will guide you through implementing a Stack in C++ from scratch, leveraging a linked list for dynamic memory management and efficient operations.

Understanding the Stack Data Structure

A stack supports a limited set of operations, primarily push (add an element to the top), pop (remove the top element), peek or top (view the top element without removing it), and isEmpty (check if the stack contains any elements). The LIFO nature makes stacks ideal for scenarios like function call management, expression evaluation, and undo/redo functionalities.

flowchart TD
    Start[Stack Operations]
    Start --> Push(Push Element)
    Push --> Top[Top of Stack]
    Top --> Pop(Pop Element)
    Pop --> Top
    Top --> Peek(Peek Element)
    Peek --> Top
    Top --> IsEmpty{Is Stack Empty?}
    IsEmpty -->|Yes| Empty[Stack is Empty]
    IsEmpty -->|No| NotEmpty[Stack has Elements]

Basic operations and flow of a Stack data structure.

Designing the Stack Class

We'll implement our Stack using a linked list. This approach offers flexibility as the stack can grow or shrink dynamically without a fixed size limit. Each node in our linked list will store a data element and a pointer to the next node. The top of the stack will always be represented by the head of our linked list.

template <typename T>
class Stack {
private:
    struct Node {
        T data;
        Node* next;
        Node(T val) : data(val), next(nullptr) {}
    };
    Node* topNode;

public:
    Stack() : topNode(nullptr) {}
    ~Stack(); // Destructor to free memory

    void push(T val);
    void pop();
    T peek() const;
    bool isEmpty() const;
};

The basic structure of our Stack class and its private Node structure.

Implementing Core Stack Operations

Let's dive into the implementation of each core operation. We'll focus on push, pop, peek, and isEmpty.

template <typename T>
void Stack<T>::push(T val) {
    Node* newNode = new Node(val);
    newNode->next = topNode;
    topNode = newNode;
}

template <typename T>
void Stack<T>::pop() {
    if (isEmpty()) {
        // Handle underflow, e.g., throw an exception or print an error
        throw std::out_of_range("Stack is empty, cannot pop.");
    }
    Node* temp = topNode;
    topNode = topNode->next;
    delete temp;
}

template <typename T>
T Stack<T>::peek() const {
    if (isEmpty()) {
        // Handle empty stack, e.g., throw an exception
        throw std::out_of_range("Stack is empty, no top element.");
    }
    return topNode->data;
}

template <typename T>
bool Stack<T>::isEmpty() const {
    return topNode == nullptr;
}

template <typename T>
Stack<T>::~Stack() {
    while (!isEmpty()) {
        pop();
    }
}

Implementation of push, pop, peek, isEmpty, and the destructor for memory management.

Putting It All Together: A Complete Example

Here's a complete program demonstrating how to use our custom Stack class.

#include <iostream>
#include <stdexcept> // Required for std::out_of_range

// (Include the Stack class definition from above here)

int main() {
    Stack<int> myStack;

    std::cout << "Is stack empty? " << (myStack.isEmpty() ? "Yes" : "No") << std::endl;

    myStack.push(10);
    myStack.push(20);
    myStack.push(30);

    std::cout << "Top element: " << myStack.peek() << std::endl; // Should be 30
    myStack.pop();
    std::cout << "Top element after pop: " << myStack.peek() << std::endl; // Should be 20

    myStack.push(40);
    std::cout << "Top element after push: " << myStack.peek() << std::endl; // Should be 40

    while (!myStack.isEmpty()) {
        std::cout << "Popping: " << myStack.peek() << std::endl;
        myStack.pop();
    }

    std::cout << "Is stack empty? " << (myStack.isEmpty() ? "Yes" : "No") << std::endl;

    try {
        myStack.pop(); // This will throw an exception
    } catch (const std::out_of_range& e) {
        std::cerr << "Error: " << e.what() << std::endl;
    }

    return 0;
}

A complete C++ program demonstrating the usage of the custom Stack.