CONCEPT · 75 minutes
Monotonic stacks, BFS-ready queues, and the bracket-matching patterns that recur again and again — grounded in the Python orchestration scheduler that uses BFS to determine task wave order.
When I was building the Python orchestration framework, I hit two problems in the same week that looked completely different on the surface but had the same root cause: I was using the wrong data structure for the access pattern I needed.
The first was the task scheduler. I needed to determine which tasks were eligible to run in the current wave — those whose dependencies had all completed. My first attempt scanned all pending tasks on every tick: for each task, loop over its dependencies, check if all were done. It worked, but it was O(n x d) per wave, where d was the average number of dependencies. For a 40-task DAG it was barely noticeable; in a stress test with 200 tasks it crawled. The fix was BFS: push all root tasks (no dependencies) into a queue at startup, process them in waves, push their children when each completes. One visit per task, total O(n + e) where e is the edge count.
The second problem was the MDX content validator I bolted onto the build pipeline. It needed to confirm that every opening brace in a code string had a matching close. The natural tool is a stack: push every opening symbol, pop when you see a close, return false the moment a mismatch appears. Twenty lines, zero ambiguity.
That week taught me to separate the two patterns clearly: a stack answers "what is the most recent thing I haven't finished with?" and a queue answers "what has been waiting the longest?" One is LIFO — last in, first out. The other is FIFO — first in, first out. The access pattern you need dictates which one you reach for.
Stacks and queues also appear implicitly. DFS is a stack (the call stack, or an explicit one in the iterative version). BFS is a queue. Recognising the hidden structure inside a traversal algorithm is as important as knowing the data structure itself.
Think of a stack as a physical pile of plates. You can only add a plate on top and only take one off the top. The last plate you put on is the first one you take off — LIFO. In Python, a plain list is a perfectly good stack: append to push, pop to pop. No deque needed here; both operations are O(1) amortized on a list.
The bracket-matching problem shows up constantly — in compilers, in the MDX validator I mentioned, in anything that processes nested structure. The logic is simple: every opening bracket needs a matching close, in the right order, with no interleaving.
The invariant: the stack top is always the most recently opened unmatched bracket. When a closing bracket arrives, it must match the top — not any bracket, the most recent one. If it doesn't, the nesting is broken. If the stack is empty at the end, every open was matched.
When this bites: the return not stack at the end is easy to forget. An input like "(((" has no closing brackets, so the loop body never triggers a return False. A naive early return True gives the wrong answer. The non-empty stack after the loop is the signal that unmatched opens remain.
The monotonic stack is a pattern that confuses people on first contact, then clicks permanently. Here is how I think about it: imagine standing in a crowd and trying to find the first person taller than you. You cannot look forward; you record your own height and wait to be "answered" when someone taller walks past. The stack holds everyone who is still waiting for their answer.
The problem is Daily Temperatures: given a list of daily temperatures, for each day return the number of days until a warmer one. If no warmer day exists, return 0.
flowchart LR
A[For each index i] --> B{Stack not empty AND\ntemps at top less than temps at i?}
B -- Yes --> D[Pop index j\nresult_j = i minus j]
D --> B
B -- No --> E[Push i onto stack]
E --> AThe stack maintains a monotonic decreasing invariant: every index on the stack corresponds to a temperature greater than or equal to the one above it. When a new temperature arrives that is higher than the top's temperature, it "answers" the top — pop it, record the distance, repeat until the invariant holds again, then push the new index.
The key insight: we store indices, not temperature values. The index lets us compute the distance (i - j) and look up the temperature (temps[j]) from the same slot. Time complexity is O(n): each index is pushed once and popped at most once, so the total work across all inner while iterations is O(n).
The monotonic stack family: flip the comparison to greater than instead of less than and you get "next smaller element" using a monotonic increasing stack. The element that triggers a pop is always the answer for everything it pops — only the comparison flips.
A queue is the opposite of a stack in access order: the first thing you put in is the first thing you take out. Think of a line at a box office — the person who arrived first is served first, no exceptions. In Python, the correct queue is collections.deque, not a list.
Why not a list? list.pop(0) is O(n) because Python shifts every remaining element left. On a BFS of a large graph, every node is dequeued exactly once, making the total work O(n squared) just from queue operations. deque.popleft() is O(1) amortized. For BFS that gap matters enormously.
BFS visits nodes in distance order from the source: everything at distance 1 before distance 2, and so on. This level-by-level ordering is exactly what a wave-based scheduler needs.
graph TD
A["Task A (wave 1)"] --> C["Task C (wave 2)"]
B["Task B (wave 1)"] --> C
B --> D["Task D (wave 2)"]
C --> E["Task E (wave 3)"]
D --> E
style A fill:#4ade80,color:#000
style B fill:#4ade80,color:#000
style C fill:#60a5fa,color:#000
style D fill:#60a5fa,color:#000
style E fill:#f87171,color:#fffTasks A and B have no dependencies — they enter the queue first (wave 1). When they complete, C and D become eligible and join the queue (wave 2). Only after both C and D finish does E become eligible (wave 3). BFS discovers these waves automatically.
The wave structure emerges from BFS: drain the queue into a wave, then refill it with everything that just became eligible. This is the same logic used to detect topological order and to measure the critical-path length in a real scheduler.
When this bites: BFS on a very wide graph can use O(n) memory at once — the queue holds an entire level. For a graph where wave 1 contains thousands of tasks, the queue holds all of them before you process any. If memory is tight, iterative DFS with an explicit stack keeps the stack size proportional to path length, not level width — a very different memory profile.
Before the quiz, close the code examples and try these from memory:
"()[]{}" character by character. What is the stack when the function returns?deque rather than a list? What changes at n = 1,000,000 nodes?Reflective prompt: Both the monotonic stack and BFS rely on processing things in a specific order and answering deferred work at the right moment. The monotonic stack answers waiting indices when something bigger arrives; BFS answers waiting tasks when their dependencies complete. Think of a real problem you have hit where work had to be deferred until a condition was met. Was it naturally LIFO (most-recently-deferred answered first, like undo history or recursive calls) or FIFO (longest-waiting answered first, like a job queue or level-order processing)? The access pattern determines the data structure — and getting it wrong by one letter (stack vs queue) completely changes the traversal order.
If you can answer all four questions without looking, the quiz will confirm it. If any felt uncertain, re-read the relevant section.
Application-level questions on stack and queue behaviour, monotonic patterns, and BFS
1. Your bracket-matching function processes '([)]'. At the moment it returns False, what caused the failure?
Correct Answer: B
After '(' push '(', after '[' push '[', then ')' arrives — the stack top is '[', not '(' (which is the required pair for ')'). The mismatch means the brackets are interleaved incorrectly, so the function returns False immediately.
2. In the daily-temperatures monotonic stack, what is stored on the stack?
Correct Answer: B
The stack stores indices, not temperature values. Storing the index lets us compute the distance (i - j) and look up the temperature (temps[j]) when we pop. The temperatures at the stored indices are implicitly in decreasing order, but what is pushed is always the index.
3. Why does BFS use collections.deque instead of a Python list for its queue?
Correct Answer: B
Python list.pop(0) shifts every remaining element left, making it O(n). On a BFS of a million-node graph that means O(n^2) total work just for queue operations. deque is implemented as a doubly-linked list of fixed-size blocks, so popleft() is O(1) amortized.
4. A task scheduler uses BFS from root tasks. Which ordering does it naturally produce?
Correct Answer: B
BFS enqueues a node's neighbours before processing them, so everything at distance 1 from the source is visited before anything at distance 2. For a scheduler this means: all tasks with no dependencies run first (wave 1), their direct dependents run next (wave 2), and so on.
5. You want to find the 'next smaller element' for each index (instead of next greater). Which stack invariant do you maintain?
Correct Answer: B
For 'next greater', you pop when incoming > top (keeping a decreasing stack). For 'next smaller', you pop when incoming < top (keeping an increasing stack). The element that causes a pop is the answer for everything it pops — only the comparison flips.
6. A Min Stack must return the current minimum in O(1) alongside push and pop. What is the standard space trade-off?
Correct Answer: B
The canonical solution keeps a parallel 'min stack'. On push(x), also push min(x, min_stack[-1]) onto the min stack. On pop, pop both. The min stack always holds the minimum of the main stack up to that depth — O(n) extra space for O(1) getMin().
7. You convert recursive DFS to iterative to avoid Python's recursion limit. What data structure replaces the call stack?
Correct Answer: B
Recursive DFS implicitly uses the call stack — each call pushes a frame, returns pop it. Iterative DFS replaces this with an explicit list used as a stack: push the start node, then loop: pop a node, process it, push its unvisited neighbours. LIFO ensures you go deep before going wide, exactly mirroring recursion.
Two classic problems in sequence. The first cements the stack pattern; the second makes the monotonic variant click permanently.
Problem 1: Given a string s containing only '(', ')', '{', '}', '[', and ']', return True if the brackets are valid and False otherwise.
Problem 2: Given a list of integers temps, return a list where result[i] is the number of days until a strictly warmer temperature. Return 0 if no warmer day exists.
Work through both before reading the hints.
Hint 1 — is_valid: Build a pairs dict mapping each closing bracket to its expected open ({')': '(', ...}). Loop over characters: if it is an opener, push it; if it is a closer, check that the stack is non-empty and the top equals pairs[ch]. Return not stack after the loop — leftover opens mean the string is invalid.
Hint 2 — daily_temperatures: The stack stores indices, not temperatures. For each index i, pop indices from the stack while it is non-empty and temps[stack[-1]] < temps[i]. For each popped index j, set result[j] = i - j. Then push i. Everything remaining after the loop stays at 0.
Worked solution: Only open this after your own version passes the assertions.
Going further: once both work, try the Min Stack problem (LeetCode 155). It requires O(1) getMin() alongside push and pop. The trick is an auxiliary stack tracking the running minimum at each depth — the same deferred-work idea you just used, applied to a different question.