Queue and Monotonic Deque

A FIFO structure that underlies BFS. The monotonic deque maintains a window's max/min in O(1) amortized by popping from the back while it's dominated by the incoming element — the deque analogue of the monotonic stack.

Sub-patterns

• A — Standard Queue as a BFS Driver. The queue that drives level-by-level traversal, reused constantly from here through Graphs.
• B — Monotonic Deque. Maintains a sliding window's max/min in O(1) amortized.
• C — Circular Queue Design. A fixed-capacity ring-buffer queue as a design problem.

Practice set (6)

• Medium — Design Circular Queue, Dota2 Senate, Number of Recent Calls
• Hard — Sliding Window Maximum, Shortest Subarray with Sum at Least K, Constrained Subsequence Sum