Stack — The Pancake Pile

Real-world analogy

What is it?

A stack is a fundamental data structure that follows the LIFO (Last In, First Out) principle. You can only add (push) and remove (pop) elements from the top. It's like a stack of pancakes or plates — you always deal with the top item. Stacks are essential for bracket matching, undo operations, expression evaluation, and many competitive programming problems.

Real-world relevance

Your browser's back button is a stack of visited pages. The Ctrl+Z undo feature in every text editor uses a stack of actions. Call centers put callers on hold in a stack (sometimes!). Even the way your computer runs functions (the call stack) is a stack. Compilers use stacks to check if your parentheses and brackets are balanced.

Key points

• What is a Stack? — A stack is a data structure where you can only add and remove elements from the TOP. It follows the LIFO principle: Last In, First Out. The last thing you put in is the first thing you take out. Think of a stack of books, plates, or pancakes!
• Push — Add to the Top — The 'push' operation adds an element to the top of the stack. Like placing a new pancake on top of the pile. In C++: myStack.push(42); adds 42 to the top. You can push as many elements as you want.
• Pop — Remove from the Top — The 'pop' operation removes the top element from the stack. Like taking the top pancake off the pile. In C++: myStack.pop(); removes the top element. WARNING: never pop an empty stack — it causes an error!
• Top — Peek at the Top — The 'top' operation lets you see what's on top WITHOUT removing it. Like looking at the top pancake without eating it. In C++: myStack.top(); returns the top element. Always check if the stack is empty before using top()!
• Empty and Size — myStack.empty() returns true if the stack has no elements. myStack.size() tells you how many elements are in the stack. Always check empty() before calling top() or pop() to avoid crashes!
• C++ stack from STL — C++ gives us a ready-made stack in the Standard Template Library. Just use: stack s; for a stack of integers, or stack s; for a stack of strings. You need #include (or bits/stdc++.h which includes everything).
• Bracket Matching — Classic Stack Problem! — Given a string like '({[]})', check if every opening bracket has a matching closing bracket in the right order. Push opening brackets onto the stack. When you see a closing bracket, check if the top of the stack is the matching opening bracket. If the stack is empty at the end, the brackets match!
• Reverse a String with a Stack — Push each character onto a stack, then pop them all off. Since stacks are LIFO, the characters come out in reverse order! push 'h','e','l','l','o' → pop gives 'o','l','l','e','h' = 'olleh'. A simple but powerful trick!
• Where Stacks Are Used — The undo button (Ctrl+Z) uses a stack — each action is pushed, and undo pops the last one. Your web browser's back button is a stack of pages. The call stack in recursion (lesson 32) is literally a stack! Stacks are everywhere in CS.

Code example

#include <bits/stdc++.h>
using namespace std;

// Check if brackets are balanced
bool isBalanced(string s) {
    stack<char> st;
    for (char c : s) {
        if (c == '(' || c == '{' || c == '[') {
            st.push(c);  // Push opening brackets
        } else if (c == ')' || c == '}' || c == ']') {
            if (st.empty()) return false;  // No matching opener
            char top = st.top();
            st.pop();
            // Check if the brackets match
            if (c == ')' && top != '(') return false;
            if (c == '}' && top != '{') return false;
            if (c == ']' && top != '[') return false;
        }
    }
    return st.empty();  // All brackets matched?
}

int main() {
    // Basic stack operations
    stack<int> s;
    s.push(10);   // Stack: [10]
    s.push(20);   // Stack: [10, 20]
    s.push(30);   // Stack: [10, 20, 30]
    
    cout << "Top: " << s.top() << "\n";    // 30
    cout << "Size: " << s.size() << "\n";   // 3
    
    s.pop();  // Remove 30. Stack: [10, 20]
    cout << "Top after pop: " << s.top() << "\n";  // 20
    
    // Bracket matching
    cout << "({[]}) balanced? " << (isBalanced("({[]})") ? "YES" : "NO") << "\n";
    cout << "({[}) balanced? " << (isBalanced("({[})") ? "YES" : "NO") << "\n";
    
    return 0;
}

Line-by-line walkthrough

1. 1. #include — includes everything, including the stack library.
2. 2. bool isBalanced(string s) — a function that takes a string and returns true if all brackets are properly matched and nested.
3. 3. stack st; — we create a stack that holds characters. We'll push opening brackets onto it.
4. 4. for (char c : s) — we loop through every character in the string, one at a time.
5. 5. if (c == '(' || c == '{' || c == '[') st.push(c); — when we see an opening bracket, we push it onto the stack. We'll check for its match later.
6. 6. if (st.empty()) return false; — if we see a closing bracket but the stack is empty, there's no matching opening bracket, so the string is NOT balanced.
7. 7. char top = st.top(); st.pop(); — we get the top of the stack (the most recent opening bracket) and remove it. Then we check if it matches the closing bracket we found.
8. 8. return st.empty(); — at the end, if the stack is empty, every opening bracket found its match. If not, there are unmatched opening brackets.
9. 9. In main(), we demonstrate push, top, size, and pop operations, then test our bracket matching function with two examples.

Spot the bug

#include <bits/stdc++.h>
using namespace std;

int main() {
    stack<int> s;
    s.push(10);
    s.push(20);
    s.push(30);
    
    while (s.size() > 0) {
        s.pop();
        cout << s.top() << " ";
    }
    return 0;
}

Explain like I'm 5

Fun fact

Hands-on challenge

More resources

• Stacks — Data Structures (HackerRank)
• Stack in C++ STL (GeeksforGeeks)
• Stack Problems (Codeforces)