The Deque

A stack operates at one end, while a queue inserts at the back and removes from the front. Some algorithms require insertion and removal at either end of the same sequence.

A double-ended queue, or deque, supports these operations.

A deque supports push_front, pop_front, push_back, and pop_back, all in O(1).

It makes no such promise about the middle. Two common implementations provide those four operations in very different ways.

One implementation extends a ring buffer by allowing both indices to move in either direction. push_back writes at the tail and advances it, while push_front decrements the head with wrap-around and then writes.

Pop operations update the corresponding index and read the selected value. These operations require no element shifting or allocation when capacity is available.

When the ring is full, the deque can allocate an array with twice the capacity and copy existing elements into one contiguous range.

The copy costs O(n), but geometric growth keeps the amortized cost of each push at O(1). Rust’s VecDeque uses this growable ring-buffer design.

C++ std::deque and Python collections.deque use multiple fixed-size blocks instead of one resizable array. A separate map stores pointers to the blocks in sequence order.

Growth at either end allocates another block and adds its pointer to the map. Existing elements remain in their current blocks, so growth does not copy the full sequence.

A monotonic deque can compute the maximum value in each sliding window in amortized O(1) time per step.

The deque stores indices in decreasing order of value. When a value enters, smaller values are removed from the back before the new index is added. Indices outside the window are removed from the front, leaving the current maximum at the front.

The Chase–Lev deque gives every worker thread its own task deque. The owning thread treats its bottom as a stack: push and pop there on the fast path, with no contention and no atomic read-modify-write in the common case.

Idle threads steal from the top instead — the opposite end from where the owner works — so the two sides only ever race when exactly one task remains. That single carefully-synchronized case is what makes the whole scheme safe without a lock on every operation.

Unlike a plain array, a deque can add or remove at the front without shifting every element. Unlike a linked list, it stores values in contiguous blocks and avoids one allocation per node.

Middle insertions and deletions remain O(n). A block-based deque also pays a pointer indirection whenever iteration crosses into the next block.

Python, C++, and Rust all expose deques directly. Work-stealing variants are used by schedulers in Go, Tokio, Rayon, and Java’s ForkJoinPool.

0-1 BFS pushes zero-weight edges to the front and one-weight edges to the back. Other applications include undo histories, browser navigation, and sliding-window analytics.

A deque may use a growable ring buffer or a collection of fixed-size blocks. Both implementations support constant-time insertion and removal at either end.

Insertion and removal in the middle remain linear-time operations.