collections.deque

A double-ended queue: fast adding and removing of items at both ends, optionally with a length limit.

Returns
A deque object.
On this page

Example

#
Python
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))
Resultsaved result, you can check it
deque(['Zoe', 'Emma', 'Jack', 'Mia'])
Zoe
Mia
deque(['Emma', 'Jack']) 2

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

#
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

#
Recent results thanks to maxlen
Python
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))
Resultsaved result, you can check it
[72]
[72, 95]
[72, 95, 64]
[95, 64, 88]
[64, 88, 91]
deque([64, 88, 91], maxlen=3)
81.0
A task queue and rotate()
Python
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)
Resultsaved result, you can check it
Checking 1_1
Checking 1_2
Checking 1_3
deque(['Mia', 'Emma', 'Jack'])
deque(['Jack', 'Mia', 'Emma'])
The shortest route, or breadth-first search
Python
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"))
Resultsaved result, you can check it
['Egypt', 'Rome', 'Safari']

Good practices

#
  • When you often remove items from the start of a list with pop(0), switch it to a deque and use popleft().
  • deque does not support slices, e.g. queue[1:3]. If you need them, turn the queue into a list or use itertools.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

#

Spotted a mistake or missing an example? Write to us.