Stacks & Queues
- State the LIFO and FIFO contracts and pick the right one from a problem description
- Implement a stack with a list and a queue with collections.deque, with correct costs
- Solve bracket-matching with a stack and explain why a counter is not enough
- Apply a monotonic stack to a next-greater-element problem
- Name three real systems built on each structure (undo, call stack, task queues…)
| Spaced-rep warm-up: Days 23–24 cards + due deck | 10 min |
| ELI5 + tech read, watch the stack-ops visualizer | 20 min |
| Guided: brackets + deque timing + monotonic stack | 35 min |
| Practice: queue-from-stacks + min-stack | 20 min |
| Project: pattern log + in-the-wild inventory | 20 min |
| Quiz + flashcards | 10 min |
Builds on: Day 4 — Collections — lists · Day 22 — Big O & complexity · Day 23 — Arrays & hashing
In a cafeteria, clean trays are stacked in a pile: the tray you take is the LAST one added — whatever is on top. Nobody excavates the bottom tray. That is a stack: Last In, First Out. It sounds trivially simple, but LIFO is exactly the shape of *interrupted work*: you're washing dishes, the phone rings, mid-call the doorbell goes — you answer the door, THEN finish the call, THEN return to dishes. Most-recently-interrupted resumes first. Your editor's undo, your browser's back button, and Python's function-call bookkeeping are all tray piles.
The lunch line is the other contract: First In, First Out. The person who arrived first is served first — anything else causes a riot. FIFO is the shape of *fairness and order-preservation*: print jobs, requests to a server, tickets in a support queue. Two dumb-simple rules — "take from the top" and "take from the front" — and the entire skill is recognizing which one a problem is secretly asking for: does the most RECENT thing matter first (nesting, undo, backtracking), or the OLDEST (scheduling, buffering, breadth-first anything)?
Stacks and queues are how systems you'll build actually organize work. Every task queue between your API and its workers (Day 47) is FIFO; every traceback you read (Day 19) is a printout of the call stack; agent frameworks (Day 120) maintain stacks of pending sub-tasks and queues of tool results. Interview-wise, bracket matching and monotonic stacks are perennial, and BFS — the algorithm that powers Day 31's shortest paths — is literally "a loop around a queue". Choosing deque over list.pop(0) is also a classic complexity trap you can now name on sight.
The tray pile — matching brackets in "{[()]}"
step 1 / 6A stack is a tray pile: add on top, take from top, never from the middle. LIFO. We'll use it to check whether "{[()]}" is balanced.
Guided practice
Brackets: the stack earns its keep
15 min- In
stacks_lab.py, implementis_balanced(s)for the three bracket pairs using the starter's mapping trick. - Run the test block — including "([)]", the case that defeats counters. In a comment, explain in one sentence WHY the counter fails on it.
- Extend: make it ignore non-bracket characters so real code snippets can be checked, and test it on a line of Python from your own repo.
- Implement
undo_demo(): a 10-line action history where each string command is pushed, and "undo" pops and prints what was reverted. Stacks stop being abstract the moment you build undo.
Queues done right + the monotonic stack
20 min- In
queues_lab.py, run the starter's timing comparison: drain a 100k-element queue vialist.pop(0)vsdeque.popleft(). Record both times and name the complexity of each drain (Day 22 reflex). - Implement
daily_temperatures(temps): for each day, how many days until a warmer one (0 if never). Use the monotonic stack of indices from the starter skeleton; trace [73, 74, 75, 71, 69, 72, 76, 73] by hand for the first four elements in a comment. - State the O(n) argument in a comment: how many times can each index be pushed and popped?
- Bonus wiring for Day 31: write
bfs_preview(grid_neighbors, start)— 6 lines: deque, seen-set, popleft loop — and run it on the tiny graph in the starter. You have just written the skeleton of every BFS you will ever need.
On your own
Two solo
20 min(1) Queue via two stacks: implement a class with enqueue and dequeue using ONLY two lists used as stacks (no deque, no pop(0)). Then make the amortized O(1) argument for dequeue: each element crosses from the in-stack to the out-stack at most once in its lifetime.
(2) Min-stack: a stack supporting push, pop, and get_min, all O(1). Constraint: no scanning on get_min.
Hints: for (1), only refill the out-stack when it is empty — that laziness is where the amortization comes from. For (2), keep a second stack recording the minimum *as of* each pushed element; pop them in lockstep.
Pattern log: LIFO/FIFO section + systems inventory
Add the "Stacks & Queues" section to patterns.md with the usual four parts (when to reach for each contract, solved problems with one-line tricks, recognition cues — "nested", "most recent first", "in order of arrival", "next greater" — and honest costs, headlined by the list.pop(0) trap with YOUR measured timings). Then add a "in the wild" inventory: find three real stack appearances and three real queue appearances in systems you actually use or have built (traceback = call stack; git stash; your editor's undo; a printer spooler; the Day 16 logging handlers' internal queue…), each with one sentence on why that contract fits. Commit.
Common mistakes & misconceptions
- Using list.pop(0) for a queue. Every dequeue shifts the whole list: O(n) each, O(n²) to drain. deque.popleft() exists precisely for this — you timed the difference today.
- Matching brackets with counters. Counters verify quantity, not order: "([)]" balances every counter and is still invalid. Nesting is LIFO; only a stack remembers it.
- Forgetting the end-of-input check: a bracket string is valid only if the stack is EMPTY at the end. "(((" passes every per-character check and must still fail.
- Popping from an empty stack without a guard. Check `if not stack` before touching stack[-1] — the empty case is the first edge every interviewer probes.
- Storing values instead of indices in a monotonic stack. The answer is usually a distance or position; values alone cannot recover it.
- Reaching for a stack or queue when you need random access. They are access-DISCIPLINE structures; if you need the middle, you want yesterday's array or a dict.
Q1. Why does bracket matching need a stack rather than open/close counters?
Q2. Draining an n-element queue implemented as a Python list with pop(0) costs…
Q3. A problem asks: "for each element, find the NEXT element to its right that is larger." The efficient tool is…
Go deeper — curated resources
- Largest rectangle in histogram — The monotonic stack's hardest classic. If daily_temperatures felt clean, study how the same "pop when a smaller bar arrives" idea computes rectangle areas — a genuinely beautiful O(n) algorithm.
- All lab asserts pass; list vs deque timings recorded
- Both practice structures work with their amortized/O(1) arguments written
- patterns.md section + six-item systems inventory committed
- Quiz ≥ 2/3
← Back: The monotonic stack's "pushed once, popped once" argument is Day 24's amortized reasoning reappearing within a day. The traceback you learned to read on Day 19 is a call-stack printout — today you know the structure behind it.
Forward →: Day 27 makes the call stack visible when recursion runs. Day 31 wraps a loop around today's deque and calls it BFS. Day 47 scales the lunch line into message queues between services, where FIFO plus retries powers real AI pipelines.
Unlocks: D27 Recursion & Divide/Conquer · D29 Binary Trees & BSTs · D31 Graphs, BFS & DFS