Python deque: The Double-Ended Queue That Beats list for Queue Operations

A deque (pronounced “deck”) is a double-ended queue from the collections module. Unlike a list, which stores elements in a contiguous memory block, a deque uses a doubly-linked list of fixed-size blocks. That layout makes appending and popping from either end O(1), whereas list.pop(0) requires shifting every remaining element and costs O(n).

Basic Operations

from collections import deque

dq = deque([1, 2, 3])

# Append and pop from the right (same as list)
dq.append(4)           # deque([1, 2, 3, 4])
print(dq.pop())        # 4 — removes from right

# Append and pop from the left — O(1), unlike list
dq.appendleft(0)       # deque([0, 1, 2, 3])
print(dq.popleft())    # 0 — removes from left

print(dq)              # deque([1, 2, 3])

Using deque as a Queue (FIFO)

from collections import deque

task_queue = deque()

# Producers add to the right
task_queue.append("send_email")
task_queue.append("resize_image")
task_queue.append("update_cache")

# Workers consume from the left
while task_queue:
    task = task_queue.popleft()   # O(1) — not O(n) like list.pop(0)
    print(f"Processing: {task}")

# Output:
# Processing: send_email
# Processing: resize_image
# Processing: update_cache

This is the correct way to implement a queue in Python. Using a list with pop(0) is a common performance mistake.

Bounded deque with maxlen — Sliding Windows and Recent History

Setting maxlen creates a bounded deque. When the deque is full, adding to one end automatically drops the element from the other end.

from collections import deque

# Keep only the last 5 log entries
recent_logs = deque(maxlen=5)

for i in range(8):
    recent_logs.append(f"log_{i}")
    print(list(recent_logs))

# Final state: deque(['log_3', 'log_4', 'log_5', 'log_6', 'log_7'], maxlen=5)

This is cleaner than manually slicing a list every time you add an element.

Sliding Window Maximum (Classic deque Problem)

Find the maximum in each window of size k as it slides through an array. The deque stores indices in decreasing order of their values, keeping only indices within the current window.

from collections import deque

def sliding_window_max(arr, k):
    """
    Return the maximum of each subarray of size k.
    O(n) time using a monotonic deque.
    """
    result = []
    dq = deque()   # stores indices, front = index of current window's max

    for i in range(len(arr)):
        # Remove indices outside the current window
        while dq and dq[0] < i - k + 1:
            dq.popleft()

        # Remove indices whose values are smaller than arr[i]
        # (they can never be the maximum for any future window)
        while dq and arr[dq[-1]] < arr[i]:
            dq.pop()

        dq.append(i)

        # Start recording once the first full window is complete
        if i >= k - 1:
            result.append(arr[dq[0]])

    return result

arr = [1, 3, -1, -3, 5, 3, 6, 7]
print(sliding_window_max(arr, 3))
# Output: [3, 3, 5, 5, 6, 7]

A naive nested-loop solution would be O(n×k). The deque makes it O(n).

Rotating a deque

from collections import deque

dq = deque([1, 2, 3, 4, 5])

dq.rotate(2)    # rotate right by 2
print(dq)       # deque([4, 5, 1, 2, 3])

dq.rotate(-1)   # rotate left by 1
print(dq)       # deque([5, 1, 2, 3, 4])

Other Useful Methods

from collections import deque

dq = deque([3, 1, 4, 1, 5, 9, 2])

# Extend from either end
dq.extendleft([10, 20])   # adds 10 then 20 from left → [20, 10, 3, 1, 4, 1, 5, 9, 2]

# Count occurrences
print(dq.count(1))        # depends on current state

# Remove first occurrence of a value
dq.remove(9)

# Reverse in place
dq.reverse()

deque vs list Performance

Operation	list	deque
`append(x)`	O(1) amortised	O(1)
`pop()`	O(1)	O(1)
`appendleft(x)`	O(n)	O(1)
`popleft()`	O(n)	O(1)
Random access `[i]`	O(1)	O(n)

The trade-off: deque gives you fast ends, list gives you fast random access. Use deque when you are primarily adding/removing from the front, and list when you need to index by position.