The Deque (Double-Ended Queue)

Why the deque matters

The stack and the queue are the two most-taught container abstractions, and they are duals: a stack is last-in-first-out, a queue is first-in-first-out. Each restricts you to a single end. The deque lifts that restriction. Once both ends are cheap, a whole family of algorithms that need to look at, add, or discard elements from either boundary of a window becomes clean and asymptotically optimal.

Concretely, three high-value patterns depend on a deque:

• Sliding-window extrema in O(n). The monotonic deque answers "maximum (or minimum) of every length-k window" in a single linear pass instead of the naive O(n·k) or the O(n log k) balanced-tree/heap approach.
• Work-stealing parallelism. Modern task schedulers give each worker a private deque of runnable tasks. The owner runs it as a stack; idle thieves steal from the far end. This is the load-balancing engine behind Cilk, Java's ForkJoinPool, Rust's Rayon, and the Go runtime.
• 0-1 BFS. On a graph whose edges cost 0 or 1, Dijkstra collapses to a deque scan: relax a 0-edge and push_front; relax a 1-edge and push_back. The deque stays sorted by distance for free, giving O(V + E) instead of O((V + E) log V).

How a deque works

A deque exposes four core mutators and two peeks:

• push_front(x) / push_back(x) — insert at either end.
• pop_front() / pop_back() — remove and return either end.
• front() / back() — inspect either end without removing.

The interface is trivial; the interest is entirely in the layout that makes all four mutators O(1). There are two dominant strategies.

1. Doubly linked list

Each element is a node with a prev and a next pointer, and the deque holds a head and a tail pointer. Every operation splices a node at head or tail — a couple of pointer writes, genuinely worst-case O(1), never a shift or a copy. The cost is memory and cache behavior: two pointers of overhead per element, a separate heap allocation per node, and elements scattered across the heap so that iteration constantly misses the CPU cache. Random access by index is O(n) because you must walk the chain.

2. Ring buffer (circular array)

Store elements in a fixed-capacity array with two indices, head and tail, advanced modulo the capacity so the logical sequence can wrap around the physical end of the array. push_back writes at tail and steps tail forward; push_front steps head backward and writes there. When the buffer fills, it doubles its capacity and copies the elements into a fresh, un-wrapped array. That copy makes growth O(n), but it happens rarely enough that the amortized cost per push stays O(1). Random access is O(1): element i lives at (head + i) mod capacity. If the capacity is a power of two, that modulo becomes a single bitwise & (capacity - 1). This is what Rust's VecDeque and Java's ArrayDeque use.

3. Block map — the std::deque design

C++'s std::deque is a hybrid. Elements live in fixed-size chunks (implementation-defined, often 512 bytes or a small element count). A central map — itself a small array of pointers to chunks — tracks the chunks in order. To push at either end you either write into the current end chunk or, if it is full, allocate a new chunk and record its pointer in the map (growing the map occasionally). This gives amortized O(1) at both ends, O(1) indexing (two divisions to find chunk and offset), and a valuable guarantee the ring buffer lacks: inserting at either end never invalidates references or pointers to existing elements — only iterators are invalidated. The trade-off is that memory is not contiguous across chunks, so &d[0] is not a flat buffer of d.size() elements.

Deque vs stack vs queue vs vector

	Deque	Stack	Queue	Dynamic array (vector)
Push/pop back	O(1) amortized	O(1) amortized	O(1) amortized	O(1) amortized
Push/pop front	O(1) amortized	—	pop O(1)	O(n) (shift)
Random access [i]	O(1) array-backed	top only	ends only	O(1)
Contiguous memory	No (chunked/wrapped)	Yes (if array-backed)	No	Yes
Access discipline	Both ends (LIFO+FIFO)	LIFO, one end	FIFO, two ends	Any index
Implements the others?	Yes — is a superset	Subset of deque	Subset of deque	Superset by index, not by end

The row that captures the point: a deque is a strict superset of both the stack and the queue, which is exactly why the C++ standard library defaults std::stack and std::queue to adapt over a std::deque, and why Java's docs recommend ArrayDeque over the legacy Stack class.

Implementation: a power-of-two ring-buffer deque

Here is a compact, correct ring-buffer deque in Python. Capacity is kept a power of two so index arithmetic is a bitmask, and the buffer doubles on overflow.

class RingDeque:
    def __init__(self, cap=8):
        self._buf = [None] * cap          # cap must be a power of two
        self._mask = cap - 1              # index & mask == index % cap
        self._head = 0                    # index of current front element
        self._size = 0

    def __len__(self):
        return self._size

    def _grow(self):
        cap = len(self._buf)
        new = [None] * (cap * 2)
        # copy in logical order, un-wrapping the ring
        for i in range(self._size):
            new[i] = self._buf[(self._head + i) & self._mask]
        self._buf = new
        self._mask = cap * 2 - 1
        self._head = 0

    def push_back(self, x):
        if self._size == len(self._buf):
            self._grow()
        tail = (self._head + self._size) & self._mask
        self._buf[tail] = x
        self._size += 1

    def push_front(self, x):
        if self._size == len(self._buf):
            self._grow()
        self._head = (self._head - 1) & self._mask
        self._buf[self._head] = x
        self._size += 1

    def pop_front(self):
        if self._size == 0:
            raise IndexError("pop from empty deque")
        x = self._buf[self._head]
        self._buf[self._head] = None      # release reference
        self._head = (self._head + 1) & self._mask
        self._size -= 1
        return x

    def pop_back(self):
        if self._size == 0:
            raise IndexError("pop from empty deque")
        tail = (self._head + self._size - 1) & self._mask
        x = self._buf[tail]
        self._buf[tail] = None
        self._size -= 1
        return x

    def __getitem__(self, i):             # O(1) random access
        if not 0 <= i < self._size:
            raise IndexError(i)
        return self._buf[(self._head + i) & self._mask]

Note the two subtleties that trip people up: growth must copy in logical order (un-wrapping the ring, not memcpy-ing the raw array, or a wrapped deque comes out scrambled), and push_front decrements head with a masked subtraction so that -1 wraps to the last physical slot.

Worked example: sliding window maximum in O(n)

The canonical showcase for a deque is LeetCode 239, "Sliding Window Maximum": given an array and a window size k, report the maximum of every contiguous length-k window. The elegant solution stores indices in a deque, maintaining the invariant that the values at those indices are strictly decreasing from front to back.

from collections import deque

def max_sliding_window(nums, k):
    dq = deque()          # holds indices; nums[dq] is decreasing
    out = []
    for i, x in enumerate(nums):
        # 1. drop indices that fell out of the window on the left
        if dq and dq[0] <= i - k:
            dq.popleft()
        # 2. drop back indices whose value can never be the max again
        while dq and nums[dq[-1]] <= x:
            dq.pop()
        # 3. this index is a candidate
        dq.append(i)
        # 4. once the first full window is formed, the front is the max
        if i >= k - 1:
            out.append(nums[dq[0]])
    return out

Why it is O(n): every index is append-ed exactly once and pop-ped at most once, so across the whole scan there are at most 2n deque operations regardless of k. Step 2 is the crux — when a new element arrives that is at least as large as the back of the deque, those smaller, older elements are dominated: they can never be a future window's maximum while this larger, more-recent element is still in the window, so we discard them. The front of the deque is therefore always the index of the current window's maximum. Swap the two comparisons and you get the sliding-window minimum.

Worked example: work-stealing deque

Fork-join parallel runtimes give each worker thread its own deque of tasks. The owner treats it as a stack — it pushes freshly-spawned child tasks and pops from the same (bottom) end. This LIFO order is deliberate: the most recently spawned task is the hottest in cache and usually the largest remaining chunk of work. When a worker runs dry, it becomes a thief and steals a task from the top (the opposite end) of some other worker's deque — an old, coarse-grained task that is likely to spawn plenty of further work.

Because the owner and the thieves touch opposite ends, they almost never collide. The famous Chase-Lev lock-free deque exploits this: the owner's push and pop need no atomic operation on the common (non-empty, uncontended) path, and only the rare owner-vs-thief race over the last element requires a compare-and-swap. That is the load balancer inside Cilk, Intel TBB, Java's ForkJoinPool, and Rust's Rayon.

Common misconceptions and pitfalls

• "A deque is always contiguous like a vector." False for std::deque (chunked) and misleading for a ring buffer (logically contiguous, physically wrapped). You cannot hand either to a C API expecting a flat pointer.
• "O(1) at both ends means worst-case O(1)." Only for the linked-list implementation. Array-backed deques are amortized O(1): an individual push that triggers a doubling reallocation is O(n). If you need a hard real-time worst-case bound, that reallocation spike matters.
• "I can index into a linked-list deque cheaply." No — deque[i] is O(n) for Python's collections.deque (a linked list of blocks); it is O(1) only for array-backed deques like Rust's VecDeque.
• "Growth is free amortized, so I never pay for it." You pay in latency variance. High-throughput and low-latency systems often pre-size the ring buffer to avoid the copy entirely.
• "Iterators survive end insertions in every deque." In std::deque, inserting at an end preserves references and pointers to existing elements but still invalidates iterators; inserting in the middle invalidates everything. Read your standard-library's invalidation rules before you rely on them.

A note on origins

The double-ended queue is old enough that it predates most named algorithms that use it; the term and the abstraction were already standard in Donald Knuth's The Art of Computer Programming (Volume 1, 1968), where he catalogs the deque alongside the stack and the queue and distinguishes the "output-restricted" and "input-restricted" variants. The work-stealing deque was formalized by Blumofe and Leiserson's analysis of the Cilk scheduler in the mid-1990s, and the practical lock-free version by David Chase and Yossi Lev in 2005. The monotonic-deque sliding-window trick is competitive-programming folklore that every serious library now ships as a one-liner primitive.