Stacks

What is a stack?

A stack is a LIFO (last-in, first-out) data structure: the most recently added element is always the first to be removed. The call stack is the clearest real-world analogy - when function A calls B, A is paused and suspended; when B returns, A resumes. The most recent call is always resolved before older ones.

In Python, there is no separate stack class. A plain list serves the purpose directly:

stack = []
stack.append(42)   # push
stack.append(17)
top = stack[-1]    # peek: 17, no removal
stack.pop()        # pop: removes and returns 17

This works because Python's list provides O(1) amortized append (push) and O(1) pop from the right end. The stack grows rightward; the top is always stack[-1].

The core trade-off: push and pop are O(1), but there is no random access and no O(1) search. If you need to find a value, you must scan from the top. The power of a stack is not in retrieval - it is in the ordering guarantee that the top always reflects the most recent unsettled state.

Core operations

Key patterns

Monotonic stack

Keep the stack sorted in one direction. An element that breaks the order pops everything it dominates before it goes on.

When to use - you want the nearest element to the left or right that beats a comparison: next greater, next smaller, stock spans, largest rectangle. Brute force checks every pair at O(n²). A monotonic stack answers all of them in one O(n) pass.

How it works - pick the direction by the question: a decreasing stack finds next-greater, an increasing stack finds next-smaller. When an incoming element breaks the order, pop until it fits - each element you pop has just found its answer in the incomer. Store indices, not values, so you can write the answer back by position. Every element is pushed once and popped at most once, so the whole pass is O(n) amortized.

Bracket matching

Use the stack to remember every opener that hasn't been closed yet, and match each closer against the most recent one.

When to use - anything with nested, last-opened-first-closed structure: validating brackets or tags, parsing expressions, checking that delimiters balance. A stack is LIFO, which is exactly how nesting works, so one O(n) scan does it.

How it works - push each opening bracket. On a closer, the only thing it can validly match is the top of the stack - the most recently opened bracket - so pop it and check. If it doesn't match, or the stack was empty when the closer arrived, the string is invalid. When the scan ends, any openers still on the stack were never closed; a valid string finishes with an empty stack.

Canonical examples

Daily temperatures (monotonic stack)

For each day, how many days until a warmer temperature? A brute-force O(n²) scan works, but a monotonic stack solves it in O(n). The key insight: push each day's index onto the stack; when we see a warmer day, every day still waiting on the stack gets its answer at that moment.

Valid parentheses

The bracket matching pattern applied directly: a stack of unmatched openers, a dict for O(1) pair lookup, and a final emptiness check to catch unclosed brackets.

When to reach for a stack

• The problem involves matching or nesting - brackets, function calls, HTML tags.
• You need the next greater or smaller element to the left or right of each position.
• You're simulating a call stack or evaluating an expression left to right.
• The problem mentions undo/redo - stacks model history naturally.
• You need to implement DFS iteratively without recursion.

Practice problems

• Valid Parentheses - The canonical bracket matching problem.
• Min Stack - Augment a stack to track the running minimum in O(1).
• Daily Temperatures - Monotonic stack, nearest warmer day.
• Evaluate Reverse Polish Notation - Operand stack with arithmetic.
• Largest Rectangle in Histogram - Monotonic stack for span calculation; the hardest stack problem.