Stacks and queues are lists with rules about which end you add to and remove from. Those rules make some problems almost trivial: anything with nesting, undo, "the most recent unmatched thing", or processing in arrival order.
Stack: last in, first out
Push items on top, pop the top item off. Think of a stack of plates.
| Operation | Python list | JavaScript Array | Cost |
|---|---|---|---|
| Push | stack.append(x) | stack.push(x) | O(1) |
| Pop | stack.pop() | stack.pop() | O(1) |
| Peek at the top | stack[-1] | stack[stack.length - 1] | O(1) |
| Is it empty? | not stack | stack.length === 0 | O(1) |
Use a stack when the most recent thing you haven't finished with is the one that matters next: matching brackets, undo history, evaluating expressions, and depth-first search without recursion.
Push 3: it goes on top.
Queue: first in, first out
Add at the back, remove from the front, like a line at a shop.
| Operation | Python | JavaScript | Cost |
|---|---|---|---|
| Add to the back | queue.append(x) (with collections.deque) | queue.push(x) | O(1) |
| Remove from the front | queue.popleft() | queue[head++] (keep an index) | O(1) |
Use a queue when you process things in the order they arrived: breadth-first search, task scheduling, and streams of events.
D joins at the back.
OK, but when would a stack actually save me in an interview?
Pattern: matching pairs
For brackets, tags or anything that opens and closes: push each opener; when a closer arrives, it must match the opener on top of the stack, so pop it and compare. At the end, the stack must be empty (nothing left open).
'(' opens: push it.
Pattern: the monotonic stack
A monotonic stack keeps its items in sorted order (for example, values decreasing from bottom to top). When a new item arrives, pop everything it "beats" first. Each popped item has just found its answer: the next bigger item is the one that popped it.
1answer = [0] * len(values)2stack = [] # indexes whose next bigger value isn't known yetindexes still waiting for an answer
3for i, v in enumerate(values):4 while stack and values[stack[-1]] < v:v beats the waiting values...
5 j = stack.pop()6 answer[j] = i - j # v is the next bigger value for j...so v is their next bigger value
7 stack.append(i)now v waits for its own answer
Every index is pushed once and popped at most once, so this is O(n), not O(n²). Look for monotonic stacks in "next greater", "previous smaller", "how many days until...", and skyline/histogram problems.
18 and 17 wait on the stack: neither has met a bigger value yet.
Common mistakes
- Popping from an empty stack: check
if stackfirst, and decide what an unmatched closer means. - Forgetting the final check: a leftover opener means the input wasn't balanced.
- Using
list.pop(0)/shift()in a loop and turning an O(n) algorithm into O(n²).
Nice work!
You've got the big idea. Try the quick quiz below, then put it to work on the practice problems.