Stacks

Stacks in C++

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 is the first one to be removed. A stack is often likened to a stack of plates: plates are added to the top, and when you remove one, you take the top plate off first.

Stacks are widely used in various computational problems, such as expression evaluation, function call management (recursion), and undo functionality in software applications.

Basic Operations of a Stack

A stack supports a few fundamental operations:

1. Push: Adds an element to the top of the stack.
2. Pop: Removes the element from the top of the stack.
3. Peek (Top): Returns the element at the top of the stack without removing it.
4. IsEmpty: Checks whether the stack is empty.
5. Size: Returns the number of elements currently in the stack.

Implementation of Stacks in C++

In C++, stacks can be implemented using arrays, linked lists, or by using the Standard Template Library (STL) stack class. Below, we'll discuss both the manual implementation using arrays/linked lists and using the C++ STL.

1. Manual Implementation of a Stack Using Array

When implementing a stack manually, you need to manage the size of the stack and the top pointer to keep track of the topmost element.

Array-based Stack Implementation:

#include <iostream>
using namespace std;

class Stack {
private:
    int *arr;          // Array to hold stack elements
    int capacity;      // Maximum capacity of the stack
    int top;           // Top of the stack

public:
    // Constructor to initialize the stack
    Stack(int size) {
        arr = new int[size];  // Dynamically allocate memory for the stack
        capacity = size;
        top = -1;  // Indicates that the stack is empty
    }

    // Push operation
    void push(int x) {
        if (top >= capacity - 1) {
            cout << "Stack Overflow\n";
            return;
        }
        arr[++top] = x;  // Increment top and add the element
    }

    // Pop operation
    int pop() {
        if (top == -1) {
            cout << "Stack Underflow\n";
            return -1;
        }
        return arr[top--];  // Return the top element and decrement the top
    }

    // Peek operation
    int peek() {
        if (top == -1) {
            cout << "Stack is empty\n";
            return -1;
        }
        return arr[top];  // Return the top element
    }

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

    // Destructor to deallocate the memory
    ~Stack() {
        delete[] arr;
    }
};

int main() {
    Stack s(5);

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

    cout << "Top element: " << s.peek() << endl;  // Should print 30

    cout << "Popped element: " << s.pop() << endl;  // Should print 30

    cout << "Is stack empty? " << (s.isEmpty() ? "Yes" : "No") << endl;  // Should print No

    return 0;
}

2. Stack Using Linked List

Alternatively, you can implement a stack using a linked list, where each node in the list represents an element in the stack. The top of the stack will be represented by the head of the linked list.

Linked List-based Stack Implementation:

#include <iostream>
using namespace std;

// Node structure for the stack
struct Node {
    int data;
    Node* next;
};

class Stack {
private:
    Node* top;  // Points to the top of the stack

public:
    // Constructor to initialize the stack
    Stack() {
        top = nullptr;
    }

    // Push operation
    void push(int x) {
        Node* newNode = new Node();
        newNode->data = x;
        newNode->next = top;  // Link the new node to the previous top
        top = newNode;  // Move top to point to the new node
    }

    // Pop operation
    int pop() {
        if (top == nullptr) {
            cout << "Stack Underflow\n";
            return -1;
        }
        int data = top->data;
        Node* temp = top;
        top = top->next;  // Move top to the next node
        delete temp;  // Free the memory
        return data;
    }

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

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

    // Destructor to free memory
    ~Stack() {
        while (top != nullptr) {
            pop();
        }
    }
};

int main() {
    Stack s;

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

    cout << "Top element: " << s.peek() << endl;  // Should print 30

    cout << "Popped element: " << s.pop() << endl;  // Should print 30

    cout << "Is stack empty? " << (s.isEmpty() ? "Yes" : "No") << endl;  // Should print No

    return 0;
}

3. Using C++ Standard Library (STL)

C++ provides a built-in stack container in the Standard Template Library (STL), which simplifies stack operations. The stack container is an adapter that provides a restricted set of operations, making it easier to use compared to manually implementing a stack.

Using STL Stack:

#include <iostream>
#include <stack>
using namespace std;

int main() {
    stack<int> s;

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

    cout << "Top element: " << s.top() << endl;  // Should print 30

    s.pop();  // Removes 30

    cout << "Top element after pop: " << s.top() << endl;  // Should print 20

    cout << "Is stack empty? " << (s.empty() ? "Yes" : "No") << endl;  // Should print No

    return 0;
}

The STL stack provides:

• push(x): Adds element x to the stack.
• pop(): Removes the top element.
• top(): Returns the top element without removing it.
• empty(): Checks whether the stack is empty.
• size(): Returns the number of elements in the stack.

Applications of Stacks

1. Expression Evaluation: Stacks are commonly used to evaluate arithmetic expressions, especially in postfix and prefix notation.

2. Function Calls (Recursion): The function call stack keeps track of function calls and their local variables. Each function call pushes a new frame onto the stack, and when a function completes, its frame is popped.

3. Undo Operations: Many applications (e.g., text editors) use stacks to implement undo functionality. Every action (e.g., typing text) is pushed onto a stack, and when the user requests an undo, the last action is popped off and reversed.

4. Depth-First Search (DFS): In graph algorithms like DFS, stacks are used to keep track of vertices to visit.

Time Complexity of Stack Operations

For both array-based and linked list-based stacks:

• Push: O(1)
• Pop: O(1)
• Peek/Top: O(1)
• IsEmpty: O(1)
• Size: O(1) (if implemented with a counter)

Advantages and Disadvantages

• Advantages:

  • Simple to implement.
  • Fast access to the top element (constant time).
  • Suitable for problems that require LIFO behavior.

• Disadvantages:

  • Fixed size (in array implementation) — can lead to overflow if too many elements are pushed onto the stack.
  • Inefficient for accessing elements other than the top (e.g., to find an element deeper in the stack).

Conclusion

Stacks are essential in many areas of computer science and programming. Whether using manual implementations or the C++ STL, stacks provide an efficient and easy-to-understand mechanism for solving problems that require a LIFO data structure. Understanding how stacks work and their applications will help you in both theoretical concepts and practical coding challenges.