Queue and Deque in Python Explained

A queue is a line. New items join at the back and items leave from the front, so the first one in is the first one out. This is called FIFO (first in, first out). Think of a ticket counter, a print queue or the tasks waiting for a server. In Python the right tool is collections.deque (say “deck”), which adds and removes at both ends in O(1) time.

This guide explains why a plain list is the wrong tool for a queue, how to use deque, how to wrap it in a Queue class, and the problems where a queue is the answer: shortest path with BFS, sliding windows, and round-robin. All the output shown is real.

Why not a list?

A list makes it easy to add at the end (append) and remove from the front (pop(0)), so it looks like a queue. The catch is that removing from the front makes every other item slide one place to the left. On a list of a hundred thousand items that is a hundred thousand moves for a single dequeue. (The costs of each operation are in Time Complexity of Python Data Structures.) A deque avoids the shifting completely. Here we remove 20,000 items from the front of each, and only print a yes-or-no answer, so the result does not depend on how fast your computer is:

import time
from collections import deque

n = 100_000
items = list(range(n))
dq = deque(range(n))

start = time.perf_counter()
for _ in range(20_000):
    items.pop(0)
t_list = time.perf_counter() - start

start = time.perf_counter()
for _ in range(20_000):
    dq.popleft()
t_deque = time.perf_counter() - start

print("list.pop(0) is at least 5x slower:", t_list > 5 * t_deque)

Output

list.pop(0) is at least 5x slower: True

The gap is usually far more than 5x, and it grows with the size of the queue. For a tiny queue you will never notice, but algorithms such as BFS can put thousands of items through a queue, and that is where O(n) per dequeue turns into a slow program.

deque: the right tool

deque lives in the collections module. Enqueue with append. Dequeue with popleft. The front is [0] and the back is [-1]:

from collections import deque

queue = deque()
queue.append("A")
queue.append("B")
queue.append("C")
print(queue)
print(queue.popleft())
print(queue[0], queue[-1])
print(len(queue), not queue)

Output

deque(['A', 'B', 'C'])
A
B C
2 False

Because it is double-ended, you can also add and remove at the front. That makes a deque work as a queue, as a stack, or as both at once:

from collections import deque

d = deque([2, 3])
d.appendleft(1)
d.append(4)
print(list(d))
print(d.popleft(), d.pop())
print(list(d))

Output

[1, 2, 3, 4]
1 4
[2, 3]

Dequeuing from an empty deque raises IndexError, so check if queue: first when it might be empty:

from collections import deque

q = deque()
try:
    q.popleft()
except IndexError as e:
    print(type(e).__name__)

Output

IndexError

A Queue class

In interviews and larger programs, wrap the deque in a small class, so the code reads enqueue and dequeue and exposes nothing else:

from collections import deque

class Queue:
    def __init__(self):
        self._items = deque()

    def enqueue(self, x):
        self._items.append(x)

    def dequeue(self):
        if not self._items:
            raise IndexError("dequeue from empty queue")
        return self._items.popleft()

    def peek(self):
        if not self._items:
            raise IndexError("peek from empty queue")
        return self._items[0]

    def is_empty(self):
        return not self._items

    def __len__(self):
        return len(self._items)

q = Queue()
for name in ["Asha", "Ben", "Chen"]:
    q.enqueue(name)
print(q.peek(), len(q))
print(q.dequeue(), q.dequeue())
print(q.is_empty(), len(q))

Output

Asha 3
Asha Ben
False 1

This mirrors the Stack class from Stack in Python: Implementation and Uses. The only difference is which end you take from.

maxlen and rotate

Two features that a list does not have. First, maxlen makes a bounded queue. When it is full, adding a new item silently drops the item at the opposite end. That is a perfect “keep the last N things” buffer, for example the last 3 readings or the recent history of a command line:

from collections import deque

last3 = deque(maxlen=3)
for x in range(1, 6):
    last3.append(x)
    print(list(last3))

Output

[1]
[1, 2]
[1, 2, 3]
[2, 3, 4]
[3, 4, 5]

Second, rotate(n) moves items around the ends. A positive number rotates to the right and a negative number to the left, and the items that fall off one end come back on the other:

from collections import deque

d = deque([1, 2, 3, 4, 5])
d.rotate(1)
print(list(d))
d.rotate(-2)
print(list(d))

Output

[5, 1, 2, 3, 4]
[2, 3, 4, 5, 1]

queue.Queue and priority queues

The standard library also has a queue module. Its Queue class is built for threads: it locks safely so several threads can put and get at the same time, and get() can wait until an item arrives. It uses put and get instead of append and popleft:

import queue

q = queue.Queue()
q.put("job1")
q.put("job2")
print(q.get(), q.qsize(), q.empty())
q.get()
try:
    q.get_nowait()
except queue.Empty:
    print("Empty")

Output

job1 1 False
Empty

Use queue.Queue when threads share work, and deque for everything else. It is faster because it does not lock anything. If you need the smallest item to come out first rather than the oldest, that is a priority queue, built on a heap. See Heap and heapq in Python: Priority Queues.

Use 1: shortest path with BFS

Breadth-first search (BFS) explores a maze or a graph in rings: everything one step away, then everything two steps away, and so on. A queue does that for free, because items discovered first are also processed first. Here S is the start, E is the exit and # is a wall:

from collections import deque

maze = [
    "S.#.",
    "..#.",
    ".#..",
    "...E",
]

def shortest_path(maze):
    rows, cols = len(maze), len(maze[0])
    queue = deque([(0, 0, 0)])          # row, column, steps so far
    seen = {(0, 0)}
    while queue:
        r, c, steps = queue.popleft()
        if maze[r][c] == "E":
            return steps
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = r + dr, c + dc
            inside = 0 <= nr < rows and 0 <= nc < cols
            if inside and maze[nr][nc] != "#" and (nr, nc) not in seen:
                seen.add((nr, nc))
                queue.append((nr, nc, steps + 1))
    return -1

print(shortest_path(maze))
print(shortest_path(["S#E"]))

Output

6
-1

The first time the search reaches E, it has used the fewest possible steps, since every shorter route was already tried. The seen set stops it from visiting a cell twice. Returning -1 means there is no route at all, like the second example. The same code works on any graph, see Graphs in Python: Adjacency List, BFS and DFS. On trees, BFS is the level-by-level traversal in Binary Tree in Python: Traversals Explained.

Use 2: counting recent events

“How many requests came in during the last 3000 milliseconds?” Requests arrive in time order, so the oldest are always at the front. Keep the timestamps in a deque, and drop from the front while they are too old:

from collections import deque

class RecentCounter:
    def __init__(self):
        self.times = deque()

    def ping(self, t):
        self.times.append(t)
        while self.times[0] < t - 3000:
            self.times.popleft()
        return len(self.times)

rc = RecentCounter()
print([rc.ping(t) for t in [1, 100, 3001, 3002]])

Output

[1, 2, 3, 3]

Every timestamp is added once and removed at most once, so each call is O(1) on average. This is a rate limiter in a few lines, and it is the sliding-window idea from Sliding Window in Python applied to time.

Use 3: round-robin

Operating systems give each process a turn, then send it to the back of the line. That is a queue, and rotate makes it short to write. In the “hot potato” game (the Josephus problem), players stand in a circle and every k-th player is eliminated until one is left:

from collections import deque

def last_standing(players, k):
    circle = deque(players)
    out = []
    while len(circle) > 1:
        circle.rotate(-(k - 1))
        out.append(circle.popleft())
    return out, circle[0]

print(last_standing(["A", "B", "C", "D", "E"], 3))

Output

(['C', 'A', 'E', 'B'], 'D')

Rotating by -(k - 1) brings the k-th player to the front, and popleft() removes them. Player D is the last one standing.

Use 4: sliding window maximum

A well-known interview question: given a list and a window size k, report the maximum of every window. Checking each window costs O(n × k). With a deque that keeps indexes in decreasing order of value, the maximum is always at the front, and the whole thing is O(n):

from collections import deque

def window_max(nums, k):
    dq = deque()                  # indexes, values kept in decreasing order
    out = []
    for i, x in enumerate(nums):
        while dq and nums[dq[-1]] <= x:
            dq.pop()
        dq.append(i)
        if dq[0] <= i - k:
            dq.popleft()
        if i >= k - 1:
            out.append(nums[dq[0]])
    return out

print(window_max([1, 3, -1, -3, 5, 3, 6, 7], 3))

Output

[3, 3, 5, 5, 6, 7]

Before adding a new number, pop every smaller number from the back, since they can never be the maximum again while the new number is in the window. Pop from the front once the front index has slid out of the window. Each index enters and leaves the deque once. This is a monotonic deque, the cousin of the monotonic stack in the stack guide.

A queue built from two stacks

A classic question: “implement a queue using only stacks”. Use one stack for incoming items and one for outgoing items. When the outgoing stack is empty, pour the incoming stack into it, which reverses the order, so the oldest item ends up on top:

class QueueFromStacks:
    def __init__(self):
        self.inbox = []
        self.outbox = []

    def enqueue(self, x):
        self.inbox.append(x)

    def dequeue(self):
        if not self.outbox:
            while self.inbox:
                self.outbox.append(self.inbox.pop())
        return self.outbox.pop()

q = QueueFromStacks()
for x in [1, 2, 3]:
    q.enqueue(x)
print(q.dequeue())
q.enqueue(4)
print(q.dequeue(), q.dequeue(), q.dequeue())

Output

1
2 3 4

Each item is moved at most once, so dequeue is O(1) amortized. Note that item 4 correctly waits behind 2 and 3, even though it was added after the first dequeue.

Time complexity

The ends are fast and the middle is slow. If you find yourself indexing into the middle of a deque, a list is probably the better choice.

Common mistakes

• Using list.pop(0) as a queue. It works, but it is O(n) for every dequeue. Use deque.
• Dequeuing from an empty queue. popleft() raises IndexError. Check while queue: or if queue:.
• Slicing a deque. d[1:3] is not allowed and raises TypeError. Convert with list(d) first, or use itertools.islice.
• Forgetting the seen set in BFS. Without it, the same cell is added again and again and the search may never end.
• Mixing up stack and queue. pop() takes the newest item (stack). popleft() takes the oldest (queue).

Try it yourself

Work out each answer first, then open the solution.

1. Use a deque to keep only the last 3 numbers while adding 1 to 6 one by one.

from collections import deque

last = deque(maxlen=3)
for x in range(1, 7):
    last.append(x)
print(list(last))

[4, 5, 6]

2. Rotate [1, 2, 3, 4, 5] two places to the left.

from collections import deque

d = deque([1, 2, 3, 4, 5])
d.rotate(-2)
print(list(d))

[3, 4, 5, 1, 2]

3. Check whether a word is a palindrome using a deque, comparing the front and the back.

from collections import deque

def is_palindrome(text):
    d = deque(text)
    while len(d) > 1:
        if d.popleft() != d.pop():
            return False
    return True

print(is_palindrome("racecar"), is_palindrome("python"))

True False

4. Why is list.pop(0) a poor way to dequeue?

Run these in our free Python compiler.

Frequently asked questions

What is a queue in Python?

A queue is a first-in, first-out collection: items are added at the back and removed from the front. In Python you normally use collections.deque with append() and popleft().

What does FIFO mean?

First in, first out: the item that has waited longest is served first, like people standing in a line.

What is the difference between a stack and a queue?

A stack removes the newest item first (LIFO), a queue removes the oldest item first (FIFO). Use pop() on a list for a stack and popleft() on a deque for a queue.

What is a deque in Python?

A deque (double-ended queue) is a sequence that supports adding and removing at both ends in O(1) time. It can act as a stack, a queue, or a fixed-size buffer with maxlen.

Should I use a list or a deque for a queue?

Use a deque. A list works for tiny queues, but pop(0) is O(n), so it slows down as the queue grows.

When should I use queue.Queue instead of deque?

Use queue.Queue when several threads share the queue, because it is thread-safe and can block until an item is available. In single-threaded code, deque is simpler and faster.

Related reading

• Stack in Python: Implementation and Uses – the last-in-first-out partner.
• Graphs in Python: Adjacency List, BFS and DFS – BFS on any graph.
• Heap and heapq in Python: Priority Queues – when the smallest item should go first.
• Sliding Window Technique in Python – windows over lists and strings.