Skip to content
Tutorials Center
My learning

Topics

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.

Python
from collections import deque

queue = deque(["a", "b"])
queue.append("c")
queue.popleft()   # 'a'

Try it

Python Queue operations

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.

Python A ring buffer with maxlen

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

Python
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.
  • maxlen makes 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] raises TypeError; convert with list(d) first, or use itertools.islice.
  • Thread safety. append, appendleft, pop and popleft are atomic, so a deque works for simple producer/consumer code between threads. For blocking behavior use queue.
  • Equality and order. Two deques are equal if their items are equal in order; maxlen is not part of the comparison.
  • Shallow copies. copy() copies the container, not the items.
  • Use list when you mostly index or slice, and deque when you mostly add and remove at the ends.