Python deque: Double-Ended Queue from collections
What you’ll learn
Section titled “What you’ll learn”- The difference between
listanddequeand whylist.pop(0)is a performance trap. - How
append,appendleft,pop, andpopleftgive O(1) operations at both ends. - How
maxlencreates a self-evicting bounded buffer for sliding windows and recent history. - How
rotaterepositions elements in place without re-sorting, for round-robin and circular use. - When
dequeis the wrong choice and a plainlist(orsetorheapq) is better.
Summary
Section titled “Summary”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 problem it solves
Section titled “The problem it solves”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.
How it works
Section titled “How it works”A deque is a sequence. You build it from any iterable, and optionally cap it with maxlen.
from collections import deque
d = deque() # emptyd = deque([1, 2, 3]) # from an iterabled = deque(maxlen=3) # bounded, starts emptyThe 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 droppedrotate(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()andpopleft()on an empty deque raiseIndexError.extendleft([1, 2, 3])reverses the input: it callsappendleftonce per element, so the last input element ends up leftmost, givingdeque([3, 2, 1, ...]).- Indexed access
d[500]is O(n); there is no slicing —d[1:3]raisesTypeError. Convert withlist(d)first if you need a slice. - A bounded
dequesilently drops on overflow; nothing raises, which is both its power and a footgun if you expected an error. - In CPython, individual
append/pop/appendleft/popleftcalls are atomic, so adequeis 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).
Realistic example
Section titled “Realistic example”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 unblocksgraph = { "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']Production patterns
Section titled “Production patterns”- Bounded ring buffer with
maxlen: preferdeque(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/popleftlet you skip a lock for the queue operations themselves. For real coordination — blocking gets, timeouts, bounded waits, task completion — reach forqueue.Queue, which wraps adequeand 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)Common mistakes
Section titled “Common mistakes”- Using
list.pop(0)orlist.insert(0, x)in a hot loop — both are O(n); usedeque. - Forgetting that
extendleftreverses the input order, soextendleft([1, 2, 3])yields[3, 2, 1, ...]. - Treating a
dequelike a list and indexing the middle —d[500]is O(n). - Expecting slicing to work —
d[1:3]raisesTypeError; convert withlist(d)first. - Assuming a bounded
dequeraises on overflow — it silently drops the opposite end. - Using
dequefor random-access lookups when alistordictwould be O(1).
When to use it and when not to
Section titled “When to use it and when not to”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 —
inis O(n) on bothlistanddeque; use asetordictfor O(1) membership. - You need a sorted structure or repeated min/max extraction — use
heapq.
Compatibility
Section titled “Compatibility”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.
Interview questions
Section titled “Interview questions”-
What is the time complexity of
list.pop(0)versusdeque.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. -
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 rightappend) 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. -
Why does
extendleft([1, 2, 3])produce[3, 2, 1, ...]instead of[1, 2, 3, ...]?extendleftcallsappendleftonce per input element, and eachappendleftputs the new item at the very front, pushing existing items right. Processing[1, 2, 3]in order means3lands leftmost and the rest shift right behind it, yielding[3, 2, 1]followed by the original contents. -
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 versusdequeorqueue.Queue? A plain list with a lock is correct but slow if the consumer usespop(0): each dequeue is O(n) and holds the lock while shifting the whole list, serializing producers. Adequemakes each end operation O(1) and atomic in CPython, so a simpledequewith a lock — or even lock-freeappend/popleft— is much faster for the common case. But a baredequegives you no blockingget, no timeout, notask_done/joincoordination, and no bounded-wait semantics. For a real pipeline,queue.Queueis the production choice: it wraps adeque, adds blocking put and get with timeouts, amaxsizecap, andjoinso the consumer can signal completion. Use a baredequewhen you need raw speed and will add coordination yourself; usequeue.Queuewhen you want the coordination built in.
Key takeaways
Section titled “Key takeaways”dequegives O(1) append and pop at both ends;listonly at the end.maxlenmakes a self-trimming bounded buffer — ideal for sliding windows and recent history.rotateshifts elements in place without sorting, for round-robin and circular-buffer patterns.- Indexed access and slicing are not
deque’s strength — use alistfor random access. - For thread-safe producer/consumer with blocking and coordination, prefer
queue.Queue;dequeis the fast, low-level primitive underneath it.
Related pages
Section titled “Related pages”- collections module — overview of
collectionsincludingdeque,defaultdict, andCounter - OrderedDict — when order matters and
dictordering is not enough - namedtuple — lightweight immutable records
- itertools — iterator building blocks that pair well with deque pipelines
- threading vs multiprocessing — concurrency patterns and the GIL
Official references
Section titled “Official references”- collections.deque — Python docs
- collections recipes — standard-library recipes including several deque patterns
- PEP 309 — Built-in deque type