Stack data structure

The stack is a fundamental data structure in computer science, commonly used for managing data in Last-In, First-Out (LIFO) order. In a stack, the last element inserted is the first one to be removed, which is analogous to a stack of plates where the last one placed on top is the first one you would pick up.

Key Characteristics of a Stack

• LIFO Principle: The last element pushed onto the stack is the first to be removed.
• Push Operation: Adds an element to the top of the stack.
• Pop Operation: Removes the element from the top of the stack.
• Peek (Top) Operation: Returns the top element without removing it.
• Empty Check: Determines if the stack is empty.

Why Use Stacks?

Stacks are used in various applications:

• Function Call Management: When functions are called, their execution contexts are stored on a stack.
• Expression Evaluation: Infix, prefix, and postfix expressions are often evaluated using stacks.
• Undo Mechanisms: They keep track of states to enable the undo operation.
• Backtracking Algorithms: Like the ones used in maze solvers and puzzle solvers.

Stack Implementation in C++

Stacks can be implemented in C++ using arrays, linked lists, or through the Standard Template Library (STL). Here’s a deeper dive into each method:

1. Array-Based Implementation

An array-based implementation uses a fixed-size array and an index that points to the top of the stack. This is straightforward but has a limitation in terms of dynamic resizing.

class Stack {
private:
    int top;
    int arr[1000]; // Array size is fixed at 1000
public:
    Stack() { top = -1; }

    void push(int x) {
        if (top >= 999) {
            std::cout << "Stack Overflow\n";
        } else {
            arr[++top] = x;
        }
    }

    void pop() {
        if (top < 0) {
            std::cout << "Stack Underflow\n";
        } else {
            top--;
        }
    }

    int peek() {
        if (top < 0) {
            std::cout << "Stack is Empty\n";
            return -1;
        } else {
            return arr[top];
        }
    }

    bool isEmpty() {
        return top < 0;
    }
};

Pros:

• Simple and fast
• Minimal overhead in terms of memory usage

Cons:

• Fixed size leads to inefficient memory use when less space is needed
• Not suitable for dynamic data size

2. Linked List-Based Implementation

Using a linked list allows the stack to grow dynamically. Each node stores an integer and a pointer to the next node.

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

class Stack {
private:
    Node* top;
public:
    Stack() { top = nullptr; }

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

    void pop() {
        if (!top) {
            std::cout << "Stack Underflow\n";
            return;
        }
        Node* temp = top;
        top = top->next;
        delete temp;
    }

    int peek() {
        if (!top) {
            std::cout << "Stack is Empty\n";
            return -1;
        }
        return top->data;
    }

    bool isEmpty() {
        return top == nullptr;
    }
};

Pros:

• Dynamic memory usage
• No need to predefine size

Cons:

• Overhead due to pointers

3. Stack Using STL

The STL provides a stack container, which internally uses either deque or vector to provide dynamic memory management and LIFO operations.

#include <iostream>
#include <stack>

int main() {
    std::stack<int> stk;

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

    std::cout << "Top element is: " << stk.top() << std::endl;

    stk.pop();
    std::cout << "Top element is: " << stk.top() << std::endl;

    if (stk.empty()) {
        std::cout << "Stack is empty\n";
    } else {
        std::cout << "Stack is not empty\n";
    }

    return 0;
}

Pros:

• Easy to use
• Automatically manages memory and size

Cons:

• Some overhead in terms of abstraction

Common Stack Operations

1. Push

Push operation adds an element to the top of the stack.

void push(int x) {
    // Implementation specific to array, linked list, or STL stack
}

2. Pop

Pop operation removes the top element from the stack.

void pop() {
    // Implementation specific to array, linked list, or STL stack
}

3. Peek

Peek operation returns the top element without removing it.

int peek() {
    // Implementation specific to array, linked list, or STL stack
}

4. IsEmpty

IsEmpty checks if the stack is empty.

bool isEmpty() {
    // Implementation specific to array, linked list, or STL stack
}