Stacks

You’ll recognise it when

• Things come in pairs that nest: brackets, HTML tags, begin and end. Each closer must match the newest opener that is still open.
• You keep needing the most recent unmatched thing: the last open bracket, the last folder you entered, the last item still waiting.
• There’s an undo: actions are reversed newest first.
• You’re evaluating an expression. In postfix, 3 4 + 2 *, each operand waits until its operator arrives.
• A recursive solution is right, but the recursion is too deep for Python. An explicit stack does the same work in a loop.

It’s easy to confuse with the monotonic stack, a stack with one extra rule: pop everything smaller before you push. Reach for that one when each element needs its next bigger or smaller neighbour.

The idea

Think of a pile of plates. You put plates on top and take them from the top. The plate you can reach is always the one you put down last. That’s last in, first out, or LIFO.

A stack has three operations, and each takes O(1): push puts a value on top, pop removes the top and returns it, and peek reads the top without removing it. In Python a plain list is the stack: stack.append(x), stack.pop() and stack[-1]. In C++ use a vector (push_back, pop_back, back), and in Java an ArrayDeque (push, pop, peek).

The point of a stack is that it gives things back in the order you’ll need them. When the newest unfinished item must be handled first, the stack keeps it on top for you.

Its first-in, first-out partner is the queue, like a line at a till: add at the back, take from the front. In Python use collections.deque with append and popleft. A deque (double-ended queue) does both jobs: it pushes and pops at either end in O(1).

How it works

We’ll check whether the brackets in a string are balanced: every opener is closed by the same kind, in the right order.

Scroll through the steps and the graphic follows along. The string runs along the top, and the stack stands on the right with its top at the top. You can also press play, or edit the input: try ([)], a lone ), or ((.

Why it’s correct: the stack always holds the openers that are still open, oldest at the bottom. Proper nesting means the next closer must close the newest of them, so checking the top is enough. A string can fail in exactly three ways, and each is one line of the code: a closer arrives when the stack is empty, a closer doesn’t match the top, or openers are left over at the end.

PAIRS = {")": "(", "]": "[", "}": "{"}   # each closer and the opener it needs


def is_balanced(s):
    """True if every bracket in s is closed by the same kind, in the right order."""
    stack = []
    for ch in s:
        if ch in "([{":
            stack.append(ch)
        elif ch in PAIRS:
            if not stack or stack[-1] != PAIRS[ch]:
                return False
            stack.pop()
    return not stack

#include <string>
#include <vector>
using namespace std;

// The opener that a closing bracket needs.
char openerFor(char close) {
    if (close == ')') return '(';
    if (close == ']') return '[';
    return '{';
}

// True if every bracket in s is closed by the same kind, in the right order.
bool isBalanced(const string& s) {
    vector<char> stack;
    for (char ch : s) {
        if (ch == '(' || ch == '[' || ch == '{') {
            stack.push_back(ch);
        } else if (ch == ')' || ch == ']' || ch == '}') {
            if (stack.empty() || stack.back() != openerFor(ch))
                return false;
            stack.pop_back();
        }
    }
    return stack.empty();
}

import java.util.ArrayDeque;
import java.util.Deque;

class Brackets {
    // The opener that a closing bracket needs.
    static char openerFor(char close) {
        if (close == ')') return '(';
        if (close == ']') return '[';
        return '{';
    }

    // True if every bracket in s is closed by the same kind, in the right order.
    static boolean isBalanced(String s) {
        Deque<Character> stack = new ArrayDeque<>();
        for (char ch : s.toCharArray()) {
            if (ch == '(' || ch == '[' || ch == '{') {
                stack.push(ch);
            } else if (ch == ')' || ch == ']' || ch == '}') {
                if (stack.isEmpty() || stack.peek() != openerFor(ch))
                    return false;
                stack.pop();
            }
        }
        return stack.isEmpty();
    }
}

Why it’s O(n)

Each character is read once. An opener costs one push. A closer costs one peek and at most one pop. All of them are O(1), so the whole scan is O(n).

“Amortised” means a push sometimes has to grow the list and copy it, but averaged over all pushes each one is O(1).

Space is O(n) in the worst case: a string of only openers, like ((((, pushes every character.

Common mistakes

if stack[-1] != PAIRS[ch]:                # ✗ crashes on ")"
if not stack or stack[-1] != PAIRS[ch]:   # ✓ empty means nothing to match

return True        # ✗ "((" passes
return not stack   # ✓ anything left was never closed

stack.append(stack.pop() - stack.pop())   # ✗ computes 2 - 8
b, a = stack.pop(), stack.pop()
stack.append(a - b)                       # ✓ 8 - 2

first = queue.pop(0)       # ✗ O(n) on a list
first = queue.popleft()    # ✓ O(1) on a collections.deque

Variations

• Postfix evaluation. Push numbers. On an operator, pop two values, apply it (the first one popped goes on the right), and push the result. One value is left at the end.
• Minimum in O(1). Push the pair (x, min(x, current minimum)) instead of x. The minimum of the whole stack is always on top, and popping brings back the previous minimum for free.
• Undo log. For each action, push what you need to reverse it: how many letters were typed, or the text that was deleted. Undo pops the newest entry and applies it.
• Replacing recursion. Push the work a recursive call would have done, and loop while the stack isn’t empty. This is how depth-first search avoids Python’s recursion limit of about 1,000.
• A queue from two stacks. Push onto an “in” stack. When the “out” stack is empty, pour everything across: pouring reverses the order, so the oldest item lands on top. Each item moves at most once, so every operation is O(1) amortised.