Stacks

A stack is a linear data structure that follows the Last In, First Out (LIFO) principle. Elements are added and removed from the same end, called the top of the stack. Think of it like a stack of plates - you can only add or remove plates from the top.

Stacks are fundamental in computer science and are used in function calls, expression evaluation, undo operations, and many algorithms.

Stack Operations

The main operations on a stack are:

push(): Add an element to the top
pop(): Remove the top element
top()/peek(): View the top element without removing it
empty(): Check if the stack is empty
size(): Get the number of elements

Stack Implementation using Array

#include <iostream>
using namespace std;

class Stack {
private:
    int* arr;
    int capacity;
    int topIndex;

public:
    Stack(int size) {
        arr = new int[size];
        capacity = size;
        topIndex = -1;
    }
    
    ~Stack() {
        delete[] arr;
    }
    
    // Push element to top
    void push(int value) {
        if (topIndex >= capacity - 1) {
            cout << "Stack Overflow! Cannot push " << value << endl;
            return;
        }
        arr[++topIndex] = value;
        cout << "Pushed: " << value << endl;
    }
    
    // Pop element from top
    int pop() {
        if (topIndex < 0) {
            cout << "Stack Underflow! Cannot pop from empty stack" << endl;
            return -1;
        }
        return arr[topIndex--];
    }
    
    // Peek at top element
    int top() {
        if (topIndex < 0) {
            cout << "Stack is empty" << endl;
            return -1;
        }
        return arr[topIndex];
    }
    
    // Check if stack is empty
    bool empty() {
        return topIndex < 0;
    }
    
    // Get size of stack
    int size() {
        return topIndex + 1;
    }
    
    // Display stack contents
    void display() {
        if (empty()) {
            cout << "Stack is empty" << endl;
            return;
        }
        
        cout << "Stack contents (top to bottom): ";
        for (int i = topIndex; i >= 0; i--) {
            cout << arr[i] << " ";
        }
        cout << endl;
    }
};

int main() {
    Stack stack(5);
    
    // Push elements
    stack.push(10);
    stack.push(20);
    stack.push(30);
    
    stack.display();
    cout << "Top element: " << stack.top() << endl;
    cout << "Stack size: " << stack.size() << endl;
    
    // Pop elements
    cout << "Popped: " << stack.pop() << endl;
    cout << "Popped: " << stack.pop() << endl;
    
    stack.display();
    
    // Try to pop from empty stack
    stack.pop();
    stack.pop(); // This will cause underflow
    
    return 0;
}

STL Stack

C++ Standard Template Library provides a stack container adapter that can be used with different underlying containers:

Using STL Stack

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

int main() {
    // Default stack (uses deque as underlying container)
    stack<int> st;
    
    // Push elements
    st.push(10);
    st.push(20);
    st.push(30);
    st.push(40);
    
    cout << "Stack size: " << st.size() << endl;
    cout << "Top element: " << st.top() << endl;
    
    // Display and pop all elements
    cout << "Stack contents: ";
    while (!st.empty()) {
        cout << st.top() << " ";
        st.pop();
    }
    cout << endl;
    
    // Stack with vector as underlying container
    stack<int, vector<int>> stackWithVector;
    stackWithVector.push(1);
    stackWithVector.push(2);
    stackWithVector.push(3);
    
    cout << "Vector-based stack: ";
    while (!stackWithVector.empty()) {
        cout << stackWithVector.top() << " ";
        stackWithVector.pop();
    }
    cout << endl;
    
    // Stack of strings
    stack<string> stringStack;
    stringStack.push("First");
    stringStack.push("Second");
    stringStack.push("Third");
    
    cout << "String stack: ";
    while (!stringStack.empty()) {
        cout << stringStack.top() << " ";
        stringStack.pop();
    }
    cout << endl;
    
    return 0;
}

Stack Applications

Balanced Parentheses Check

One of the most common applications of stacks is checking if parentheses are balanced in an expression:

Balanced Parentheses Checker

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

bool isBalanced(string expression) {
    stack<char> s;
    
    for (char ch : expression) {
        // Push opening brackets
        if (ch == '(' || ch == '[' || ch == '{') {
            s.push(ch);
        }
        // Check closing brackets
        else if (ch == ')' || ch == ']' || ch == '}') {
            if (s.empty()) {
                return false; // No matching opening bracket
            }
            
            char top = s.top();
            s.pop();
            
            // Check if brackets match
            if ((ch == ')' && top != '(') ||
                (ch == ']' && top != '[') ||
                (ch == '}' && top != '{')) {
                return false;
            }
        }
    }
    
    // Stack should be empty for balanced expression
    return s.empty();
}

int main() {
    vector<string> expressions = {
        "()",
        "()[]{}", 
        "([{}])",
        "(((",
        "())",
        "([)]",
        "{[()()]}"
    };
    
    cout << "Checking balanced parentheses:" << endl;
    for (const string& expr : expressions) {
        cout << expr << " -> " 
             << (isBalanced(expr) ? "Balanced" : "Not Balanced") 
             << endl;
    }
    
    return 0;
}

Expression Evaluation

Stacks can be used to evaluate postfix expressions (Reverse Polish Notation):

Postfix Expression Evaluation

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

int evaluatePostfix(string expression) {
    stack<int> s;
    istringstream iss(expression);
    string token;
    
    while (iss >> token) {
        if (token == "+" || token == "-" || token == "*" || token == "/") {
            // Pop two operands
            int operand2 = s.top(); s.pop();
            int operand1 = s.top(); s.pop();
            
            int result;
            if (token == "+") result = operand1 + operand2;
            else if (token == "-") result = operand1 - operand2;
            else if (token == "*") result = operand1 * operand2;
            else if (token == "/") result = operand1 / operand2;
            
            s.push(result);
        } else {
            // Convert token to number and push
            s.push(stoi(token));
        }
    }
    
    return s.top();
}

int main() {
    vector<string> expressions = {
        "3 4 +",           // 3 + 4 = 7
        "5 2 * 3 +",       // 5 * 2 + 3 = 13
        "15 7 1 1 + - / 3 * 2 1 1 + + -", // Complex expression
        "2 3 1 * + 9 -"    // 2 + 3 * 1 - 9 = -4
    };
    
    cout << "Postfix Expression Evaluation:" << endl;
    for (const string& expr : expressions) {
        cout << expr << " = " << evaluatePostfix(expr) << endl;
    }
    
    return 0;
}