Stacks & Queues
Last-in-first-out and first-in-first-out — and how to recognise which one a problem needs
Stacks and queues are the same idea — a sequence you add to and remove from — differing only in which end you remove from. That single choice determines which problems they solve.
What They Actually Look Like
Both are just a list with a rule about where you are allowed to touch it. The rule is the entire point: by giving up random access, you get a structure whose behaviour matches how certain problems are shaped.
The names
| Word | Stack | Queue |
|---|---|---|
| Add an item | push | enqueue |
| Remove an item | pop | dequeue |
| Look without removing | peek / top | front |
| Order | LIFO — last in, first out | FIFO — first in, first out |
Everyday version: a stack is a pile of plates — you take from the top, which is the one added most recently. A queue is a line at a shop — first to arrive is first served.
A stack, operating
Everything happens at one end. The bottom of the pile is untouchable until everything above it has gone.
A queue, operating
Two ends. You add at the back and remove from the front, so order is preserved instead of reversed.
Why this one difference matters so much
Put the same three items through both and you get opposite outputs — 3, 2, 1 versus 1, 2, 3.
That is the whole reason DFS and BFS are different algorithms. They share identical code; one holds pending work in a stack, the other in a queue. Serving newest-first makes you dive; serving oldest-first makes you sweep.
One line of difference, two completely different behaviours.
Stack — Last In, First Out
Reach for a stack whenever the most recent thing is the first thing you need to resolve.
Signals that a stack is the answer
- Nesting — brackets, tags, nested structures (Valid Parentheses)
- Undo / go back —
..in a path (Simplify Path) - Deferred operands — postfix evaluation (Evaluate Reverse Polish Notation)
- Depth-first traversal — recursion is a stack, whether you manage it or the runtime does
Queue — First In, First Out
Reach for a queue when things must be processed in arrival order.
- Level-by-level exploration — Binary Tree Level Order Traversal
- Shortest path in an unweighted graph — BFS reaches every node in the fewest possible steps
Do not use a plain list as a queue
Python: list.pop(0) is O(n) because everything shifts left. Use collections.deque, whose popleft is O(1).
TypeScript: Array.prototype.shift() has the same cost. Either keep a read index into the array, or build a fresh array per BFS level.
Getting this wrong silently turns an O(n) traversal into O(n²).
Augmented Stacks
A stack can carry extra state alongside its values, giving O(1) answers to questions that would otherwise need a scan.
- Min Stack — every entry stores the minimum as of its push
The same idea powers monotonic stacks, which keep their contents sorted and solve "next greater element" style problems in linear time.
Language Notes
| Operation | Python | TypeScript |
|---|---|---|
| Push | stack.append(x) | stack.push(x) |
| Pop | stack.pop() — raises on empty | stack.pop() — returns undefined |
| Peek | stack[-1] | stack[stack.length - 1] |
| Enqueue | queue.append(x) | queue.push(x) |
| Dequeue | queue.popleft() (deque) | index-based read, or swap arrays |
That difference in pop behaviour on an empty container shows up repeatedly: Python needs an explicit emptiness check where TypeScript's undefined falls through harmlessly.
All Problems
| Problem | Difficulty | Pattern |
|---|---|---|
| Valid Parentheses | Easy | Stack |
| Min Stack | Medium | Augmented Stack |
| Evaluate Reverse Polish Notation | Medium | Stack |
| Simplify Path | Medium | Stack |