Double-ended queue

A double-ended queue supports insertion and removal at both ends. It combines the access patterns of a stack and a queue without promising fast arbitrary indexing. For example, appending a,b at the right and then c at the left produces c,a,b; removing at the right returns b. A circular array or a doubly linked list can implement the abstraction, with different allocation and indexing costs. Python's deque provides approximately constant-time end operations, unlike repeatedly inserting at the start of an ordinary list.^[ref]

A deque can use two permanent stacks holding the front and back portions, plus an empty temporary stack. When removal encounters an empty side, park the top half of the other side in the temporary stack, reverse its remaining half into the empty side, and restore the parked half. This preserves order and balances the permanent stacks. The potential method with $\Phi =3||F|-|B||$ pays for the linear time transfer from the previous size imbalance, giving constant amortized cost for all four endpoint operations with only a fixed number of size counters.

In an endpoint-based double-ended queue represented by a doubly linked list, the first and last references are both null exactly when the double-ended queue is empty. Otherwise the first node has null predecessor, the last has null successor, and the finite successor chain is acyclic.

The two directions must agree: if node $x$ has successor $y$, then $y$ has predecessor $x$, and conversely for a nonnull predecessor. Thus following successors and following predecessors visit the same linked list nodes in reverse order.

Removing the only linked list node must clear both endpoints. Clearing only the endpoint used by that operation would leave one traversal apparently empty and the reverse traversal still reaching the removed node. The representation invariant makes that error visible before it affects later operations.

A monotonic queue keeps candidate values in sorted order while a window moves through a sequence. For window maxima, discard smaller or equal values from the back before appending a new value, and remove expired indices from the front. The maximum is always at the front. Each index enters and leaves at most once, so all windows can be processed in linear time.