🧩 Data Structures & Algorithms · Chapter 7

Queues and deques

The print jobs on an office printer, the messages between two services, and breadth-first search through a map all need the same promise: whoever arrived first is served first.

Study this lesson free in the app →

The basics

A queue is a collection where items join at the back and leave from the front: first in, first out — FIFO. A deque ("deck", double-ended queue) lets you add and remove at both ends.

The problem it solves: whenever work arrives faster than it can be handled — print jobs, customer requests, messages, cells to explore in a maze — you need to hold it and process it fairly, in arrival order. A queue does that with O(1) enqueue and dequeue.

The mental model: a line at a bakery counter. New customers join the end; the person at the front is served next. Nobody jumps the line, and nobody waits forever.

In Python, use collections.deque. A plain list is the wrong tool: list.pop(0) shifts every remaining item, O(n). Space is O(n) for n items.

Explained

Ten people send documents to one printer within a minute. The printer can handle one at a time.

If it printed the most recent job first (a stack), the first person might wait all afternoon while newer jobs keep jumping ahead.

So the printer keeps a queue: first sent, first printed. Fair, predictable, and every add and remove takes constant time.

The bakery line and the ferry ramp

At a bakery, customers take their place at the end of the line and the baker serves whoever is at the front. Someone who arrives at 8:01 is always served before someone who arrives at 8:02. That's a queue.

Now picture a small car ferry with one ramp at each end. Cars can drive on at the back or, if the crew decides, squeeze on at the front; at the far shore they can drive off either end. That's a deque — both ends are open.

What neither allows is pulling a car out of the middle of the line. Both structures are fast precisely because they only ever touch the ends.

Precisely

| Operation | deque | list | | --- | --- | --- | | add at back — append(x) | O(1) | O(1) amortised | | remove at front — popleft() / pop(0) | O(1) | O(n) | | add at front — appendleft(x) / insert(0, x) | O(1) | O(n) | | remove at back — pop() | O(1) | O(1) | | index in the middle — d[i] | O(n) | O(1) |

How O(1) at the front is possible:

• Linked list — keep pointers to head and tail; dequeue moves the head pointer.
• Circular buffer — a fixed array plus head and size. Dequeue: read buf[head], head = (head + 1) % cap. Enqueue: write at (head + size) % cap. Nothing ever shifts; indices wrap around.
• CPython's deque — a doubly linked list of 64-slot blocks: both ends O(1), good memory locality.

For threads handing work to each other, queue.Queue wraps this with locks and blocking get().

Enqueue at the back, dequeue from the front

3, 7 and 1 join in that order. The first dequeue removes 3 — the oldest, not the newest. 9 joins at the back; the next dequeue removes 7. After 4 joins, the queue reads 1, 9, 4 from front to back. Every operation touches only an end: O(1).

A ticket counter: everyone served in order

Tickets 101–103 arrive, two are served, two more arrive, then the counter catches up. Served order: 101, 102, 103, 104, 105 — exactly the arrival order, however arrivals and service interleave. Run the same operations as a stack and the order would be 103, 102, 105, 104, 101: ticket 101 waits until the very end.

deque in practice, and BFS

from collections import deque

q = deque()
q.append("job-1")            # enqueue   O(1)
q.append("job-2")
q.popleft()                  # dequeue   O(1)  -> 'job-1'

last3 = deque(maxlen=3)      # keeps only the newest 3
for reading in [5, 6, 7, 8]:
    last3.append(reading)    # deque([6, 7, 8]) — 5 fell off the front

def bfs_distance(graph, start):
    dist = {start: 0}
    q = deque([start])
    while q:
        node = q.popleft()               # nearest unexplored first
        for nxt in graph[node]:
            if nxt not in dist:
                dist[nxt] = dist[node] + 1
                q.append(nxt)
    return dist                          # O(V + E) time, O(V) space

city = {"Home": ["Cafe", "Park"], "Cafe": ["Home", "Library"],
        "Park": ["Home", "Library", "Museum"],
        "Library": ["Cafe", "Park", "Station"],
        "Museum": ["Park"], "Station": ["Library"]}
bfs_distance(city, "Home")
# {'Home': 0, 'Cafe': 1, 'Park': 1, 'Library': 2, 'Museum': 2, 'Station': 3}

Because the queue releases nodes in the order they were found, every node at distance 1 is processed before any at distance 2 — so the first time BFS reaches a node is along a shortest path.

Queues between machines

The same FIFO idea, stretched across a network, is how large systems stay up:

• Message queues (RabbitMQ, Amazon SQS, Kafka topics) sit between a producer and a consumer. A traffic spike piles up in the queue instead of crashing the consumer; the consumer drains it at its own pace.
• Bounded queues and back-pressure — an unbounded queue just moves the crash from CPU to memory. Production queues have a maximum size; when full, they block the producer, drop, or reject with "try later".
• Ordering costs throughput — strict FIFO across one queue means one consumer at a time. To scale, systems split into many queues (partitions) and keep FIFO only within each.
• Fairness — a single shared queue lets one noisy customer delay everyone; per-customer queues served round-robin fix that.

The question to ask in a design round: what happens when the queue fills up?

Gotchas

• list.pop(0) as a queue — O(n) per dequeue; a BFS over a million nodes turns quadratic. Use deque.popleft().
• Using a stack where order must be fair — LIFO starves the oldest work.
• Indexing a deque in the middle — d[len(d) // 2] is O(n). Deques are for the ends.
• Marking BFS nodes visited too late — mark when you enqueue, not when you dequeue, or the same node enters the queue many times.
• Unbounded queues — memory grows until the process dies; give real queues a limit.
• Confusing a priority queue with a queue — heapq serves the smallest item first, not the earliest.

Words to know

In two minutes

• A queue is FIFO: enqueue at the back, dequeue from the front, both O(1). Space O(n).
• In Python use collections.deque: append + popleft. list.pop(0) is O(n), so draining a list-queue of n items is O(n²).
• A deque is O(1) at both ends, so it can act as a stack, a queue, or a sliding window that drops old items from the front.
• Under the hood, queues are a linked list, a circular buffer (head and tail indices wrapping with % capacity), or a deque of fixed-size blocks.
• Breadth-first search uses a queue so nodes are explored in order of distance — that's why BFS finds shortest paths in unweighted graphs. O(V + E).
• A deque of timestamps is a rolling-window counter: append new events, popleft expired ones — the core of many rate limiters.
• Deques are fast at the ends but O(n) in the middle; a priority queue (heap) serves by priority, not arrival.

Test yourself

There are 9 questions, 4 puzzles and 5 recall cards for this lesson in the app — the recall cards come back on later days, just before you would forget.