Section Recap

You now understand queues and deques:

$1.$ Queues: FIFO structure. needed for BFS and processing in arrival order.

$2.$ Deques: Double-ended access. Add and remove from both ends in $O(1)$.

$3.$ Monotonic deques: Find max/min over sliding windows in $O(n)$. Store indices, maintain sorted order, remove dominated elements.

$4.$ DP optimization: When transitions look at max/min over last $k$ states, use monotonic deques to go from $O(nk)$ to $O(n)$. The monotonic deque is less famous than the monotonic stack, but equally powerful. Learn both. In the next section, I'll show you hash tables for $O(1)$ lookups.