Deque

A deque (pronounced “deck”) is a double-ended queue from the collections module. The critical difference from a list: appending or popping from either end is O(1), while a list’s insert(0, x) and pop(0) are O(n).

from collections import deque

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

Core operations

from collections import deque

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

# Append — O(1) on both ends
d.append(4)         # right: deque([1, 2, 3, 4])
d.appendleft(0)     # left:  deque([0, 1, 2, 3, 4])

# Pop — O(1) on both ends
d.pop()             # returns 4, deque([0, 1, 2, 3])
d.popleft()         # returns 0, deque([1, 2, 3])

# Extend
d.extend([4, 5])           # add multiple to right
d.extendleft([-2, -1])     # add multiple to left (each appended one at a time, so reversed)

# Rotate
d = deque([1, 2, 3, 4, 5])
d.rotate(2)         # deque([4, 5, 1, 2, 3]) — shift right by 2
d.rotate(-1)        # shift left by 1

maxlen — sliding window

Passing maxlen turns the deque into a fixed-size buffer: when it’s full, adding to one end automatically removes from the other.

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

Stack and Queue patterns

from collections import deque

# Stack (LIFO) — push and pop from the right
stack = deque()
stack.append("a")
stack.append("b")
stack.pop()         # "b"

# Queue (FIFO) — push right, pop left
queue = deque()
queue.append("first")
queue.append("second")
queue.popleft()     # "first"

Why not just use a list for queues?

list.pop(0) shifts every remaining element one position left — that is O(n). For a long-lived queue that processes many items, this adds up. deque.popleft() is always O(1).

Complexity comparison

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

The trade-off: random access by index (d[i]) is O(n) for a deque, because it is a doubly-linked list internally. Use a list when you need frequent indexing; use a deque when you need frequent appends or pops from the left.