Python Double-Ended Queues with collections.deque

Intermediate

The Lists lesson already showed how a list can represent a small waiting line. This lesson answers a different question: what should you choose when adding and removing items at either end is a frequent operation? The standard-library collections.deque is a double-ended queue designed for that job.

Create a deque and work at both ends

Import deque from collections and create one from any iterable. append() adds on the right, appendleft() adds on the left, pop() removes from the right, and popleft() removes from the left. Each operation returns or stores the item as its name suggests; they do not return a replacement deque.

from collections import deque

work = deque(["test", "package"])
work.append("publish")
work.appendleft("lint")
work.popleft()
work.pop()
print(list(work))?

Use popleft() for a first-in, first-out queue

A FIFO queue serves items in the order they arrived. With deque, append() adds new work at the right and popleft() serves the oldest item from the left. Check that the deque is not empty before removing an item: pop() and popleft() both raise IndexError when the deque is empty.

from collections import deque

waiting = deque(["A", "B", "C"])
served = waiting.popleft()
print(served, list(waiting))?

Choose deque instead of repeatedly removing index zero

A list is a great general-purpose sequence and supports fast indexing. But removing the first item with list.pop(0) shifts the remaining items, making that operation O(n). deque is designed for efficient end operations, which take approximately O(1) time at either end. Prefer deque for a queue that repeatedly adds at one end and removes at the other; prefer a list when fast random access or frequent middle indexing is the main need.

from collections import deque

ready = deque([10, 20, 30, 40])
removed = ready.popleft()
print(removed)
print(list(ready))?

Keep only the most recent items with maxlen

Set maxlen to make a bounded deque. When it is full, appending on one end discards the same number of items from the opposite end. This is useful for a rolling history or the latest few events. Inspect maxlen to read the configured bound; it is read-only. Choose a bound deliberately because discarded entries are not retained by the deque.

from collections import deque

recent = deque(["open", "edit", "save"], maxlen=3)
recent.append("close")
print(list(recent))?

Rotate items when the starting position changes

rotate(n) moves items around the ends without building a second list. A positive n rotates to the right; a negative n rotates to the left. Rotation is useful when a sequence of turns or workers needs a new starting position. A deque also supports iteration and membership tests, but indexed access slows toward the middle, so it is not a replacement for every list.

from collections import deque

players = deque(["Ari", "Bo", "Cy"])
players.rotate(-1)
print(list(players))?