Deques (Double-Ended Queues)

The mental model: a train with two doors

A regular queue is a train with one entrance (the back) and one exit (the front). A stack is a train where the entrance and exit are the same door at the back. A deque has doors at both ends — you can board or exit from either side, independently.

That sounds like a minor feature, but it unlocks a surprising number of algorithms. The deque's two extra operations — push-front and pop-back — are the difference between needing two separate data structures and needing one.

flowchart LR
    PF["push_front(x)"] -->|"O(1)"| H["HEAD ← [x] ↔ [3] ↔ [7] ↔ [12] ↔ [5] → TAIL"]
    H -->|"O(1)"| PB["push_back(y)"]
    H -->|"O(1)"| DLF["pop_front() → x"]
    H -->|"O(1)"| DLB["pop_back() → 5"]
    style H fill:#7c5cff,color:#fff
    style PF fill:#22d3ee,color:#0a0a0f
    style PB fill:#22d3ee,color:#0a0a0f
    style DLF fill:#00ff9d,color:#0a0a0f
    style DLB fill:#00ff9d,color:#0a0a0f

How it actually works: two implementations

Doubly linked list

The conceptually clean version. Each node holds a value and two pointers: one to the previous node, one to the next. The deque keeps two sentinel pointers — head and tail — and every operation touches only those two ends.

class Node:
    def __init__(self, val):
        self.val = val
        self.prev = None
        self.next = None

class Deque:
    def __init__(self):
        self.head = None
        self.tail = None
        self._size = 0

    def push_front(self, val):
        node = Node(val)
        if self.head is None:
            self.head = self.tail = node
        else:
            node.next = self.head
            self.head.prev = node
            self.head = node
        self._size += 1

    def push_back(self, val):
        node = Node(val)
        if self.tail is None:
            self.head = self.tail = node
        else:
            node.prev = self.tail
            self.tail.next = node
            self.tail = node
        self._size += 1

    def pop_front(self):
        if not self.head:
            raise IndexError("pop from empty deque")
        val = self.head.val
        self.head = self.head.next
        if self.head:
            self.head.prev = None
        else:
            self.tail = None
        self._size -= 1
        return val

    def pop_back(self):
        if not self.tail:
            raise IndexError("pop from empty deque")
        val = self.tail.val
        self.tail = self.tail.prev
        if self.tail:
            self.tail.next = None
        else:
            self.head = None
        self._size -= 1
        return val

Each operation is pure pointer surgery — three or four assignments, no matter how many elements are in the deque. No copying, no shifting.

The cost you pay: each node is a separate heap allocation, and those allocations are scattered across memory. Following node.next for a thousand nodes is following a thousand different pointers — the CPU's prefetcher can't predict where you're going, so you get a cache miss per hop. For sequential access, a doubly linked list is noticeably slower than an array even though Big-O says they're the same.

Circular buffer (ring buffer)

The cache-friendly version. Pre-allocate an array of size capacity. Track two indices: head (where the front element lives) and tail (the next empty slot at the back). All arithmetic is modular: (index + 1) % capacity wraps around, so the array appears circular.

   capacity = 8
   [ _, _, 3, 7, 12, 5, 9, _ ]
             ^              ^
            head           tail

Push back: write to tail, then tail = (tail + 1) % capacity.
Push front: head = (head - 1) % capacity, write there.
Pop front: read from head, then head = (head + 1) % capacity.
Pop back: tail = (tail - 1) % capacity, read there.

All four operations: one modular arithmetic step, one array write or read. No allocations, no pointer chasing. The data is contiguous in memory, which the CPU loves.

The trade-off: fixed capacity. When the buffer fills, you have to reallocate a larger array and copy — same story as a dynamic array. The amortized cost per operation remains O(1), but you take the hit periodically.

flowchart LR
    subgraph "Circular Buffer (capacity = 8)"
        direction LR
        I0["_"] --- I1["_"] --- I2["3"] --- I3["7"] --- I4["12"] --- I5["5"] --- I6["9"] --- I7["_"]
    end
    H["head = 2"] -.-> I2
    T["tail = 7"] -.-> I7
    style I2 fill:#7c5cff,color:#fff
    style I4 fill:#22d3ee,color:#0a0a0f
    style I6 fill:#00ff9d,color:#0a0a0f

Python's collections.deque is neither purely one nor the other. CPython implements it as a doubly-linked list of fixed-size blocks (each block holds ~64 elements). This hybrid keeps allocations rare (amortized like a dynamic array) while making sequential traversal within a block cache-friendly. The implementation detail is invisible from outside — you just get O(1) on both ends and reasonably good performance for sequential access.

Complexity at a glance

Operation	Doubly Linked List	Circular Buffer	Python collections.deque
push_front / push_back	O(1)	O(1) amortized	O(1) amortized
pop_front / pop_back	O(1)	O(1)	O(1)
peek front / peek back	O(1)	O(1)	O(1)
Access by index i	O(n)	O(1)*	O(n)
Memory layout	scattered	contiguous	block-linked

*Circular buffer supports O(1) index access since the data IS an array — buffer[(head + i) % capacity].

Using it in Python

from collections import deque

dq = deque([3, 7, 12, 5, 9])

dq.appendleft(0)    # push front → [0, 3, 7, 12, 5, 9]
dq.append(99)       # push back  → [0, 3, 7, 12, 5, 9, 99]

dq.popleft()        # pop front  → returns 0
dq.pop()            # pop back   → returns 99

dq[0]               # peek front → 3  (O(1) for ends, O(n) by index in general)
dq[-1]              # peek back  → 9

# Cap the size: automatically evicts oldest when full
limited = deque(maxlen=3)
for x in [1, 2, 3, 4, 5]:
    limited.append(x)
# limited == deque([3, 4, 5])

One thing that catches people: collections.deque supports indexing with dq[i], but accessing a middle element is O(n) — the library has to walk from the nearer end. If you write dq[500] in a hot loop you have a quiet O(n) hiding in there. Reach for a plain list if you need random access.

The maxlen parameter is legitimately useful for sliding-window work where you want automatic eviction of old items. Set it and forget it.

The killer use case: sliding window maximum

This is why you need to know deques even if you're never asked to implement one from scratch.

The problem: given an array nums and an integer k, return the maximum value in each contiguous window of size k as the window slides right.

nums = [1, 3, -1, -3, 5, 3, 6, 7],  k = 3

Window [1,  3, -1] → 3
Window [3, -1, -3] → 3
Window [-1, -3,  5] → 5
Window [-3,  5,  3] → 5
Window [5,   3,  6] → 6
Window [3,   6,  7] → 7

Brute force: for each of the n - k + 1 windows, scan k elements to find the max. O(nk) — fine for small k, miserable for k = n/2 on a million-element array.

The monotonic deque. Here's the insight: if element A is to the LEFT of element B and A ≤ B, then A can never be the maximum of any future window — because any window containing A also contains B, which is larger. A is useless. Throw it away.

So we maintain a deque of indices with the property that the corresponding values are strictly decreasing. When a new element arrives:

1. Evict from the back any indices whose values are ≤ the new element (they're useless, as above).
2. Push the new index to the back.
3. Evict from the front any index that's outside the current window (i - dq[0] >= k).
4. The front of the deque is always the index of the current window's maximum.

from collections import deque

def sliding_window_maximum(nums, k):
    dq = deque()   # stores indices, values are strictly decreasing
    result = []

    for i, val in enumerate(nums):
        # 1. evict from back: remove indices whose values are ≤ current
        while dq and nums[dq[-1]] <= val:
            dq.pop()                    # pop_back: this index is useless now

        # 2. push current index to back
        dq.append(i)

        # 3. evict from front: index is outside current window
        if dq[0] <= i - k:
            dq.popleft()               # pop_front: too old

        # 4. once we have a full window, record the max
        if i >= k - 1:
            result.append(nums[dq[0]])  # front is always the max

    return result

{ "type": "queue", "variant": "queue", "title": "Monotonic deque: decreasing index values", "data": [3, -1, -3, 5, 3, 6] }

Play with it — imagine each value in the visualizer is an index-value pair. When a big value enters from the right, smaller values ahead of it get evicted. The front always holds the current window's champion.

Complexity: Every index enters the deque exactly once and leaves exactly once. That is O(n) total across all operations, O(k) space for the deque at any moment.

This pattern — maintaining a monotonic deque to track window extrema — generalizes to minimum, and to any property you can maintain monotonically. It shows up in problems like "longest subarray with bounded max minus min," "jump game," and "constrained subsequence sum." Recognize the shape: I need the max (or min) of a sliding window, efficiently → monotonic deque.

The monotonic stack is a close cousin — when the "window" is not bounded by a fixed k but by a structural property (like the next-greater-element), you reach for that technique instead.

When the deque replaces both a stack and a queue

You occasionally hit algorithms that need both LIFO and FIFO behavior in the same structure. A good example: palindrome checking using a deque.

from collections import deque

def is_palindrome(s):
    dq = deque(s)
    while len(dq) > 1:
        if dq.popleft() != dq.pop():   # compare front and back
            return False
    return True

One data structure, two different removal points, zero overhead. Compare that to spinning up a separate stack and a queue and coordinating between them.

Another real scenario: 0-1 BFS (graph problems where edges have weight 0 or 1). Normal BFS uses a queue — all edges cost the same. Dijkstra uses a heap — edges have arbitrary weights. When edges are only 0 or 1, there is a trick: use a deque. Edges with cost 0 get pushed to the front (they don't change priority), and edges with cost 1 get pushed to the back (they do). The deque stays approximately sorted at O(1) per operation, much cheaper than a heap's O(log n).

from collections import deque

def bfs_0_1(graph, start, end):
    dist = {start: 0}
    dq = deque([start])

    while dq:
        node = dq.popleft()
        for neighbor, weight in graph[node]:
            new_dist = dist[node] + weight
            if neighbor not in dist or new_dist < dist[neighbor]:
                dist[neighbor] = new_dist
                if weight == 0:
                    dq.appendleft(neighbor)  # free edge: push front
                else:
                    dq.append(neighbor)       # cost edge: push back

    return dist.get(end, float('inf'))

This is a trick that is specifically not possible with a plain queue or a plain stack — you need both ends.

Three patterns, one recognizer

When you see one of these in a problem, think deque first:

Pattern	Tell	Technique
Sliding window extremum	"max/min of each window of size k"	Monotonic deque — O(n)
Bidirectional traversal	"compare from both ends," "palindrome," "symmetric"	Deque as queue + stack simultaneously
Prioritized BFS	"edge weight 0 or 1," "move to front if condition"	0-1 BFS with deque

Pitfalls

Using a list as a deque in Python. list.insert(0, x) and list.pop(0) are both O(n) because the whole list shifts. People write this constantly without realizing it. collections.deque is the fix — appendleft and popleft are O(1).

# BAD — O(n) for every front insert
queue = []
queue.insert(0, x)

# GOOD — O(1)
from collections import deque
queue = deque()
queue.appendleft(x)

Indexing a deque in a hot loop. dq[500] walks from the nearer end, O(n). If you find yourself writing dq[i] anywhere but dq[0] or dq[-1], you've chosen the wrong data structure. Convert to a list, or reconsider the design.

Forgetting to check the front index in the sliding window pattern. The monotonic deque eviction step at the back is intuitive. The front eviction step — checking whether the front index has gone stale — is easy to skip. Without it, you return the maximum of a larger window than intended. The condition is dq[0] <= i - k, not dq[0] < i - k.

Using maxlen and then assuming elements stick around. When a deque(maxlen=k) is full, append silently drops the leftmost element. That automatic eviction is exactly what you want for fixed-size windows — but if you didn't intend it, you just lost data with no error.

When NOT to use a deque

You need this	Use this instead
O(1) random access by index	Array / list
Always need the current minimum or maximum, inserts are non-windowed	Heap
Pure FIFO, never touch the front for non-FIFO reasons	Queue
Pure LIFO	Stack
Key-value lookup	Hash table

The deque is a specialised tool. When you only need one end, the simpler interface of a plain stack or queue communicates intent more clearly. Reach for a deque exactly when the algorithm is explicitly doing something at both ends — if you're honest with yourself, those moments are rarer than you'd think. When they do show up, the deque fits like a key in a lock.

The sliding window maximum is the canonical example that separates people who know deques from people who don't. If you understand the monotonic deque pattern — why smaller elements get evicted, why each element enters exactly once — you can apply it to a half-dozen variations on sight. That is the real payoff.