A stack only ever touches one end of a sequence. A queue touches two ends, but each operation is dedicated to one of them — push goes in the back, pop comes out the front. Neither structure lets the same call site work either end.
Some algorithms need both ends of the same sequence, live, interchangeably: push or pop from the front just as cheaply as the back. That structure is a double-ended queue, or deque.
The deque interface is four operations: push_front, pop_front, push_back, pop_back. All four run in O(1).
Nothing in the contract mentions the middle of the sequence — inserting or removing an arbitrary interior element is not part of what a deque promises to do cheaply. Two implementations deliver on the contract in very different ways.
The first implementation is exactly the ring buffer, except both indices are allowed to move in both directions. push_back writes at the tail and advances it forward, same as a ring buffer's push. push_front moves the head backward first, then writes — and backward off slot 0 wraps to the last slot, exactly the same modular arithmetic as the forward wrap, walked in reverse.
Pop from either end is the mirror of push: move the index toward the other end, read the value it now points at. Every operation stays a single array write and a pointer increment or decrement — no shifting, no reallocation on the common path.
When the ring fills, growth works the same way a ring buffer grows: allocate a block of double the capacity and copy the existing elements out, straightened into a single contiguous run in the new array. The old wrap disappears; the new block starts clean.
The copy costs O(n), but it happens on a shrinking fraction of operations as the deque grows, so the amortized cost per push stays O(1). This is precisely how Rust's VecDeque is implemented — a growable ring buffer wearing a deque-shaped interface.
The second implementation, used by C++'s std::deque and Python's collections.deque, never resizes a single backing array at all. Instead it keeps many small fixed-size blocks, and a separate map — an array of pointers to blocks, in order.
Growing at either end allocates one new block and appends its pointer to the map; every element already stored stays exactly where it is, because no element ever moves between blocks. The cost of growth is one small allocation, not a copy of everything so far.
The deque's signature algorithm is the sliding-window maximum: given an array and a window size, report the max of every window as it slides across. A brute-force scan re-examines the whole window each step; a monotonic deque does it in amortized O(1) per step.
Keep indices in the deque in decreasing order of value. When a new value enters the window, pop every smaller value off the back first — they can never be the max again while this new, larger value is in play — then push the new index. Pop the front whenever it falls outside the window. The front of the deque is always the current window's maximum.
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.
Compared to a plain array or Vec, a deque adds front operations at O(1) instead of O(n) — no shifting every element down to make room at index 0. Compared to a linked list, both deque implementations keep elements in contiguous memory blocks, avoiding a per-node allocation and pointer chase for every element.
The cost is unchanged from either alternative: inserting or deleting in the middle is still O(n), and for the block-based implementation, iterating across a block boundary costs a pointer indirection the plain array never pays.
Standard libraries expose the deque directly: Python's collections.deque, C++'s std::deque, Rust's VecDeque. Work-stealing schedulers built on the Chase–Lev deque run underneath Go's goroutine scheduler, Tokio's async runtime, Rust's Rayon, and Java's ForkJoinPool.
0-1 BFS — shortest paths in a graph where every edge weighs 0 or 1 — pushes 0-weight edges to the front and 1-weight edges to the back of a deque, getting Dijkstra-quality results without a heap. Undo histories, browser back/forward stacks, and sliding-window analytics over streaming data all lean on the same two-ended shape.
One sequence, two ends that are both first-class. Underneath, either a ring that both indices can walk, or fixed blocks tied together by a map — the interface is identical either way.
Both doors cost O(1); the middle still costs O(n), always. The deque doesn't remove that cost — it just refuses to let the ends pay it.