Skip to content

Python deque: Double-Ended Queue from collections

  • The difference between list and deque and why list.pop(0) is a performance trap.
  • How append, appendleft, pop, and popleft give O(1) operations at both ends.
  • How maxlen creates a self-evicting bounded buffer for sliding windows and recent history.
  • How rotate repositions elements in place without re-sorting, for round-robin and circular use.
  • When deque is the wrong choice and a plain list (or set or heapq) is better.

collections.deque (pronounced “deck”) is a double-ended queue. It looks like a list but is engineered for fast adds and removals at both the front and the back. A regular list is only cheap to grow at the end; inserting or removing at the front costs O(n) because every remaining element has to shift. A deque keeps both ends at O(1) by storing elements in a doubly-linked chain of fixed-size blocks rather than one contiguous array.

The tradeoff is in the middle: indexed access into a deque is O(n), and slicing is not supported. Use a deque when your access pattern is at the ends — queues, stacks, sliding windows, and breadth-first search frontiers. Use a list when you need random access by index or slicing.

The natural way to build a FIFO queue in Python is a list with append to enqueue and pop(0) to dequeue. It reads fine and works on small inputs, but pop(0) is O(n): removing the first element forces every other element to move one slot left. On a queue of a million orders, each dequeue shifts nearly a million pointers. The same problem hits insert(0, x) for pushing to the front. The result is code that is correct but quietly quadratic — it passes tests and then degrades under load.

deque exists to make both ends cheap. append and pop operate on the right end in O(1); appendleft and popleft operate on the left end in O(1). None of them shift the other elements. For the canonical queue, stack, and BFS patterns, this is the data structure that matches the operation pattern.

A second problem deque solves is bounded history. “Keep the last N events” is a common need — recent orders viewed by an agent, a rolling window of order amounts, a live tail of audit log lines. With a list you manage the cap yourself: append, then check len, then pop(0) when over. deque(maxlen=N) does this automatically, evicting the oldest item from the opposite end the moment a new item would exceed the cap. The buffer physically cannot leak past its limit.

A deque is a sequence. You build it from any iterable, and optionally cap it with maxlen.

from collections import deque
d = deque() # empty
d = deque([1, 2, 3]) # from an iterable
d = deque(maxlen=3) # bounded, starts empty

The four end operations are all O(1):

from collections import deque
q = deque([1, 2, 3])
q.append(4) # deque([1, 2, 3, 4])
q.appendleft(0) # deque([0, 1, 2, 3, 4])
q.pop() # 4 -> deque([0, 1, 2, 3])
q.popleft() # 0 -> deque([1, 2, 3])

maxlen auto-evicts from the opposite end:

recent = deque(maxlen=3)
for i in range(5):
recent.append(i)
# deque([2, 3, 4], maxlen=3) -- 0 and 1 silently dropped

rotate(n) shifts elements n steps right (negative for left), in place:

d = deque([1, 2, 3, 4, 5])
d.rotate(2) # deque([4, 5, 1, 2, 3])
d.rotate(-1) # deque([5, 1, 2, 3, 4])

Result shape and edge cases worth remembering:

  • pop() and popleft() on an empty deque raise IndexError.
  • extendleft([1, 2, 3]) reverses the input: it calls appendleft once per element, so the last input element ends up leftmost, giving deque([3, 2, 1, ...]).
  • Indexed access d[500] is O(n); there is no slicing — d[1:3] raises TypeError. Convert with list(d) first if you need a slice.
  • A bounded deque silently drops on overflow; nothing raises, which is both its power and a footgun if you expected an error.
  • In CPython, individual append/pop/appendleft/popleft calls are atomic, so a deque is safe to use as a simple producer/consumer queue across threads without an explicit lock for the operations themselves (it is not a substitute for full coordination, covered below).

OrdersPortal is an order management system. A support agent dashboard needs three things at once: a work queue of orders to process in arrival order (FIFO), a “recently viewed orders” strip capped at five entries, and a rolling ten-order moving average of order amounts. All three map cleanly onto deque.

from collections import deque
class OrderDesk:
def __init__(self):
self._queue = deque() # FIFO work queue
self._recent = deque(maxlen=5) # bounded recent-views strip
self._amounts = deque(maxlen=10) # rolling window for the average
def enqueue(self, order_id, amount):
self._queue.append((order_id, amount))
def next_order(self):
if not self._queue:
raise IndexError("no orders in the queue")
return self._queue.popleft() # O(1) dequeue
def mark_viewed(self, order_id):
self._recent.append(order_id) # oldest auto-evicted once at 5
def record_amount(self, amount):
self._amounts.append(amount)
def average_amount(self):
if not self._amounts:
return 0.0
return sum(self._amounts) / len(self._amounts)

Driving it:

desk = OrderDesk()
desk.enqueue("ORD-1001", 250.00)
desk.enqueue("ORD-1002", 80.50)
desk.enqueue("ORD-1003", 399.99)
order_id, amount = desk.next_order() # ("ORD-1001", 250.00)
desk.record_amount(amount)
for oid in ["ORD-1001", "ORD-1002", "ORD-1003", "ORD-1004", "ORD-1005", "ORD-1006"]:
desk.mark_viewed(oid)
print(list(desk._recent))
# ['ORD-1002', 'ORD-1003', 'ORD-1004', 'ORD-1005', 'ORD-1006']

Note that six mark_viewed calls leave exactly five entries — the oldest two dropped automatically, with no manual trimming code.

deque is also the correct structure for breadth-first traversal. OrdersPortal models an order’s lifecycle as a dependency graph — shipping depends on fulfillment, fulfillment depends on payment — and BFS walks it cleanly:

from collections import deque
# stage -> stages it unblocks
graph = {
"payment": ["fulfillment"],
"fulfillment": ["shipping"],
"shipping": ["delivered"],
"delivered": [],
}
def order_pipeline(start):
seen = {start}
queue = deque([start])
while queue:
stage = queue.popleft()
yield stage
for nxt in graph[stage]:
if nxt not in seen:
seen.add(nxt)
queue.append(nxt)
print(list(order_pipeline("payment")))
# ['payment', 'fulfillment', 'shipping', 'delivered']
  • Bounded ring buffer with maxlen: prefer deque(maxlen=N) over a list with manual trimming. It cannot leak past the cap, and it removes a whole class of off-by-one bugs.
  • O(1) sliding aggregates: pair a deque(maxlen=w) with a running total so adding a value updates the average in constant time instead of re-summing the window each step.
  • Rotate for round-robin: rotating a deque of workers by one each cycle yields fair round-robin assignment without modulo arithmetic or index juggling.
  • Thread-safe single operations: for a lightweight producer/consumer, CPython’s atomic append/popleft let you skip a lock for the queue operations themselves. For real coordination — blocking gets, timeouts, bounded waits, task completion — reach for queue.Queue, which wraps a deque and adds all of that.

A running-average class that keeps the update O(1):

class RollingAverage:
def __init__(self, window):
self.window = deque(maxlen=window)
self.total = 0.0
def add(self, value):
if len(self.window) == self.window.maxlen:
self.total -= self.window[0] # subtract the soon-to-be-evicted value
self.window.append(value)
self.total += value
return self.total / len(self.window)
  • Using list.pop(0) or list.insert(0, x) in a hot loop — both are O(n); use deque.
  • Forgetting that extendleft reverses the input order, so extendleft([1, 2, 3]) yields [3, 2, 1, ...].
  • Treating a deque like a list and indexing the middle — d[500] is O(n).
  • Expecting slicing to work — d[1:3] raises TypeError; convert with list(d) first.
  • Assuming a bounded deque raises on overflow — it silently drops the opposite end.
  • Using deque for random-access lookups when a list or dict would be O(1).

Use deque when:

  • You push or pop at both ends (queue, stack, or both).
  • You need a bounded recent-history buffer (maxlen).
  • You implement BFS or a scheduler frontier.
  • You want a sliding window with O(1) end operations.

Avoid deque when:

  • You need random access by index (use list).
  • You need slicing (use list).
  • You search by value often — in is O(n) on both list and deque; use a set or dict for O(1) membership.
  • You need a sorted structure or repeated min/max extraction — use heapq.

collections.deque has been in the standard library since Python 2.4 and is available in every Python 3.x release, including 3.9 through 3.14. maxlen, extendleft, rotate, count, index, insert, and remove are all supported on 3.9+. No third-party packages are required.

  1. What is the time complexity of list.pop(0) versus deque.popleft(), and why? list.pop(0) is O(n) because removing the first element forces every remaining element to shift left one position in the underlying array. deque.popleft() is O(1) because a deque stores elements in a doubly-linked chain of blocks; removing from the left only updates a block pointer and leaves the other elements in place.

  2. What does deque(maxlen=3) do when you append a fourth item? It silently discards the item at the opposite end (the leftmost, for a right append) to stay within the cap. No exception is raised. That is exactly what you want for a “keep the last N” buffer, and exactly what surprises people who expected an overflow error.

  3. Why does extendleft([1, 2, 3]) produce [3, 2, 1, ...] instead of [1, 2, 3, ...]? extendleft calls appendleft once per input element, and each appendleft puts the new item at the very front, pushing existing items right. Processing [1, 2, 3] in order means 3 lands leftmost and the rest shift right behind it, yielding [3, 2, 1] followed by the original contents.

  4. Senior scenario: you need a producer/consumer pipeline where producers add work and a consumer drains it, across threads. A teammate suggests a plain list with a threading.Lock. What are the tradeoffs versus deque or queue.Queue? A plain list with a lock is correct but slow if the consumer uses pop(0): each dequeue is O(n) and holds the lock while shifting the whole list, serializing producers. A deque makes each end operation O(1) and atomic in CPython, so a simple deque with a lock — or even lock-free append/popleft — is much faster for the common case. But a bare deque gives you no blocking get, no timeout, no task_done/join coordination, and no bounded-wait semantics. For a real pipeline, queue.Queue is the production choice: it wraps a deque, adds blocking put and get with timeouts, a maxsize cap, and join so the consumer can signal completion. Use a bare deque when you need raw speed and will add coordination yourself; use queue.Queue when you want the coordination built in.

  • deque gives O(1) append and pop at both ends; list only at the end.
  • maxlen makes a self-trimming bounded buffer — ideal for sliding windows and recent history.
  • rotate shifts elements in place without sorting, for round-robin and circular-buffer patterns.
  • Indexed access and slicing are not deque’s strength — use a list for random access.
  • For thread-safe producer/consumer with blocking and coordination, prefer queue.Queue; deque is the fast, low-level primitive underneath it.