Lesson 05 of 16 · 14:58
Stacks & queues
Stacks and queues contain ordinary items; their power comes from deciding which unresolved item is processed next. A stack chooses the newest item and naturally goes deep. A queue chooses the oldest item and naturally preserves discovery order or distance layers.
Before selecting either structure, describe the scheduling guarantee you need. That proof is more important than memorizing that DFS uses a stack and BFS uses a queue.
What you should be able to do after this lesson
- Derive the container from removal order
- Keep only unresolved work in the structure
- Use Python operations whose endpoint costs match the algorithm
The mental model
The data structure is a scheduling policy: a stack says ‘finish the newest branch first’; a queue says ‘finish the oldest discovered layer first.’
Recognize it when: Use a stack for nested syntax, undo, monotonic candidates, and iterative DFS. Use a queue for BFS, streaming buffers, and level-by-level work.
The invariant to say aloud: Every stored item is unresolved work, and the next removal order is exactly the order required by the algorithm’s guarantee.
Learn the ideas one at a time
Concept 1 of 4
Stack / LIFO
Watch from 0:00 ↗Push and pop at one end. The last item inserted leaves first, matching nested delimiters, recursion simulation, and depth-first exploration.
Last-in, first-out matches nested work: the most recently opened delimiter must close first, and the most recently discovered branch is explored next. The stack should hold just enough information to resume unresolved work, such as an index, node, or partial state.
Walk through an example
For '([])', push '(' then '['. On ']', the top '[' matches and is removed; on ')', the top '(' matches. An empty stack at the end proves every opener was matched in the correct nesting order.
In an interview
Explain what each stack entry represents and why the top is exactly the next item that must be resolved.
Concept 2 of 4
Queue / FIFO
Watch from 0:00 ↗Enqueue at the back and dequeue at the front. The first item inserted leaves first, which preserves BFS discovery layers.
First-in, first-out preserves the order in which work was discovered. In breadth-first search, all nodes one edge away are enqueued before nodes two edges away, so the first time an unweighted node is reached gives its shortest distance.
Walk through an example
Start with A. Remove A and enqueue B, C. Remove B and enqueue its unseen neighbors, then remove C. Every depth-1 node leaves the queue before any depth-2 node.
In an interview
Mark an item seen when it is enqueued, not when removed, so the same work is not inserted repeatedly by multiple parents.
Concept 3 of 4
Deque in Python
Watch from 0:00 ↗collections.deque supports append, appendleft, pop, and popleft in O(1). Popping index 0 from a list shifts the remaining array and costs O(n).
collections.deque is designed for efficient operations at both ends. A list is efficient as a stack at its right end, but removing index 0 shifts all remaining values. The abstract algorithm may be linear while the wrong container makes the implementation quadratic.
Walk through an example
A BFS that performs list.pop(0) for n queued nodes repeatedly shifts the remaining queue. Replacing it with deque.popleft() keeps each removal O(1).
In an interview
Name the endpoint operations you need, then choose list or deque deliberately rather than by habit.
Concept 4 of 4
Monotonic stack
Watch from 0:00 ↗Keep only unresolved candidates in increasing or decreasing order. When a new value invalidates the top, pop until the ordering invariant is restored.
A monotonic stack removes candidates that a new value proves can never be the answer for future positions. Each surviving item remains unresolved and ordered. Although one input may pop many entries, every entry is pushed once and popped at most once, giving linear total work.
Walk through an example
For temperatures [73, 74, 71, 76], 74 resolves 73, 71 waits, and 76 resolves both 71 and 74. The stack holds indices whose next warmer day has not yet been found.
In an interview
State what makes the top obsolete and what the stack's increasing or decreasing order means. That is the proof, not merely the pattern name.
Before you call this lesson done
- Define each stored item
- Justify why top or front is next
- Use deque for left-end removals
- Bound each item’s pushes and pops
