Deques (Double-Ended Queues)

A deque (short for double-ended queue, pronounced deck) is a linear data structure that supports adding and removing elements from both the front and the back in constant time. It generalizes the stack (one open end, last-in-first-out) and the queue (first-in-first-out) into a single structure that lets you push and pop from either side. In Python you rarely build one from scratch — the standard library ships a highly optimized collections.deque — but understanding how it works, and why it beats a plain list for front-of-line operations, is essential for writing efficient queue-based algorithms like breadth-first search, sliding-window problems, and undo/redo stacks.

Overview: How a Deque Works

Think of a deque as a line of people where staff can be added or removed from either end — the front of the line or the back — without disturbing anyone in the middle. Compare that to a plain Python list, which is really a resizable array: appending to the right end is cheap (O(1) amortized) because there’s usually spare capacity there, but inserting or removing at the left end (list.insert(0, x) or list.pop(0)) is expensive because every remaining element has to shift over by one slot — an O(n) operation.

Python’s collections.deque solves this by using a different internal layout: instead of one contiguous block of memory, it’s implemented as a doubly linked list of fixed-size blocks (small arrays, typically 64 elements each). Adding or removing an element at either end only touches the block at that end and adjusts a couple of pointers — it never has to shift the rest of the sequence. That’s why both ends are O(1): append and pop work on the right end, appendleft and popleft work on the left end.

The tradeoff is that a deque gives up cheap random access. A list can jump straight to arr[500000] in O(1) because it’s one contiguous array with a known memory offset. A deque has to walk from whichever end is closer, block by block, to reach an arbitrary index, which makes dq[i] an O(n) operation in the worst case. In practice this rarely matters, because the entire point of reaching for a deque is that you only ever touch the two ends.

A deque also accepts an optional maxlen argument: deque(maxlen=5) creates a bounded deque that automatically discards an element from the opposite end whenever a new one would push it past capacity. This is extremely useful for “keep the last N items” patterns — a fixed-size sliding window, a recent-history buffer, a simple cache of recently seen keys — without writing any eviction logic yourself.

Because a deque supports O(1) operations at both ends, it can play three roles at once: a stack (use append/pop on one end only), a queue (use append on the right and popleft on the left), and a genuine double-ended structure (use both ends deliberately, as in the sliding-window and palindrome examples below).

Time and Space Complexity

All complexities below are in terms of n, the number of elements currently stored in the deque.

Operation	Complexity	Why
append(x) (add right)	O(1)	Writes into the current right-hand block; a new block is allocated only when the current one is full.
appendleft(x) (add left)	O(1)	Same as above, mirrored to the left-hand block. No shifting of existing elements.
pop() (remove right)	O(1)	Removes the last element of the right-hand block; the block is freed once empty.
popleft() (remove left)	O(1)	Mirror of pop() on the left-hand block.
dq[i] (indexing)	O(n) worst case	Must walk block by block from the nearer end; there’s no direct offset calculation like a contiguous array has.
x in dq (search)	O(n)	No hashing involved — a linear scan is required, same as searching a list.
dq.rotate(k)	O(k)	Moves k elements from one end to the other one at a time.
Space	O(n)	One slot per stored element, plus small fixed overhead per block.

Compare that to a plain list used as a queue: append is O(1) amortized, but pop(0) or insert(0, x) is O(n) because every remaining element must be copied one position over. If you enqueue and dequeue n items with a list, that’s O(n²) total work; with a deque it’s O(n) total — the difference that makes deque the correct choice for any queue-like workload.

Examples

Example 1: Basic operations on both ends

from collections import deque

def demo_basic_deque() -> None:
    dq: deque[int] = deque()
    dq.append(10)
    dq.append(20)
    dq.appendleft(5)
    dq.append(30)
    print("Deque after inserts:", list(dq))

    right_val = dq.pop()
    left_val = dq.popleft()
    print("Popped from right:", right_val)
    print("Popped from left:", left_val)
    print("Deque after pops:", list(dq))

demo_basic_deque()

Output:

Deque after inserts: [5, 10, 20, 30]
Popped from right: 30
Popped from left: 5
Deque after pops: [10, 20]

Walking through it: the deque starts empty. append(10) and append(20) add to the right, producing [10, 20]. appendleft(5) adds to the left, giving [5, 10, 20], and append(30) adds to the right again, giving [5, 10, 20, 30]. Then pop() removes and returns the rightmost value, 30, and popleft() removes and returns the leftmost value, 5, leaving [10, 20]. Every one of those six operations is O(1) regardless of how many elements were already in the deque.

Example 2: Sliding window maximum (a classic interview problem)

from collections import deque

def sliding_window_maximum(nums: list[int], window_size: int) -> list[int]:
    result: list[int] = []
    index_deque: deque[int] = deque()  # stores indices, values decreasing

    for current_index, current_value in enumerate(nums):
        # Remove indices that are outside the current window
        while index_deque and index_deque[0] <= current_index - window_size:
            index_deque.popleft()

        # Remove indices whose values are smaller than the current value
        while index_deque and nums[index_deque[-1]] < current_value:
            index_deque.pop()

        index_deque.append(current_index)

        if current_index >= window_size - 1:
            result.append(nums[index_deque[0]])

    return result

nums = [1, 3, -1, -3, 5, 3, 6, 7]
window_size = 3
print(sliding_window_maximum(nums, window_size))

Output:

[3, 3, 5, 5, 6, 7]

This is the pattern that makes deques indispensable in interviews: finding the maximum of every contiguous window of size window_size in a single O(n) pass. The trick is a monotonic deque that stores indices (not values) in strictly decreasing order of their corresponding values. Before adding the current index, the code pops off any indices from the back whose values are smaller than the current value, because those elements can never again be the maximum of any future window — the current, larger value will always outlast them. It also pops from the front whenever the oldest index has fallen outside the current window. Because the front of the deque is always the index of the largest value still inside the window, nums[index_deque[0]] is the window’s maximum, read off in O(1) once the window is full. See the step-by-step trace below for the exact sequence of pushes and pops.

Example 3: Palindrome check using both ends at once

from collections import deque

def is_palindrome(text: str) -> bool:
    cleaned = [character.lower() for character in text if character.isalnum()]
    char_deque: deque[str] = deque(cleaned)

    while len(char_deque) > 1:
        if char_deque.popleft() != char_deque.pop():
            return False

    return True

test_strings = ["Racecar", "A man, a plan, a canal: Panama", "hello"]
for text in test_strings:
    print(f"{text!r} -> {is_palindrome(text)}")

Output:

'Racecar' -> True
'A man, a plan, a canal: Panama' -> True
'hello' -> False

This uses the deque as a true double-ended structure: popleft() pulls the next character from the front while pop() pulls the next character from the back, and the two are compared. If they ever differ, the string can’t be a palindrome, so the function returns False immediately. If the two pointers meet or cross (the loop condition len(char_deque) > 1 stops when at most one character remains), every pair matched, so the string is a palindrome. Punctuation, spaces, and case are stripped out first with a list comprehension, which is why “A man, a plan, a canal: Panama” — a classic palindrome sentence — correctly returns True.

How It Works, Step by Step

Let’s trace the sliding-window-maximum algorithm from Example 2 by hand, using nums = [1, 3, -1, -3, 5, 3, 6, 7] and window_size = 3. The deque stores indices; “Action” describes what gets popped or pushed at each step.

i	nums[i]	Deque before	Action	Deque after	Window max
0	1	[]	push 0	[0]	—
1	3	[0]	nums[0]=1 < 3, pop 0; push 1	[1]	—
2	-1	[1]	no pops; push 2	[1, 2]	3
3	-3	[1, 2]	no pops; push 3	[1, 2, 3]	3
4	5	[1, 2, 3]	index 1 leaves window, popleft; pop 3, pop 2 (both < 5); push 4	[4]	5
5	3	[4]	3 < nums[4]=5, no pop; push 5	[4, 5]	5
6	6	[4, 5]	pop 5, pop 4 (both < 6); push 6	[6]	6
7	7	[6]	pop 6 (< 7); push 7	[7]	7

The window max column only starts once at least window_size elements have been seen (from i = 2 onward), matching the six values in the output: [3, 3, 5, 5, 6, 7]. Every index enters the deque exactly once and leaves at most once, whether by popleft (falling out of the window) or by pop (being outclassed by a larger value) — that amortized bound is why the whole algorithm is O(n) rather than the O(n × window_size) you’d get from recomputing the max of every window from scratch.

Common Mistakes

Mistake 1: Using a list as a queue

It’s tempting to reach for a plain list for a queue, since lists are the default sequence type. But removing from the front with list.pop(0) forces Python to shift every remaining element one slot to the left — an O(n) operation, called n times, which makes processing a queue of n items O(n²) overall.

def process_jobs_slow(jobs: list[str]) -> list[str]:
    queue = list(jobs)
    processed = []
    while queue:
        processed.append(queue.pop(0))  # O(n) per call: every remaining item shifts left
    return processed

print(process_jobs_slow(["job1", "job2", "job3"]))

Output:

['job1', 'job2', 'job3']

The output looks correct, and for small inputs the slowdown is invisible — that’s exactly what makes this mistake easy to miss until the queue grows large. Swap the list for a deque and call popleft() instead of pop(0); the observable behavior is identical, but every removal becomes O(1):

from collections import deque

def process_jobs_fast(jobs: list[str]) -> list[str]:
    queue: deque[str] = deque(jobs)
    processed = []
    while queue:
        processed.append(queue.popleft())  # O(1): no shifting required
    return processed

print(process_jobs_fast(["job1", "job2", "job3"]))

Output:

['job1', 'job2', 'job3']

Mistake 2: Mutating a deque while iterating over it

Just like a list, a deque tracks its own internal state during iteration, and changing its length inside a for loop leads to trouble. Unlike a list (which can silently skip elements), CPython’s deque detects the change and raises an error rather than returning a wrong answer silently:

from collections import deque

task_queue = deque(["email", "cleanup", "email", "report"])

for task in task_queue:
    if task == "email":
        task_queue.remove(task)  # mutates the deque while a for-loop iterator is active

print(task_queue)

Running this raises RuntimeError: deque mutated during iteration, because the call to task_queue.remove(task) changes the deque’s length while the for loop’s iterator is still walking it. The fix is to never mutate a container you’re iterating over directly — build a new one instead, typically with a generator expression or comprehension:

from collections import deque

def remove_all(task_queue: deque[str], target: str) -> deque[str]:
    filtered = deque(task for task in task_queue if task != target)
    return filtered

task_queue = deque(["email", "cleanup", "email", "report"])
task_queue = remove_all(task_queue, "email")
print(list(task_queue))

Output:

['cleanup', 'report']

Best Practices

• Reach for collections.deque whenever you need queue-like behavior (BFS, task scheduling, producer/consumer patterns) — never use a plain list with pop(0) or insert(0, x) for that purpose.
• Use the maxlen constructor argument for “keep only the last N” use cases (recent-history buffers, fixed-size sliding windows) instead of manually slicing or trimming a list after every insert.
• If your algorithm needs frequent random access (dq[i]) as well as fast ends, a deque is the wrong tool — reach for a list, or combine structures (e.g. a deque for order plus a dict for lookup).
• Never mutate a deque while iterating over it directly; build a filtered copy with a comprehension or generator expression instead.
• Use a deque as a stack too, if convenient — append/pop on the right end alone gives you LIFO behavior with the same O(1) guarantees as a list-based stack.
• A monotonic deque (storing indices in increasing or decreasing order of their values, as in Example 2) is the standard technique for “maximum/minimum of every sliding window” problems — recognize the pattern rather than re-deriving it under interview pressure.

Practice Exercises

1. Moving average. Implement a class MovingAverage(window_size: int) with a method next(value: float) -> float that returns the average of the last window_size values seen so far (fewer if not enough values have arrived yet). Use a deque(maxlen=window_size) so old values are evicted automatically. Hint: for window_size = 3 and calls next(1), next(10), next(3), next(5), the returned averages should be 1.0, 5.5, 4.666..., 6.0.
2. Sliding window minimum. Adapt Example 2’s monotonic deque to return the minimum of every window instead of the maximum. Which comparison operator has to flip?
3. Reverse the first k elements of a queue. Given a deque and an integer k, reverse the order of its first k elements while leaving the rest of the deque in its original order, using only deque operations (append, appendleft, pop, popleft) plus a temporary stack — no slicing. For deque([1, 2, 3, 4, 5]) and k = 3, the result should be deque([3, 2, 1, 4, 5]).

Summary

• A deque supports O(1) insertion and removal at both ends, unlike a list, whose front operations (insert(0, x), pop(0)) are O(n).
• Python’s collections.deque achieves this with a doubly linked list of fixed-size blocks internally, trading away O(1) random access (dq[i] is O(n)) for O(1) operations at the ends.
• A deque can act as a stack, a queue, or a genuine double-ended structure — the operations you use determine which.
• The maxlen parameter gives you a bounded, self-evicting deque for “keep the last N” patterns.
• The monotonic deque technique (Example 2) solves sliding-window maximum/minimum problems in O(n) total, versus O(n × window_size) for a naive re-scan of every window.
• Never mutate a deque while iterating it directly — build a new one with a comprehension instead.
• Space complexity is O(n) for n stored elements, same as a list.