Stacks: Last In, First Out

A stack of plates

Imagine a tall stack of cafeteria plates. You add a plate on top, and you take a plate from the top. You never pull one from the middle. The last plate you put on is the first one you take off — that's Last In, First Out, or LIFO.

A stack is an abstract data type: it's defined by what you can *do* with it, not how it's built. There are only three real operations.

1. push(x): place x on top.
2. pop(): remove the top item and return it.
3. top() / peek(): look at the top item without removing it.

push 3        top -> | 3 |
              |       | 2 |
              v       | 1 |
                      '---'   bottom

pop  -> 3     top -> | 2 |
                      | 1 |
                      '---'

Using std::stack

The C++ standard library hands you a ready-made stack. All three operations run in O(1) — constant time, no matter how tall the stack gets.

#include <stack>
#include <iostream>

std::stack<int> s;
s.push(1);
s.push(2);
s.push(3);
std::cout << s.top();   // 3 (the last one pushed)
s.pop();                // removes 3
std::cout << s.top();   // 2

Rolling your own

A stack is so simple you can build it on top of an array (or a dynamic array like `std::vector`) in a few lines. "The top" is just the last filled slot — and adding or removing at the end is O(1), no shifting required.

#include <vector>

struct Stack {
    std::vector<int> data;
    void push(int x) { data.push_back(x); }   // O(1) amortized
    int  top()       { return data.back(); }   // O(1)
    void pop()       { data.pop_back(); }       // O(1)
    bool empty()     { return data.empty(); }
};

Why is `push_back` O(1) if the vector sometimes has to grow? Because growth doubles the capacity, so the occasional expensive copy is spread thin across many cheap pushes — what we call amortized O(1). You saw this with dynamic arrays in Foundations.

Where stacks show up

Stacks are everywhere once you spot the LIFO shape. The call stack is how your program remembers where to return after each function call — every step into recursion pushes a frame, every return pops one. Undo in an editor pops your most recent action first. And matching brackets in code is a classic stack puzzle.

Bracket matching works like this: scan left to right. On every opening bracket, push it. On every closing bracket, pop and check it matches. If anything mismatches, or the stack isn't empty at the end, the brackets are unbalanced.

// Is a string of () [] {} balanced?
bool balanced(const std::string& s) {
    std::stack<char> st;
    for (char c : s) {
        if (c=='(' || c=='[' || c=='{') st.push(c);
        else {
            if (st.empty()) return false;          // closer with nothing open
            char o = st.top(); st.pop();
            if ((c==')'&&o!='(') || (c==']'&&o!='[') ||
                (c=='}'&&o!='{')) return false;     // wrong match
        }
    }
    return st.empty();   // leftover openers => unbalanced
}