Stacks

What is a stack?

A stack is a LIFO (last-in, first-out) data structure: the most recently pushed element is always the first to be removed. The call stack is the real-world analogy - when function A calls B, A is paused; when B returns, A resumes. The most recent call always finishes first.

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

Push and pop are O(1). There is no random access and no O(1) search. The power of a stack is not in retrieval - it is in the ordering guarantee: the top always reflects the most recent unsettled state.

Core operations

Key patterns

Monotonic stack

The stack pattern that turns O(n²) "nearest comparison" problems into O(n).

When to use - you need the next greater or smaller element to the left or right of each position, or a span/area problem where each element's answer depends on the nearest element satisfying a comparison. The naive alternative scans forward from each index at O(n²); a monotonic stack resolves every element in one O(n) pass.

How it works - the stack holds indices still waiting for their answer, maintained in monotonic order. When a new element breaks the order, it IS the answer for everything it pops - pop until the stack is monotone again, then push the newcomer. The pop rule creates the ordering automatically: pop-while-larger leaves only larger elements below, so a next-greater stack is decreasing bottom-to-top without you choosing it. Flip the comparison and the stack inverts.

Example: next warmer day. Given 72, 74, 76, 69, 67, 71, 79, 72, 74 pops 72 and 76 pops 74 on arrival, each writing an answer of 1, while 69 and 67 stack up behind 76 waiting. The 71 pops both waiting days, writing 1 and 2, and the 79 pops 71 and 76, writing 1 and 4. The trailing 72 and the 79 itself never warm, so they keep 0 - the visualizer below steps through all eight days.

Complexity: O(n) time - each element is pushed once and popped at most once. O(n) space.

Bracket matching

The stack pattern for validating nested, last-opened-first-closed structure.

When to use - you need to validate that a string of brackets, tags, or delimiters is properly nested, or evaluate an expression with left-to-right scanning. The naive alternative repeatedly removes adjacent matched pairs at O(n²); a stack validates in one O(n) pass.

How it works - LIFO matches nesting. The most recent unclosed opener must be closed first - exactly what a stack's top gives you. Push openers; on a closer, pop the top and check it matches via a lookup dict. If it doesn't, or the stack was empty when the closer arrived, return False. When the scan ends, any openers still on the stack were never closed; a valid string finishes with an empty stack.

Example: validate nesting. Given ([{}]), the openers (, [, { stack up, then each closer pops its exact match in reverse order: } pops {, ] pops [, ) pops (, leaving the stack empty and the string valid. On ([)], the ) arrives while [ is on top, and the lookup dict says ) needs (, so the mismatch returns False on the spot. The visualizer below runs both sequences.

Complexity: O(n) time, O(n) space in the worst case (all openers).

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.