Queues and deques

What this chapter covers

A queue is the stack's mirror image. Where a stack hands you the newest item, a queue hands you the oldest — first in, first out. That's the ordering for anything that has to be served fairly, in the order it arrived: a print spooler, a task queue, the waiting frontier of a breadth-first search. This chapter builds a queue and its two-ended cousin the deque on a doubly linked list so every end operation is O(1), and then shows the single most common way people get queues wrong in Python — and how much it costs.

A bit of history

Queues are older than computers — they come from the mathematics of waiting lines. In 1909 the Danish engineer Agner Krarup Erlang, working for the Copenhagen telephone company, published the first study of how calls wait for a free line, founding what's now called queueing theory. The unit of telephone traffic, the erlang, is named after him. When computers arrived they inherited both the math and the structure: operating systems queue processes waiting for the CPU, networks queue packets waiting for a link, and printers queue jobs waiting for the tray. The FIFO discipline is everywhere a scarce resource serves many requests, because serving them in arrival order is the simplest notion of fair.

The intuition

A queue is a line at a counter. You join at the back; you're served from the front; you can't cut in. The person who has waited longest goes next. Enqueue adds to the back, dequeue removes from the front, and that's the whole interface.

A deque — pronounced "deck," short for double-ended queue — relaxes the rule to let you add and remove at both ends. That one generalization makes it the swiss-army version of this family: use only the back and it's a stack, use back-in front-out and it's a queue. Because a deque can do everything a stack or queue can, it's the structure the standard library actually ships, and the one you'll reach for in practice.

Complexity: how it scales

Built on a doubly linked list, every operation touches only an end, so enqueue, dequeue, and all four deque operations are $O(1)$ — link or unlink a node, done, no shifting and no searching. Space is $O(n)$. The prev pointer from the linked list chapter is what makes popping the back as cheap as the front; without it, finding the new tail would mean walking the whole list.

There's no recurrence — the point is that the cost stays flat. The chart below enqueues n items and then dequeues all n, timing our queue against the library's; both lines are straight, because O(1) per operation means linear total work:

What it's good at, what it isn't

Reach for a queue whenever order of arrival matters and you only ever add to one end and take from the other. Like the stack, its restriction is its strength: FIFO is easy to reason about and O(1) to maintain, and the deque generalization covers the cases where you need both ends without giving up the constant-time guarantee.

What a queue isn't is indexable or searchable — you can't ask for the fifth item in line without walking to it. And there's a trap specific to Python that deserves its own warning, because it's so easy to fall into and so quietly expensive:

The data, or the inputs

The face-off feeds the queue the pattern that exposes the trap: enqueue n items, then dequeue all n. That's exactly where list.pop(0) turns quadratic, so it makes the difference between O(1) and O(n) per dequeue visible. The animation uses a tiny hand-written script of eight operations on a five-item line, because the point there is the order things leave, not the speed.

Build it, one function at a time

The deque is the foundation. Pushing to the back links a node onto the tail:

def push_back(self, value):
    """O(1): link a node onto the tail (the back of the line)."""
    node = _Node(value)
    node.prev = self._tail
    if self._tail is not None:
        self._tail.next = node
    else:
        self._head = node
    self._tail = node
    self._n += 1

Pushing to the front is the mirror — link onto the head:

def push_front(self, value):
    """O(1): link a node onto the head (the front of the line)."""
    node = _Node(value)
    node.next = self._head
    if self._head is not None:
        self._head.prev = node
    else:
        self._tail = node
    self._head = node
    self._n += 1

Popping the front removes the head, in O(1), by just moving the head pointer — no shifting, which is the whole advantage over a list:

def pop_front(self):
    """O(1): remove and return the front. No shifting — just move the head."""
    if self._head is None:
        raise IndexError("pop from empty deque")
    node = self._head
    self._head = node.next
    if self._head is not None:
        self._head.prev = None
    else:
        self._tail = None
    self._n -= 1
    return node.value

And popping the back is the operation the prev pointer buys us — remove the tail just as cheaply:

def pop_back(self):
    """O(1): remove and return the back — the payoff of the prev pointer."""
    if self._tail is None:
        raise IndexError("pop from empty deque")
    node = self._tail
    self._tail = node.prev
    if self._tail is not None:
        self._tail.next = None
    else:
        self._head = None
    self._n -= 1
    return node.value

The queue is then just a deque with the interface narrowed to FIFO: join the back, leave the front, nothing in between:

class Queue:
    """A FIFO queue is just a deque with the operations restricted: you join at
    the back and leave from the front, and can't touch anything in between."""

    def __init__(self):
        self._d = Deque()

    def enqueue(self, value):
        self._d.push_back(value)      # join the back of the line

    def dequeue(self):
        return self._d.pop_front()    # the person who's waited longest goes first

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

    def to_list(self):
        return self._d.to_list()

Watch it work

Here's a queue as a little line at a counter. Green is the front — the next to be served; blue is the back — the most recent to arrive. Step through it: items join at the back (blue), and each dequeue takes the front (green), the one that has waited longest. Notice the order out matches the order in — A, B, C, D come out in exactly the sequence they arrived, which is the whole promise of FIFO:

The complete code

Both versions in one place — flip between them. The from-scratch tab is our Deque and the Queue built on it. The library tab is collections.deque, the doubly linked structure you actually use — plus the list.pop(0) version, kept only to show what not to do.

"""A queue — first in, first out — and its two-ended cousin the deque, both built
on a doubly linked list so every end operation is O(1).

A queue is the mirror of the stack from the last chapter: instead of taking the
newest item, you take the oldest. That's the ordering you want any time work has
to be served in the order it arrived — a print spooler, a task queue, the frontier
of a breadth-first search.
"""


class _Node:
    __slots__ = ("value", "prev", "next")

    def __init__(self, value):
        self.value = value
        self.prev = None
        self.next = None


class Deque:
    """A double-ended queue on a doubly linked list: O(1) at BOTH ends. The prev
    pointer is what lets us pop from the back as cheaply as the front."""

    def __init__(self):
        self._head = None
        self._tail = None
        self._n = 0

    # region: push_back
    def push_back(self, value):
        """O(1): link a node onto the tail (the back of the line)."""
        node = _Node(value)
        node.prev = self._tail
        if self._tail is not None:
            self._tail.next = node
        else:
            self._head = node
        self._tail = node
        self._n += 1
    # endregion

    # region: push_front
    def push_front(self, value):
        """O(1): link a node onto the head (the front of the line)."""
        node = _Node(value)
        node.next = self._head
        if self._head is not None:
            self._head.prev = node
        else:
            self._tail = node
        self._head = node
        self._n += 1
    # endregion

    # region: pop_front
    def pop_front(self):
        """O(1): remove and return the front. No shifting — just move the head."""
        if self._head is None:
            raise IndexError("pop from empty deque")
        node = self._head
        self._head = node.next
        if self._head is not None:
            self._head.prev = None
        else:
            self._tail = None
        self._n -= 1
        return node.value
    # endregion

    # region: pop_back
    def pop_back(self):
        """O(1): remove and return the back — the payoff of the prev pointer."""
        if self._tail is None:
            raise IndexError("pop from empty deque")
        node = self._tail
        self._tail = node.prev
        if self._tail is not None:
            self._tail.next = None
        else:
            self._head = None
        self._n -= 1
        return node.value
    # endregion

    def __len__(self):
        return self._n

    def to_list(self):
        out, node = [], self._head
        while node is not None:
            out.append(node.value)
            node = node.next
        return out


# region: queue
class Queue:
    """A FIFO queue is just a deque with the operations restricted: you join at
    the back and leave from the front, and can't touch anything in between."""

    def __init__(self):
        self._d = Deque()

    def enqueue(self, value):
        self._d.push_back(value)      # join the back of the line

    def dequeue(self):
        return self._d.pop_front()    # the person who's waited longest goes first

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

    def to_list(self):
        return self._d.to_list()
# endregion

"""collections.deque is the queue and deque you actually use in Python — a doubly
linked list of blocks with O(1) at both ends, exactly like ours but tuned in C.

The instructive comparison is the WRONG one: a plain list used as a queue. `append`
is fine, but taking from the front with `pop(0)` shifts every remaining element
one slot left — O(n) per dequeue, O(n²) to drain the queue. It's the single most
common accidental-quadratic bug in Python, and this chapter's face-off shows it.
"""
from collections import deque


# region: deque_queue
def run_queue_deque(ops):
    """FIFO on a deque: append to the back, popleft from the front. Both O(1)."""
    q = deque()
    out = []
    for op in ops:
        if op[0] == "enq":
            q.append(op[1])
        else:
            out.append(q.popleft())
    return out
# endregion


# region: list_queue
def run_queue_list(ops):
    """FIFO on a plain list — the anti-pattern. `pop(0)` is O(n) because every
    element after index 0 shifts left, so draining n items is O(n^2)."""
    q = []
    out = []
    for op in ops:
        if op[0] == "enq":
            q.append(op[1])
        else:
            out.append(q.pop(0))
    return out
# endregion

Scratch vs library

Now the full face-off, with the anti-pattern added back in. Our queue and the deque are both O(1) per operation, so their lines stay flat and low. The list.pop(0) line is the lesson — it curves upward hard, because draining a list from the front is O(n²):

At 32000 items the library deque finished in about 2.2 ms, our linked queue in 12.5 ms, and the list anti-pattern in 52.5 ms. Our queue sits in the middle for the usual reason — it's O(1) like the deque, but every node is a separate Python object with pointer overhead and per-operation method calls, where the deque links blocks of elements in C. The real headline is the list line pulling away from both: that's a complexity-class gap, O(n²) against O(n), and it's the exact bug the warning above is about.

Where you'll actually meet it

Queues run the systems underneath your programs. The operating-system scheduler keeps processes in queues waiting for the CPU. Network routers queue packets; message brokers like RabbitMQ and Kafka are queues you rent by the month. The breadth-first search in the graph chapters is depth-first search with the stack swapped for a queue — that single swap is the difference between exploring nearest- first and deepest-first. And any producer/consumer setup — one thread making work, another doing it — is a queue between them. Whenever work must be served in the order it arrived, this is the structure.

Takeaways

A queue is FIFO — join the back, leave the front, both $O(1)$ — and a deque generalizes it to O(1) at both ends, which is why the deque is the one the standard library gives you and the primitive the stack and queue are carved from. Build any of them on a doubly linked list and the ends stay cheap; in Python, collections.deque is the tuned version to actually use.

The one thing to carry out of this chapter is the warning: a list is not a queue, because taking from its front is O(n). Reach for deque and popleft, and you'll never write the accidental-quadratic loop that catches everyone once. With stacks and queues in hand, you have both fundamental orderings; the next chapter looks at what happens when a queue has a fixed size and has to reuse its space — the ring buffer.