Queue Data Structure in Python: deque vs list.pop(0)

A queue is the data structure of waiting in line: items join at the back and leave from the front, so the oldest one is always served first. It is also the structure behind breadth-first search, task schedulers, print spoolers and message brokers. The idea fits in one sentence; the interview questions are about the implementation, because the most obvious one in Python, a list with pop(0), quietly turns a linear algorithm into a quadratic one.

The problem it solves

Anything that must be processed in arrival order needs a queue:

• Breadth-first search explores nodes in the order they were discovered, which is what makes it find shortest paths in unweighted graphs.
• Work queues hand jobs to workers fairly, oldest first.
• Buffers absorb bursts between a fast producer and a slower consumer.

The contract is three operations, all expected to be O(1): enqueue at the back, dequeue from the front, and peek at the front without removing it. The difference from a stack is only which end things leave from: a stack is last in, first out.

The intuition

A Python list is a dynamic array: its items sit in one contiguous block, and index 0 must always be the first slot. Appending at the end is cheap. Removing the first item is not, because every item behind it must slide down one slot to close the gap. Draining a queue of n items with pop(0) performs (n - 1) + (n - 2) + ... + 1 = n(n - 1) / 2 moves, which is O(n²).

collections.deque is built for two open ends. CPython stores it as a doubly linked list of fixed-size blocks, so removing from the front just advances a marker; nothing behind it moves. Both append and popleft are O(1), and so are their mirror images appendleft and pop.

A queue from scratch needs the same property. The classic interview version is a singly linked list with a head pointer for dequeues and a tail pointer for enqueues. The one line people forget: when the last item leaves, the tail must be reset too.

Watch it run

The animation stores the lesson's print jobs two ways, a deque on top and a list below. Three print jobs; items join at the back and must leave from the front. append("job4") adds a fourth job at the back, where it waits behind all three, however urgent it feels, and that is cheap in both. q[0] peeks at the front: job1, the oldest, because arrival order is service order. Then both containers hand out job1; watch what happens to everything behind it. popleft() just moves the deque's front marker, so job2, job3 and job4 never move: O(1). list.pop(0) had to slide three elements down a slot, and on a thousand-job queue that is a thousand moves. The second popleft() returns job2 and the deque's front simply steps right again, while the list's shift counter climbs to five. The closing frame: two open ends, one direction of travel, and O(1) at both of them, which is the reason to reach for collections.deque.

The code

The lesson's jobs, a timing comparison printed as a comparison (the absolute times depend on the machine), and the maxlen trap:

from collections import deque
import time

q = deque()
for job in ("job1", "job2", "job3", "job4"):
    q.append(job)                                   # enqueue at the back
print(q[0], q.popleft(), q.popleft(), list(q))      # job1 job1 job2 ['job3', 'job4']

def drain(make, n):
    """Enqueue n items, then dequeue them all from the front; return seconds taken."""
    start = time.perf_counter()
    items = make()
    for i in range(n):
        items.append(i)
    if isinstance(items, deque):
        while items:
            items.popleft()
    else:
        while items:
            items.pop(0)                            # every call shifts the rest down a slot
    return time.perf_counter() - start

n = 40_000
t_list, t_deque = drain(list, n), drain(deque, n)
print(t_list > 5 * t_deque)                         # True  (exact times depend on the machine)

# Pitfall: a deque with maxlen is a sliding window, not a bounded queue.
recent = deque(maxlen=3)
for event in ["a", "b", "c", "d", "e"]:
    recent.append(event)                            # when full, the OLDEST is silently dropped
print(list(recent))                                 # ['c', 'd', 'e']

On the machine these outputs were produced on, the list took about 35 times as long as the deque at 40,000 items, and the gap widens with n. A queue from scratch, and queue.Queue, the version for threads, whose bound makes a producer wait instead of losing data:

class LinkedQueue:
    """A queue from scratch: a singly linked list with a head and a tail pointer."""
    class _Node:
        __slots__ = ("value", "next")
        def __init__(self, value):
            self.value, self.next = value, None

    def __init__(self):
        self.head = self.tail = None
        self.size = 0

    def enqueue(self, value):                       # O(1): link after the tail
        node = self._Node(value)
        if self.tail:
            self.tail.next = node
        else:
            self.head = node
        self.tail = node
        self.size += 1

    def dequeue(self):                              # O(1): unlink the head
        if self.head is None:
            raise IndexError("dequeue from an empty queue")
        node = self.head
        self.head = node.next
        if self.head is None:
            self.tail = None                        # the forgotten line: empty again
        self.size -= 1
        return node.value

    def peek(self):
        if self.head is None:
            raise IndexError("peek at an empty queue")
        return self.head.value

lq = LinkedQueue()
for job in ("job1", "job2"):
    lq.enqueue(job)
print(lq.dequeue(), lq.dequeue(), lq.size, lq.tail)   # job1 job2 0 None
lq.enqueue("job3")
print(lq.peek(), lq.head is lq.tail)                  # job3 True

import queue
jobs = queue.Queue(maxsize=2)                       # the thread-safe one, with a real bound
jobs.put("a")
jobs.put("b")
try:
    jobs.put_nowait("c")                            # put() would block here until a get()
except queue.Full:
    print("full: the producer has to wait")         # full: the producer has to wait

Checked on 2,000 seeded random sequences of enqueues and dequeues, including dequeues from an empty queue, against deque and against a brute force list with pop(0):

import random

rng = random.Random(30)
ok = True
for _ in range(2_000):
    mine, ref, lst = LinkedQueue(), deque(), []
    for _ in range(rng.randint(0, 60)):
        op = rng.random()
        if op < 0.55:
            x = rng.randint(0, 99)
            mine.enqueue(x)
            ref.append(x)
            lst.append(x)
        elif ref:
            a, b, c = mine.dequeue(), ref.popleft(), lst.pop(0)   # brute force: list.pop(0)
            ok &= a == b == c
        else:
            try:
                mine.dequeue()
                ok = False                          # an empty queue must refuse
            except IndexError:
                pass
        ok &= mine.size == len(ref) and (mine.head is None) == (mine.tail is None)
        if ref:
            ok &= mine.peek() == ref[0] and mine.tail.value == ref[-1]
print(ok)                                           # True

The complexity

• deque: append, popleft, appendleft, pop are O(1). Indexing the middle, q[i], is O(n); a deque is not a random-access array.
• list as a queue: append is amortised O(1), pop(0) and insert(0, x) are O(n), so draining n items is O(n²).
• Linked-list queue: O(1) per operation, with one node allocation per item.
• Space: O(n) for all of them. The big-O cheat sheet lists queue and deque operations next to the other structures.

Where it goes wrong

• list.pop(0) in a BFS loop. Correct output, quadratic time; it shows up only on big inputs.
• deque(maxlen=k) as a bounded queue. When it is full, append silently drops the oldest item. For backpressure use queue.Queue(maxsize=k), which blocks.
• Forgetting to reset the tail. After the last dequeue, a stale tail makes the next enqueue link onto a detached node, and the item vanishes.
• Sharing a plain deque between threads for coordination. Single append and popleft calls are thread-safe in CPython, but "check if empty, then pop" is not atomic. queue.Queue gives blocking get and put.

When it shows up in interviews

Directly as "implement a queue", often with a twist: with two stacks, or as a fixed-size ring buffer. Indirectly, every breadth-first search runs on one, the sliding window maximum uses a deque from both ends, and a priority queue replaces arrival order with a key.

How to say it in an interview

"A queue is first in, first out: enqueue at the back, dequeue from the front, both O(1). In Python I'd use collections.deque, because list.pop(0) shifts every remaining element and makes a drain quadratic. If I have to build one, it's a linked list with head and tail pointers, and dequeue resets the tail when the queue becomes empty. Between threads I'd use queue.Queue with a maxsize, so a full queue makes the producer wait instead of dropping or growing without bound."