Python Reference ยท Standard Library: Data Structures and Functional Tools
collections.deque
Reference for Python collections.deque: fast appends and pops at both ends, maxlen ring buffers, rotate(), extendleft() and why indexing the middle is slow.
A deque (pronounced "deck") is a double-ended queue. Adding or removing items at either end takes constant time, which a list cannot offer at the front: list.pop(0) and list.insert(0, x) shift every other element.
Use a deque for queues, breadth-first search, sliding windows and "last N items" buffers.
from collections import deque queue = deque(["a", "b"]) queue.append("c") queue.popleft() # 'a'
Try it
Press Run (or Ctrl + Enter) to see the result here.
Program input ยท what you'd type while the program runs
Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.
Press Run (or Ctrl + Enter) to see the result here.
Program input ยท what you'd type while the program runs
Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.
Syntax
deque(iterable=(), maxlen=None)
| Name | Description |
|---|---|
iterable |
Optional starting items, in order. |
maxlen |
Optional maximum size. When full, adding on one end discards an item from the other. None means unbounded. |
| Method | Description |
|---|---|
append(x), appendleft(x) |
Add to the right or left end. |
pop(), popleft() |
Remove and return from the right or left end. |
extend(it), extendleft(it) |
Add many items. extendleft reverses their order, because each lands on the left in turn. |
rotate(n=1) |
Rotate n steps to the right (negative: left). |
clear(), copy(), count(x), index(x), insert(i, x), remove(x), reverse() |
Work like the list methods of the same name. |
Return value: a new deque. pop() and popleft() return the removed item; most other methods return None.
Raises: IndexError when popping from an empty deque; ValueError for remove() or index() of a missing value; IndexError when insert() would exceed maxlen.
Usage notes
- Ends are fast, the middle is not. Indexing
d[i]is quick near either end but takes linear time near the middle, so do not treat a deque as a random-access list. maxlenmakes a ring buffer. Appending to a full bounded deque silently drops an item from the opposite end. Handy for "last 100 log lines".- No slicing.
d[1:3]raisesTypeError; convert withlist(d)first, or useitertools.islice. - Thread safety.
append,appendleft,popandpopleftare atomic, so a deque works for simple producer/consumer code between threads. For blocking behavior usequeue. - Equality and order. Two deques are equal if their items are equal in order;
maxlenis not part of the comparison. - Shallow copies.
copy()copies the container, not the items. - Use
listwhen you mostly index or slice, anddequewhen you mostly add and remove at the ends.
Related
collectionsmodule,heapq,list.pop()- Lessons: Collections, Data structures