collections.deque

The right container for queues: adding and removing at either end is O(1), where list.pop(0) and list.insert(0, x) move every element. Indexing is O(1) at the ends but O(n) in the middle, and there is no slicing.

collections classPython 2.4+Live demo
Common call
deque([1, 2, 3], maxlen=5)
Returns
deque([1, 2, 3], maxlen=5)
Replaces
list used as a queue (pop(0), insert(0, x))
Watch out
no slicing — d[1:3] is a TypeError
collections.deque(iterableiterable — Initial items, added left to right with append().type: iterable · default: ()=(), maxlenmaxlen — Maximum length. When full, adding at one end discards from the other. Read-only afterwards.type: int | None · default: None=None)
→ deque

Demo

Live evaluation
Build a deque. With maxlen, only the LAST maxlen items survive. Leave maxlen empty for None.
Try:
Inputs
itemslist[str]comma-separated items
maxlenint | Noneempty = unbounded
Code
from collections import deque
deque(['a', 'b', 'c', 'd'], maxlen=None)
Result
deque(['a', 'b', 'c', 'd'])

maxlen=2 keeps c and d: items are appended one by one and each append past the limit pushes one out on the left. maxlen=0 accepts nothing at all, and a negative maxlen is a ValueError. Indexing an empty deque fails at d[0] with "deque index out of range".

Parameters

NameTypeRequiredDescription
iterableiterableno (())Initial items, added left to right with append().
maxlenint | Noneno (None)Maximum length. When full, adding at one end discards from the other. Read-only afterwards.

Return value

deque — A new deque holding the items of iterable (the last maxlen of them when bounded).

Common patterns

Breadth-first search
The canonical deque use: a FIFO frontier.
from collections import deque
queue = deque([start])
seen = {start}
while queue:
    node = queue.popleft()
    for nxt in graph[node]:
        if nxt not in seen:
            seen.add(nxt)
            queue.append(nxt)
Tail of a file
A bounded deque keeps the last n lines (the docs recipe).
from collections import deque
with open('app.log') as f:
    last_lines = deque(f, maxlen=10)
Stack
append + pop on the same end is LIFO.
from collections import deque
stack = deque()
stack.append(1)
stack.pop()
Slicing workaround
itertools.islice iterates without copying the whole deque.
from collections import deque
from itertools import islice
first_three = list(islice(d, 3))

Examples

1. From any iterable
from collections import deque deque('abc')
Returns
deque(['a', 'b', 'c'])
2. Bounded: keeps the last n
from collections import deque deque(range(10), maxlen=3)
Returns
deque([7, 8, 9], maxlen=3)
3. Ends are d[0] and d[-1]
from collections import deque d = deque('xyz') (d[0], d[-1])
Returns
('x', 'z')
4. copy keeps maxlen
from collections import deque deque([1, 2, 3], maxlen=5).copy()
Returns
deque([1, 2, 3], maxlen=5)
5. clear empties in place
from collections import deque d = deque([1, 2]) d.clear() d
Returns
deque([])
6. Membership and len work
from collections import deque d = deque('abc') ('b' in d, len(d))
Returns
(True, 3)
7. No slicing
from collections import deque deque([1, 2, 3])[0:2]
Returns
TypeError: sequence index must be integer, not 'slice'

Pitfalls

1. Slicing a deque
deque supports indexing but not slices. Use itertools.islice or convert to a list.
d[:2]
from collections import deque
deque('abc')[:2]
TypeError: sequence index must be integer, not 'slice'
islice(d, 2)
from collections import deque
from itertools import islice
list(islice(deque('abc'), 2))
['a', 'b']
2. Changing maxlen after creation
maxlen is read-only. Build a new deque with the new limit.
d.maxlen = 5
from collections import deque
d = deque(maxlen=3)
d.maxlen = 5
AttributeError: attribute 'maxlen' of 'collections.deque' objects is not writable
deque(d, maxlen=5)
from collections import deque
d = deque([1, 2], maxlen=3)
d = deque(d, maxlen=5)
d
deque([1, 2], maxlen=5)
3. Mutating while iterating
Unlike a list, a deque detects the size change and raises.
append in loop
from collections import deque
d = deque([1, 2])
for x in d:
    d.append(x)
RuntimeError: deque mutated during iteration
iterate a copy
from collections import deque
d = deque([1, 2])
for x in list(d):
    d.append(x)
d
deque([1, 2, 1, 2])

When to use

Use it
  • FIFO queues and BFS frontiers
  • Stacks where you also need the other end
  • Fixed-size history / sliding windows (maxlen)
Reach for something else
  • Random access or slicing into the middle → list
  • Producer/consumer between threads with blocking → queue.Queue
  • Priority ordering → heapq

Notes

CPython impl
Modules/_collectionsmodule.c — a doubly linked list of fixed-size blocks, which is why the ends are O(1) and the middle is O(n)
Thread safety
append, appendleft, pop and popleft are documented as thread-safe
Versions
deque since 2.4; maxlen argument 2.6; copy(), index() and insert() added in 3.5

FAQ

collections.deque is a double-ended queue: a sequence with O(1) append and pop at both the left and right ends. It is the standard way to build queues, stacks and fixed-size buffers.