The Deque: Fast at Both Ends, and the Monotonic Deque Trick Worth Memorizing

A deque ("deck," short for double-ended queue) lets you push and pop from both the front and the back in O(1). That sentence sounds boring. The implication is that it's simultaneously a queue and a stack, which is also fine but not why you're here.

You're here because of the monotonic deque: an invariant you slap on top of this structure that turns sliding window maximum from O(nk) to O(n). It shows up in more interview problems than you'd expect. Once you see the trick, recognizing where to apply it is the whole game. The code is twelve lines. The explanation is what trips people up.

When the interviewer asks "sliding window" and you try to remember which kind.

What's Actually in Memory

The Ring Buffer

Most implementations back a deque with a circular array. Two indices, head and tail, treat the underlying storage as if the ends wrap around. There's no real ring. It's just modular arithmetic doing the heavy lifting while the array sits there being perfectly rectangular.

The "ring" is arithmetic, not geometry. head and tail are just integers doing math.

Push to the back: write at tail, advance tail by one mod capacity. Push to the front: decrement head mod capacity, write there. No element shifts. The "ring" is just arithmetic.

When the buffer fills, allocate an array twice as large and copy everything. That resize costs O(n) at that instant, but between any two resizes you insert at least n/2 elements. The total copy work across n inserts is n/2 + n/4 + ... which sums to at most n. Amortized, push_front and push_back both cost O(1).

C++'s Segmented Map

std::deque doesn't use one big array. It allocates fixed-size chunks (typically 512 bytes each on libstdc++) and keeps a central map: a compact array of pointers to those chunks. Sounds like more indirection. It is. In exchange you get a guarantee that plain arrays cannot give you.

The central map is an array of pointers. Each pointer points to a fixed-size chunk. Two dereferences per random access, but still O(1).

Adding to the back fills the last chunk or appends a new chunk pointer to the right of the map. Adding to the front fills the first chunk from its right side, or prepends a new chunk pointer to the left. No existing elements are ever moved when you push to either end. That is a meaningful guarantee that vectors cannot match.

It also means pointers and references to existing elements remain valid across push_front and push_back. Iterators do not, because the map itself might reallocate.

Random access: compute the chunk index with i / chunk_size, then the intra-chunk position with i % chunk_size. Two pointer dereferences instead of one. It is still O(1), but with a higher constant factor than std::vector.

Python's Linked Blocks

collections.deque uses a doubly linked list of 64-element blocks. Each block is a small array. Push to the front: if the first block has room on its left side, place the element there. Otherwise, allocate a fresh block and prepend it to the list. O(1) worst case, not just amortized. No doubling. No copy. Python decided not to make you think about it.

Three blocks chained together. Push to either end without touching anything in the middle.

The cost: random access by index requires walking the linked list of blocks. O(n). For interview problems, you will almost never pay it.

The maxlen parameter wraps this into a fixed-size circular buffer, evicting from the opposite end when full.

Memory Layout Side by Side

Every End Operation Is O(1). Here's Why.

The amortized versus worst-case distinction rarely matters in an interview. Both give O(1) at both ends, and that is the property you use.

Why is push_front O(n) on a plain dynamic array? Every existing element shifts one position right to make room at index 0. The ring buffer sidesteps this: "front" is just a pointer that moves left with wrap-around. Nothing shifts. The cost disappears into arithmetic.

Why does the C++ segmented model keep O(1) for random access? You compute two integers: the chunk index and the intra-chunk position. Those are constant-time arithmetic operations followed by two pointer reads.

Implementations

from collections import deque
from typing import List

d: deque[int] = deque()
d.appendleft(10)     # push_front
d.append(20)         # push_back
front = d.popleft()  # pop_front -> 10
back = d.pop()       # pop_back  -> 20
d.appendleft(1)
d.append(2)
print(d[0], d[-1])   # peek front, peek back -> 1 2

# fixed-size circular buffer: evicts from opposite end when full
window: deque[int] = deque(maxlen=3)
for val in [1, 2, 3, 4]:
    window.append(val)  # [2, 3, 4] after all four

What Problems It Solves

Reach for a deque when the problem needs fast access at both ends, or when you're combining queue and stack behavior in the same structure.

Concrete use cases:

• FIFO queue (push_back only, pop_front only)
• LIFO stack (push_back only, pop_back only)
• Sliding window maximum or minimum
• 0-1 BFS: zero-cost edges go to the front, one-cost edges to the back
• Rate limiting: append timestamps to the back, evict expired ones from the front
• Palindrome checking: compare front and back simultaneously, shrink inward
• LRU-style eviction when both ends need to move

The one that trips up interview candidates is the monotonic deque. It is not a separate data structure. It is a deque plus an ordering invariant you enforce manually before each insertion.

Recognizing the Monotonic Deque Pattern

The clearest signal: "maximum" or "minimum" over every contiguous subarray of length k. See that phrasing, reach for a monotonic deque before even considering a heap. The deque gives O(n). A heap gives O(n log n). Brute force gives O(nk). Pick one.

The second signal: a DP recurrence of the form dp[i] = nums[i] + max(dp[j]) where j is constrained to a sliding window of size k. Naive DP is O(nk). A monotonic deque makes each step O(1).

How the Invariant Works

You store indices in the deque, not values. The values at those indices form a strictly decreasing sequence from front to back (for maximum). The front is always the index of the current window's maximum.

Two rules, applied before each push:

1. Pop from the front any index that has fallen outside the current window.
2. Pop from the back any index whose value is less than or equal to the incoming value.

Rule 2 is the key insight. If a new element is larger than some older element, that older element can never become a window maximum again. The newer element is larger and will remain in the window at least as long. The older element is permanently irrelevant. Evict it. No mercy.

Watch index 1 (value 3) get immediately evicted when 5 arrives at i=4. It never had a chance.

Example 1: Sliding Window Maximum (LeetCode 239)

from collections import deque
from typing import List

def sliding_window_maximum(nums: List[int], k: int) -> List[int]:
    dq: deque[int] = deque()  # indices, decreasing by corresponding value
    result: List[int] = []

    for i, num in enumerate(nums):
        # evict indices no longer in the window
        while dq and dq[0] <= i - k:
            dq.popleft()

        # maintain decreasing invariant
        while dq and nums[dq[-1]] <= num:
            dq.pop()

        dq.append(i)

        if i >= k - 1:
            result.append(nums[dq[0]])  # front is always the window max

    return result

Each index enters the deque exactly once and leaves exactly once. Total deque operations across the entire loop: at most 2n. Time complexity O(n), regardless of k. Space O(k) for the deque.

Example 2: Jump Game VI (LeetCode 1696)

Jump at most k steps forward through nums. Each landing position adds nums[i] to your score. Maximize your score reaching index n-1.

Recurrence: dp[i] = nums[i] + max(dp[j]) for j in [max(0, i-k), i-1].

from collections import deque
from typing import List

def max_result(nums: List[int], k: int) -> int:
    n = len(nums)
    dp = [0] * n
    dp[0] = nums[0]
    dq: deque[int] = deque([0])  # indices, decreasing by dp value

    for i in range(1, n):
        while dq and dq[0] < i - k:
            dq.popleft()

        dp[i] = nums[i] + dp[dq[0]]  # front holds the index with max dp value

        while dq and dp[dq[-1]] <= dp[i]:
            dq.pop()

        dq.append(i)

    return dp[n - 1]

The structure is identical to Example 1: deque of indices, decreasing by the value you care about, two eviction conditions. Once you know the shape, the pattern transfers directly to any sliding-window DP. The only variable is which value you track in the invariant.

When to Use a Deque vs. a Stack

If the problem says "within the previous k elements," you need a deque (the window constraint requires front eviction). If it says "next greater element" without a window, a stack is enough. The window is the differentiator.

Recap

• A deque gives O(1) amortized push and pop at both ends
• Circular buffers (Java, Kotlin, Rust, Swift, JS/TS) use a doubling resize strategy; total copy work across n inserts is at most 2n, giving O(1) amortized
• C++ std::deque uses a segmented map of fixed-size chunks; push_front and push_back never move existing elements; raw pointers into the structure survive end-only operations
• Python collections.deque is a doubly linked list of 64-element blocks; O(1) worst case at both ends, O(n) random access
• The monotonic deque adds a decreasing (or increasing) invariant to solve sliding window max/min in O(n)
• Store indices, not values, so you can check whether an element has exited the window
• Evict from the front when an index falls outside the window; evict from the back when a larger (or equal) element enters
• The pattern extends directly to DP recurrences of the form "best of the previous k positions"

If you want to rehearse the monotonic deque pattern out loud before your next interview, SpaceComplexity runs voice-based mock interviews with rubric-based feedback. The algorithm is short. Narrating the invariant while writing it under time pressure is where candidates separate themselves, and that is what the rubric catches.

For sliding window problems where k is variable rather than fixed, the two-pointer technique is usually the right move instead. The post on the sliding window algorithm covers that pattern side by side with the fixed-window variant. And if you find yourself going quiet when the invariant isn't obvious at the start, the post on staying vocal when you're stuck is worth reading before your next session.

Further Reading

• Double-ended queue, Wikipedia
• std::deque, cppreference.com
• collections.deque, Python 3 docs
• ArrayDeque, Java SE docs
• VecDeque, Rust std
• Deque data structure, GeeksforGeeks