Introduction to Stacks

A stack is a linear data structure that follows the Last In, First Out (LIFO) principle. This means that the last element added to the stack will be the first one to be removed. Stacks are used in many applications, including expression evaluation, backtracking algorithms, and managing function calls in recursion.

Implementing a Stack

A stack can be implemented using an array, a linked list, or the built-in stack classes in some programming languages. Below is a simple implementation of a stack using an array in C++:

#include 
#define MAX 1000

class Stack {
    int top;

public:
    int arr[MAX]; // Maximum size of Stack

    Stack() { top = -1; }

    bool push(int x);
    int pop();
    int peek();
    bool isEmpty();
    bool isFull();
};

// Function to add an item to the stack. Increases top by 1
bool Stack::push(int x) {
    if (top >= (MAX - 1)) {
        std::cout << "Stack Overflow\n";
        return false;
    } else {
        arr[++top] = x;
        std::cout << x << " pushed into stack\n";
        return true;
    }
}

// Function to remove an item from the stack. Decreases top by 1
int Stack::pop() {
    if (top < 0) {
        std::cout << "Stack Underflow\n";
        return 0;
    } else {
        int x = arr[top--];
        return x;
    }
}

// Function to return the top element without removing it
int Stack::peek() {
    if (top < 0) {
        std::cout << "Stack is Empty\n";
        return 0;
    } else {
        int x = arr[top];
        return x;
    }
}

// Function to check if the stack is empty
bool Stack::isEmpty() {
    return (top < 0);
}

// Function to check if the stack is full
bool Stack::isFull() {
    return (top >= (MAX - 1));
}

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

    std::cout << stack.pop() << " popped from stack\n";

    return 0;
}
            

This code demonstrates how to implement a stack using an array with all basic stack operations: push, pop, peek, isEmpty, and isFull.

Stack Operations

1. Push Operation

The push operation adds an element to the top of the stack. Before adding the element, we check if the stack is full to avoid stack overflow.

// Function to add an item to the stack. Increases top by 1
bool Stack::push(int x) {
    if (top >= (MAX - 1)) {
        std::cout << "Stack Overflow\n";
        return false;
    } else {
        arr[++top] = x;
        std::cout << x << " pushed into stack\n";
        return true;
    }
}
            

2. Pop Operation

The pop operation removes the element from the top of the stack and returns it. Before removing, we check if the stack is empty to avoid stack underflow.

// Function to remove an item from the stack. Decreases top by 1
int Stack::pop() {
    if (top < 0) {
        std::cout << "Stack Underflow\n";
        return 0;
    } else {
        int x = arr[top--];
        return x;
    }
}
            

3. Peek Operation

The peek operation returns the top element of the stack without removing it. This is useful when you need to check the top element but don't want to modify the stack.

// Function to return the top element without removing it
int Stack::peek() {
    if (top < 0) {
        std::cout << "Stack is Empty\n";
        return 0;
    } else {
        int x = arr[top];
        return x;
    }
}
            

4. IsEmpty Operation

The isEmpty operation checks if the stack is empty by verifying if the top index is less than 0. This operation is useful for checking if any more elements are left to process.

// Function to check if the stack is empty
bool Stack::isEmpty() {
    return (top < 0);
}
            

5. IsFull Operation

The isFull operation checks if the stack has reached its maximum capacity by verifying if the top index is equal to or greater than the maximum allowed index.

// Function to check if the stack is full
bool Stack::isFull() {
    return (top >= (MAX - 1));
}
            

Time and Space Complexity

Stacks are very efficient in terms of time complexity for their operations:

• Push: O(1) - The push operation involves adding an element to the top of the stack, which is a constant-time operation.
• Pop: O(1) - The pop operation involves removing the top element, which is also a constant-time operation.
• Peek: O(1) - The peek operation retrieves the top element without removing it, which is done in constant time.
• IsEmpty and IsFull: O(1) - These operations involve simple comparisons and are performed in constant time.

The space complexity of a stack is O(n), where n is the number of elements stored in the stack. The space required depends on the maximum number of elements the stack can hold.

When to Use Stacks

Stacks are useful in many scenarios, particularly when you need to manage data in a LIFO manner. Here are some common use cases:

1. Function Call Management

Stacks are used to manage function calls in programming languages. When a function is called, its context (variables, return address) is pushed onto the stack. When the function returns, the context is popped off the stack.

2. Expression Evaluation

Stacks are used to evaluate expressions, particularly in parsing operations such as converting infix expressions to postfix (Reverse Polish Notation) or prefix notation, and in evaluating those expressions.

3. Undo Mechanisms

Stacks are often used to implement undo mechanisms in text editors, drawing applications, and other software. Each change is pushed onto the stack, and when the user chooses to undo, the last change is popped off the stack.

4. Backtracking Algorithms

In algorithms that require exploring all possibilities (e.g., maze solving, puzzle solving), stacks are used to keep track of the current path. If a dead end is reached, the algorithm can backtrack by popping the stack.

5. Syntax Parsing

Compilers use stacks to parse syntax in programming languages, checking for matching parentheses, braces, and other delimiters.

6. Browser History

Web browsers use stacks to keep track of the user's navigation history. Each page visited is pushed onto the stack, and the back button pops the top page off to return to the previous page.