Deque — Double-Ended Queue

A deque (pronounced "deck") supports $O(1)$ push and pop at both the front and the back. Implementations: doubly linked list or a circular array with two indices.

Sliding window maximum

Given an array and window size $k$, find the max in every window of size $k$. Naive is $O(nk)$. With a deque holding candidate indices in decreasing order of value:

• Before appending a new index, pop from the back any indices whose value is $\leq$ the new value (they can never be the max while the new one is in the window)
• Pop from the front any indices that have slid out of the window
• The front is always the current window's max

$O(n)$ total — each index enters and leaves the deque at most once.

When to use a deque

Whenever you need stack-like access on one side AND queue-like on the other. Examples: undo/redo with a fixed-size history (push new actions at one end, evict old at the other), browser back/forward stacks, and the maxima-tracking pattern above.

Implementations to know

• $C$++: std::deque (chunked array, $O(1)$ at both ends, $O(1)$ random access)
• Python: collections.deque (doubly linked list of blocks; $O(1)$ ends, $O(n)$ middle)
• Java: ArrayDeque (circular array; usually preferred over LinkedList)

Common bug

Forgetting to evict out-of-window indices before reading the front. Sliding-window-max code has two pop loops for a reason — one for the back (maintain monotone order) and one for the front (evict expired indices).