Queue and Deque Patterns
A queue turns up in two quite different roles. As the engine of breadth-first search it enforces that everything one step away is handled before anything two steps away, which is what makes BFS find shortest paths. As a double-ended queue it becomes the monotonic deque, which answers the maximum of every sliding window in linear time, something neither a heap nor a rescan can do.
Where to start, and what comes next
- 01
BFS Queue
Start here, because BFS is the reason the structure matters. Level order, shortest path and multi-source all share one loop.
- 02
Monotonic Deque
The monotonic deque. Harder, and the payoff is the sliding window maximum, which is a common hard-tier question.
- 03
Queue Design
Circular queues and building a queue from two stacks. Both are about amortised cost and index arithmetic rather than algorithms.
If you only have time for three things
- Snapshotting the queue size before each BFS level, without which the level boundaries disappear as children are enqueued.
- Seeding the queue with every source at once for multi-source BFS, which solves rotting oranges and nearest-zero in one pass instead of one per cell.
- The monotonic deque's two removal rules, which are easy to conflate: the back is trimmed by value, the front is dropped by index leaving the window.
If a problem asks for the fewest steps or moves and the edges are unweighted, BFS is almost certainly the answer and saying so quickly is worth points. The follow-up is often about memory, since BFS holds an entire level, and being able to say when DFS would be cheaper shows you understand the trade rather than defaulting.
The idea underneath
BFS = queue. If you need shortest path in an unweighted graph or level-order traversal, reach for a queue. Monotonic deques solve sliding window extremes in O(n).
Problems that use these patterns
Head to head
Questions people ask
Why does BFS find shortest paths but DFS does not?
Because a queue hands nodes back in discovery order, which is by distance. The first time BFS reaches a node it has done so along a path of minimum length. DFS explores one branch to its end first, so the path it happens to find has no relation to distance.
When would a heap be worse than a deque for window maximums?
Always, for this problem. A heap gives O(n log k) and cannot cheaply remove an element that has left the window, forcing lazy deletion. The deque is O(n) because each index enters and leaves exactly once.
LinkedList or ArrayDeque?
ArrayDeque, in almost every case. Both implement Queue, but ArrayDeque is backed by a circular array with far better cache behaviour and no per-element node allocation.