vault

Deque

13 min read

Deque

A deque (pronounced “deck”, short for double-ended queue) is a linear collection that supports insertion and removal at both ends in O(1). It is the strict generalization of both Stack (use one end) and Queue (use one end for input and the other for output): any deque can simulate either by ignoring half of its API. The two canonical implementations are the circular buffer (array-based, fast, fixed-capacity-or-amortized) and the doubly linked list of fixed-size blocks — which is exactly how Python’s collections.deque is built. Deques are the structural primitive behind the Monotonic Deque (sliding-window minimum/maximum), 01-BFS, and many “process from either end” algorithms; understanding them well is the key to recognizing when an O(n) solution is hiding behind a problem that looks like it needs O(n log n) heap work.

1. Intuition — A Restaurant Bar Where People Sit and Leave from Both Ends

Imagine the long bar at a busy restaurant. Patrons can take a seat at either end of the bar (whichever end has space first), and as patrons finish their meals, they get up from either end as well — whoever finishes first leaves first, regardless of where they’re sitting. Nobody enters or leaves from the middle (that would require everyone else to scoot, which is exactly the cost a contiguous array pays for pop(0)). The bar is a deque: you can append/pop at the right end and at the left end, all in O(1).

A second mental model: a railway maintenance car that holds tools, with hatches at both ends. As workers walk past, they can grab the most-recently-loaded tool from either end, or load a new tool at either end. The “both ends accessible” property is what distinguishes a deque from a Queue (only the front comes out, only the back goes in) or a Stack (only one end touched).

The deep reason a deque is the useful generalization: in many algorithms (especially sliding-window patterns), you want to peek and possibly remove from one end while inserting at the other end. That bidirectional churn is exactly what a deque is built for. Trying to do it with a stack pair or a circular array hand-rolled in your problem solution costs implementation time and creates bugs; reaching for the language’s deque saves both.

2. Tiny Worked Example — Palindrome Check via Deque

Decide whether "racecar" is a palindrome by repeatedly comparing the front and back of a deque, removing both if they match.

StepDeque (front→back)Action
0r a c e c a rcompare ‘r’ (front) vs ‘r’ (back) → match, pop both
1a c e c acompare ‘a’ vs ‘a’ → match, pop both
2c e ccompare ‘c’ vs ‘c’ → match, pop both
3elength ≤ 1, palindrome confirmed
from collections import deque
 
def is_palindrome(s: str) -> bool:
    dq = deque(s)
    while len(dq) > 1:
        if dq.popleft() != dq.pop():
            return False
    return True

Each operation — popleft, pop — is O(1). Total O(n). The same problem is also solvable with Two Pointers in O(1) extra space (just two indices into the original string), so this isn’t a problem you’d actually use a deque for in production; it’s a clear illustration of “remove from both ends” semantics.

A more realistic motivating problem appears in §7: the Monotonic Deque for sliding-window maximum, where deque semantics are not substitutable.

3. Pseudocode

Deque ADT:
    push_front(x):      insert x at the front           O(1)
    push_back(x):       insert x at the back            O(1)
    pop_front():        remove and return front         O(1)
    pop_back():         remove and return back          O(1)
    peek_front():       return front without removing   O(1)
    peek_back():        return back without removing    O(1)
    is_empty():         true iff size == 0              O(1)
    size():             number of elements              O(1)

Some libraries (Python’s collections.deque, Java’s ArrayDeque) expose this as appendleft/append/popleft/pop. The naming is library-specific; the contract is the same.

4. Python — collections.deque Is the Whole Game

from collections import deque
 
dq: deque[int] = deque()
dq.append(3)         # push back
dq.append(7)
dq.appendleft(1)     # push front  → now [1, 3, 7]
front = dq[0]        # 1
back = dq[-1]        # 7
x = dq.popleft()     # 1, dq = [3, 7]
y = dq.pop()         # 7, dq = [3]

Both append and appendleft are O(1); both pop and popleft are O(1). The CPython implementation is in Modules/_collectionsmodule.c and uses a doubly-linked list of blocks, where each block is a fixed-size array (typically 64 elements). Inserting at the front amounts to writing into the leftmost block; if the leftmost block is full, a new block is allocated and prepended. The structure is:

  ┌──────────┐    ┌──────────┐    ┌──────────┐
  │ block 1  │ ←→ │ block 2  │ ←→ │ block 3  │
  │ [..,a,b] │    │ [c,...,d]│    │ [e,f,...]│
  └──────────┘    └──────────┘    └──────────┘

Within each block, elements are densely packed; across blocks, links are followed. This gives deque better cache locality than a pure linked-list deque (which would have one allocation per element) while preserving true O(1) on both ends. Random indexing dq[i] for general i is O(n) — the implementation must walk block-by-block, which the official docs explicitly warn about.

A bounded variant deque(maxlen=k) discards the opposite-end element when capacity is exceeded — useful for fixed-size sliding windows where you don’t need to read what falls off (the deque does it automatically).

window = deque(maxlen=3)
for x in [1, 2, 3, 4, 5]:
    window.append(x)
    print(list(window))
# [1]
# [1, 2]
# [1, 2, 3]
# [2, 3, 4]   ← '1' silently dropped
# [3, 4, 5]

Because it’s significantly faster than a list for queue/deque operations — list.pop(0) is O(n) per call, while deque.popleft() is O(1) — deque is the right choice for any use case where elements come and go at the front. See Queue §7.1 for the exact cost comparison.

5. Implementations Under the Hood

5.1 Doubly-Linked List of Blocks (Python’s choice)

Sketched above. Each block is a T[BLOCKLEN] array; blocks are linked in a doubly-linked list so adjacent blocks can be reached in O(1). Internal leftindex and rightindex cursors mark where the live elements start/end within the leftmost and rightmost blocks.

Pros. True O(1) on both ends, no amortization required. Pointer stability for elements within a block (across operations that don’t migrate that block). Memory is allocated incrementally — a small deque uses a single block, big deques allocate as needed.

Cons. Pointer chasing across block boundaries — one cache miss per block crossed when iterating. Random access is O(n / BLOCKLEN) which is O(n) asymptotically, slower than a single contiguous array’s O(1).

5.2 Circular Buffer (Java’s ArrayDeque)

ArrayDeque uses a single power-of-two-sized array with head and tail indices that wrap modulo capacity (the same structure as a Queue §5.1 circular buffer, but with operations exposed at both ends). The power-of-two capacity makes modulo % capacity reduce to a bitwise & (capacity - 1), which is one of the reasons ArrayDeque is the recommended Java stack/queue/deque.

Pros. Single contiguous allocation → maximal cache locality. Random access is O(1) (just buf[(head + i) & (cap - 1)]).

Cons. Growth is amortized O(1) but with rare O(n) spikes when the buffer doubles. The circular indexing logic is subtler than it looks (off-by-one on the head/tail wrap is a popular bug). Not suitable when pointer/iterator stability is needed across resizes.

5.3 Doubly Linked List

A textbook deque is a Doubly Linked List with sentinel nodes at both ends. Each operation amounts to splicing a node in or out at one end — O(1) worst-case.

Pros. Simplest to reason about. Pointer stability for any node across all operations (a reference handed to a caller stays valid forever).

Cons. One allocation per element. Cache locality is essentially zero — adjacent nodes can be anywhere in the heap. In practice, doubly-linked-list deques are 5–20× slower per operation than circular-buffer or block-list deques in modern memory hierarchies. Only use this when pointer stability is required (e.g., LRU cache pointers, see Least Recently Used Cache).

5.4 Comparison Table

Implementationenq/deq either endRandom accessCache localityPointer stability
Block list (Python deque)O(1)O(n)Good (per block)Within block
Circular buffer (Java ArrayDeque, C++ deque)O(1) amortizedO(1)ExcellentNone (resize copies)
Doubly linked listO(1)O(n)PoorPermanent

6. Complexity

OperationComplexity (any standard impl)
push_front, push_backO(1) (amortized for circular-buffer growth)
pop_front, pop_backO(1)
peek_front, peek_backO(1)
Random access dq[i]O(1) for circular buffer, O(n) for block list / linked list
IterationO(n) total
is_empty, sizeO(1)

Space: O(n). Block-list and circular-buffer overheads are small per element; linked-list deque pays the per-node header tax.

7. Use Cases

7.1 Monotonic Deque — Sliding-Window Min/Max

The single most-cited interview use of a deque: solving sliding-window maximum (LeetCode 239) in O(n) instead of the heap-based O(n log k). The deque holds indices in monotonic decreasing order of their values; the front is always the current window’s max. See the dedicated Monotonic Deque note for the full algorithm.

7.2 0-1 BFS — Edges of Weight 0 or 1

A graph BFS variant where edges are either weight 0 (relax: push to front) or weight 1 (relax: push to back). The deque imposes a partial order on the frontier that is equivalent to running Dijkstra’s Algorithm on a 0/1-weighted graph — but in O(V + E) instead of O((V + E) log V). See 01-BFS for the dedicated treatment. The deque is essential here because Dijkstra’s heap-based ordering is overkill when there are only two distinct edge weights; a simple front/back insertion mimics the heap’s effect for free.

7.3 Generalized Stack/Queue

If you need both stack and queue behavior in the same data structure (rare but real), use one deque rather than maintaining two collections.

7.4 Sliding Window of Last K Items

deque(maxlen=k) automatically discards old items as new ones are appended — perfect for “running average over last k samples,” “last k log lines,” etc.

7.5 LRU Cache Eviction Order

A Least Recently Used (LRU) Cache uses a Doubly Linked List (a deque, technically) of access-order keys plus a hash map from key → node. Touching a key moves its node to one end (most-recently-used); evicting drops the node from the other end. The pointer stability of the linked-list version is what makes the O(1) move-to-end work. See Least Recently Used Cache.

7.6 Undo/Redo with Bounded History

When you want undo/redo (a Stack use case) but capped at the last K operations, a deque(maxlen=K) automatically forgets the oldest operation when a new one is recorded — a stack with eviction.

7.7 Palindrome Check, Word Reversal, Other Symmetric Algorithms

Anywhere you process from both ends inward (or write to both ends outward — building a string by interleaving prefix and suffix characters), a deque is the natural primitive.

8. Pitfalls

8.1 Random Access on a Deque

deque[i] for i away from the ends is O(n). If your algorithm needs random access and O(1) end operations, you can’t use Python’s deque directly — you need a circular-buffer-backed deque (Java ArrayDeque-style) or a different structure entirely.

8.2 Confusing appendleft with append

append(x) inserts at the back; appendleft(x) at the front. Same with pop (back) vs popleft (front). Mixing them up is a silent correctness bug, since both still preserve some ordering — it’s just the wrong one.

8.3 Iterating While Mutating

for x in dq:
    if predicate(x):
        dq.popleft()      # ← mutating during iteration

Like all containers, this is undefined behavior. Drain into a list first or rebuild the deque.

8.4 maxlen Silent Truncation

deque(maxlen=3) will silently discard the opposite end when full. If you need to see the discarded element (e.g., to update a running aggregate), you must read it before append, not after.

8.5 Slicing a Deque

dq[i:j] raises TypeError in CPython — deque does not implement slicing, even though it implements indexing. To slice, convert to a list first: list(dq)[i:j]. The conversion is O(n).

8.6 Thread Safety

collections.deque’s append, appendleft, pop, popleft are documented as thread-safe for individual calls (they hold the GIL atomically), but compound operations (if dq: dq.popleft()) are not — between the check and the pop, another thread could empty it. Use queue.Queue for thread-safe FIFO, or wrap a deque with a lock for thread-safe LIFO/deque semantics.

8.7 Forgetting That deque Is a Strict Generalization

If you only need stack OR queue semantics, both work fine on a deque, but for stacks specifically, a list (with append/pop) is slightly faster because it has lower per-operation overhead — no doubly-linked-block bookkeeping. For queues, deque is mandatory; for stacks, deque is fine but list is the default.

9. Diagram — Block-List Deque Structure

flowchart LR
    subgraph blocks["doubly-linked list of blocks"]
        B1["block A\n[ _ , _ , 'a', 'b']"]
        B2["block B\n['c', 'd', 'e', 'f']"]
        B3["block C\n['g', 'h', _ , _ ]"]
        B1 <--> B2 <--> B3
    end
    LP["leftindex = 2\n(points at 'a' in block A)"] --> B1
    RP["rightindex = 1\n(points at 'h' in block C)"] --> B3

What this diagram shows. A snapshot of CPython’s deque internal layout for the logical sequence ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h']. Three fixed-size blocks (4 cells each, in this example — the real CPython value is 64) are linked in a doubly-linked list. The leftindex cursor points to the first live cell in the leftmost block (skipping the two empty leading slots), and rightindex points to the last live cell in the rightmost block. appendleft writes at index leftindex - 1; if leftindex would go below 0, a new block is allocated and prepended. append writes at rightindex + 1 symmetrically. The block layout is what gives Python’s deque its O(1) on both ends and better cache behavior than a per-element doubly-linked list — most operations stay within a single block, and only block-boundary crossings incur a pointer chase.

10. Common Interview Problems

#ProblemDeque Role
LC 239Sliding Window MaximumMonotonic Deque
LC 862Shortest Subarray with Sum at Least KMonotonic deque on prefix sums
LC 1696Jump Game VIMonotonic deque DP optimization
LC 1438Longest Subarray with Abs Diff ≤ LimitTwo monotonic deques (min and max)
LC 933Number of Recent CallsSliding-time-window deque
LC 622 / 641Design Circular Queue / DequeImplementation problems
LC 1700Number of Students Unable to Eat LunchQueue/deque simulation
LC 281Zigzag IteratorTwo deques alternated
LC 0-1 BFSVarious graph problems with weight ∈ {0,1}01-BFS

11. Open Questions

  • Are there persistent (immutable) deques with O(1) operations? Okasaki’s Purely Functional Data Structures presents real-time deques with O(1) worst-case in a persistent setting via lazy evaluation; how do these perform in strict languages?
  • Lock-free MPMC deque algorithms (e.g., Michael’s hazard-pointer deque) — when do they pay off vs lock-based deques in practice?
  • Why is CPython’s deque block size 64? Empirical tuning is the suspected answer, but I haven’t verified the rationale in the CPython source comments.

12. See Also

Graph View

Backlinks