collections. deque
A double-ended queue: fast adding and removing of items at both ends, optionally with a length limit.
- Returns
- A
dequeobject.
Example
#from collections import deque
queue = deque(["Emma", "Jack"])
queue.append("Mia")
queue.appendleft("Zoe")
print(queue)
print(queue.popleft())
print(queue.pop())
print(queue, len(queue))Definition and usage
#The deque class (from βdouble-ended queueβ) in the collections module works like a list optimized for operations at both ends. The append() and pop() methods work on the right end, and appendleft() and popleft() on the left. Each of them runs in constant time, regardless of the length of the queue.
An ordinary list also has pop(0) and insert(0, x), but those operations shift all the other items, so they are slow on large lists. That is why task queues, breadth-first graph search (BFS), and a buffer of recent events are built on deque.
The maxlen parameter limits the length: when the queue is full, adding an item at one end removes an item from the opposite end. This is a ready-made way to keep, for example, the last few results. The rotate(n) method shifts the items around in a circle by n positions. Access by index works, but in the middle of a long queue it is slower than in a list, and slices are not supported.
Syntax
#from collections import deque
deque(iterable, maxlen=None)
queue.append(x)
queue.appendleft(x)
queue.pop()
queue.popleft()
queue.rotate(n)Parameters
#iterable
collection, optional
The initial items of the queue.maxlen
int or None, default None
The maximum length. Once it is exceeded, items from the opposite end are removed.
More examples
#from collections import deque
recent = deque(maxlen=3)
for score in [72, 95, 64, 88, 91]:
recent.append(score)
print(list(recent))
print(recent)
print(sum(recent) / len(recent))from collections import deque
tasks = deque(["1_1", "1_2", "1_3"])
while tasks:
task = tasks.popleft()
print("Checking", task)
players = deque(["Emma", "Jack", "Mia"])
players.rotate(1)
print(players)
players.rotate(-2)
print(players)from collections import deque
paths = {
"Egypt": ["Space", "Rome"],
"Space": ["Jurassic Park"],
"Rome": ["Safari"],
"Jurassic Park": ["Safari"],
"Safari": [],
}
def shortest(start, goal):
queue = deque([[start]])
seen = {start}
while queue:
route = queue.popleft()
if route[-1] == goal:
return route
for neighbor in paths[route[-1]]:
if neighbor not in seen:
seen.add(neighbor)
queue.append(route + [neighbor])
return None
print(shortest("Egypt", "Safari"))Good practices
#- When you often remove items from the start of a list with
pop(0), switch it to adequeand usepopleft(). dequedoes not support slices, e.g.queue[1:3]. If you need them, turn the queue into a list or useitertools.islice().- An empty queue is false in conditions, so a
while queue:loop runs as long as there are items left in it.
Related entries
#- list.pop()Removes the item at the given index (the last one by default) and returns it.
- list.append()Adds one item to the end of a list.
- list.insert()Inserts an item at a chosen position in a list.
- collections.CounterA dictionary for counting: for each item, it stores the number of times it occurs.
- itertoolsTools for working with iterators: chaining, grouping, combinations, and infinite sequences.
Spotted a mistake or missing an example? Write to us.