Queues Explained

A queue is a data structure that lines elements up in the order they arrive and lets them go in that same order — first in, first out (FIFO). Picture a line at a coffee shop: the person who joined first is served first, and everyone else waits their turn behind them. Queues show up constantly in real software: task schedulers, print spoolers, message brokers, and — most famously in algorithms — breadth-first search. This lesson covers how queues work under the hood, how to implement and use them correctly in Python, and the performance traps that catch beginners off guard.

Overview: How Queues Work

A queue supports two core operations: enqueue (add an element to the back) and dequeue (remove the element from the front). Everything else — checking the front element (peek), checking whether the queue is empty, checking its size — is a convenience built on top of those two. The defining rule is FIFO: whichever element has been waiting longest is the next one out. This is the opposite of a stack, which is LIFO (last in, first out) and pops whatever was pushed most recently.

Back to the coffee shop line: a new customer always joins at the back of the line (enqueue), and the barista always serves the customer at the front (dequeue). No one cuts in line and no one leaves from the middle — that ordering guarantee is exactly what makes a queue useful: it models “process things in the order they arrived.”

In Python, the tempting first instinct is to use a plain list as a queue: call append to enqueue and pop(0) to dequeue. This produces the correct FIFO behavior, but it is a performance trap covered in detail below. The standard library ships a purpose-built structure for this, collections.deque (“deck”, short for double-ended queue), which supports fast additions and removals from both ends. For queues, real Python code should almost always reach for deque rather than a list.

Under the hood, deque is implemented as a doubly linked list of fixed-size blocks (not one node per element, for cache efficiency), so it can add or remove elements at either end in constant time without shifting anything. A plain Python list, by contrast, is backed by one contiguous array — appending to the end is O(1) amortized because there is usually spare capacity there, but removing from the front means every remaining element has to shift left by one slot, which costs O(n).

Two other queue variants are worth knowing by name. A circular queue (or ring buffer) uses a fixed-size array and wraps its front/rear indices around with modulo arithmetic, giving O(1) operations without the overhead of a linked structure — useful whenever you know a hard capacity limit in advance (a fixed-size event buffer, a sliding window of recent readings). A priority queue is a different structure entirely: elements come out in priority order rather than arrival order, typically implemented with a heap via Python’s heapq module. It has its own lesson, but it is worth remembering now that a “priority queue” is not FIFO at all, despite the name.

Time and Space Complexity

The complexity of queue operations depends entirely on which implementation backs them. The table below compares the three approaches discussed above, where n is the number of elements currently in the queue.

Operation	Plain list (append / pop(0))	collections.deque	Circular array (fixed capacity)
Enqueue (add to rear)	O(1) amortized	O(1)	O(1)
Dequeue (remove front)	O(n)	O(1)	O(1)
Peek front	O(1)	O(1)	O(1)
Search for a value	O(n)	O(n)	O(n)
Space (n elements)	O(n)	O(n)	O(capacity), fixed

The reason list.pop(0) is O(n): a Python list stores its elements in one contiguous block of memory, so removing the element at index 0 leaves a gap at the start, and Python must shift every remaining element down by one position to close it. Do that inside a loop over n elements and you pay O(n) work per dequeue — O(n²) total — a common accidental performance bug that produces correct output but scales terribly. deque.popleft() avoids this entirely, because a deque is organized as a chain of blocks with pointers to both ends; removing from either end just moves a pointer, with no shifting required. A well-implemented circular queue gets the same O(1) guarantee using a plain array by tracking a front index and moving it forward (wrapping with % capacity) instead of physically deleting and shifting elements.

Space complexity for a queue holding n elements is O(n) in every case — you’re storing the elements plus a small constant amount of bookkeeping (a couple of index pointers, or block metadata for a deque). A circular queue has one extra practical property: its space is fixed at O(capacity) no matter how many enqueue/dequeue cycles happen, since it reuses the same underlying array. collections.deque even exposes this directly — pass maxlen=n and it behaves like a fixed-capacity ring buffer, silently dropping the oldest element once it’s full.

Examples

Example 1: Basic enqueue and dequeue with deque

This is the everyday pattern: append to enqueue, popleft to dequeue, and index [0] to peek at the front without removing it.

from collections import deque

def demo_basic_queue() -> None:
    queue: deque[str] = deque()
    queue.append("Alice")
    queue.append("Bob")
    queue.append("Charlie")
    print("Queue after enqueues:", list(queue))

    first_served = queue.popleft()
    print("Served:", first_served)
    print("Queue after one dequeue:", list(queue))
    print("Next to be served:", queue[0])


demo_basic_queue()

Output:

Queue after enqueues: ['Alice', 'Bob', 'Charlie']
Served: Alice
Queue after one dequeue: ['Bob', 'Charlie']
Next to be served: Bob

Three names are enqueued in order, so the queue holds ['Alice', 'Bob', 'Charlie'] with Alice at the front. popleft() removes and returns Alice, since she has been waiting the longest, leaving ['Bob', 'Charlie']. Indexing with queue[0] peeks at Bob — the next customer in line — without removing him.

Example 2: Breadth-first search with a queue

Queues are the engine behind breadth-first search (BFS): visit a starting node, then visit all of its unvisited neighbors before moving one level further out. A set tracks which nodes have already been queued so none are processed twice — checking membership with in on a set is O(1) on average, versus O(n) if a list were used for visited instead.

from collections import deque

def bfs(graph: dict[str, list[str]], start: str) -> list[str]:
    visited: set[str] = {start}
    order: list[str] = []
    queue: deque[str] = deque([start])

    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

    return order


graph = {
    "A": ["B", "C"],
    "B": ["A", "D"],
    "C": ["A", "D"],
    "D": ["B", "C", "E"],
    "E": ["D"],
}

result = bfs(graph, "A")
print("BFS order:", result)

Output:

BFS order: ['A', 'B', 'C', 'D', 'E']

Starting from A, the queue holds [A]. Popping A visits its neighbors B and C, enqueuing both — queue becomes [B, C]. Popping B finds neighbor A already visited and enqueues the new neighbor D — queue becomes [C, D]. Popping C finds both neighbors already visited or queued, so nothing new is added — queue becomes [D]. Popping D enqueues its only new neighbor, E. Popping E finds D already visited, and the queue empties, ending the traversal in the order A, B, C, D, E — nodes closest to the start come out first, which is exactly what BFS guarantees.

Example 3: A circular queue built from scratch

To see why a fixed-size array can still give O(1) enqueue/dequeue, here is a minimal circular queue. Instead of shifting elements when the front is removed, it just moves a front index forward and wraps it back to 0 with the modulo operator once it reaches the end of the array.

class CircularQueue:
    def __init__(self, capacity: int) -> None:
        self.capacity = capacity
        self.items: list = [None] * capacity
        self.front = 0
        self.size = 0

    def is_empty(self) -> bool:
        return self.size == 0

    def is_full(self) -> bool:
        return self.size == self.capacity

    def enqueue(self, value: int) -> None:
        if self.is_full():
            raise OverflowError("Queue is full")
        rear = (self.front + self.size) % self.capacity
        self.items[rear] = value
        self.size += 1

    def dequeue(self) -> int:
        if self.is_empty():
            raise IndexError("Queue is empty")
        value = self.items[self.front]
        self.items[self.front] = None
        self.front = (self.front + 1) % self.capacity
        self.size -= 1
        return value


def demo_circular_queue() -> None:
    queue = CircularQueue(3)
    queue.enqueue(10)
    queue.enqueue(20)
    queue.enqueue(30)
    print("Dequeued:", queue.dequeue())
    queue.enqueue(40)
    print("Dequeued:", queue.dequeue())
    print("Dequeued:", queue.dequeue())
    print("Dequeued:", queue.dequeue())


demo_circular_queue()

Output:

Dequeued: 10
Dequeued: 20
Dequeued: 30
Dequeued: 40

With capacity 3, enqueuing 10, 20, 30 fills the array to [10, 20, 30] with front = 0. Dequeuing returns 10 and advances front to 1, freeing one slot even though the array itself still has 20 and 30 sitting at indices 1 and 2. Enqueuing 40 computes rear = (1 + 2) % 3 = 0, so 40 is written into index 0 — the slot vacated by 10 — wrapping around the array. The remaining three dequeues return 20, 30, and 40 in order, proving the queue kept correct FIFO order even though the underlying array indices wrapped around.

How It Works Step by Step

The table below traces the exact same sequence of operations from Example 3, but shown purely from the logical “front → rear” view of the queue, ignoring the array indices underneath. This is the mental model you should carry regardless of which implementation is used.

Step	Operation	Queue (front → rear)	Returned
1	enqueue(10)	[10]	—
2	enqueue(20)	[10, 20]	—
3	enqueue(30)	[10, 20, 30]	—
4	dequeue()	[20, 30]	10
5	enqueue(40)	[20, 30, 40]	—
6	dequeue()	[30, 40]	20
7	dequeue()	[40]	30
8	dequeue()	[]	40

Notice that every dequeue() always removes whatever has been sitting in the queue the longest, regardless of when later elements were added — 10 comes out before 20 and 30 even though all three were enqueued before any dequeue happened. Whether that’s implemented with a linked structure (deque) or a wrapping array index (circular queue) is an implementation detail; the FIFO contract is what matters to code that uses the queue.

Common Mistakes

Mistake 1: Using a plain list with pop(0)

This code is logically correct — it produces the right FIFO order — but it silently does O(n) work on every single dequeue, turning what should be an O(n) algorithm into an O(n²) one as the queue grows.

queue = []
for i in range(5):
    queue.append(i)

served = []
while queue:
    served.append(queue.pop(0))

print(served)

Output:

[0, 1, 2, 3, 4]

The output is correct, which is exactly why this mistake is dangerous — it passes casual testing on small inputs and only shows up as a slowdown once the queue holds thousands of elements. The fix is to swap the list for a deque and use popleft() instead of pop(0):

from collections import deque

queue = deque()
for i in range(5):
    queue.append(i)

served = []
while queue:
    served.append(queue.popleft())

print(served)

Output:

[0, 1, 2, 3, 4]

Same output, but each popleft() is O(1) instead of O(n), so the whole loop is O(n) total instead of O(n²).

Mistake 2: Dequeuing without checking for an empty queue

Calling popleft() on an empty deque raises an IndexError at runtime — a common bug in producer/consumer or scheduling code where the queue can legitimately run dry.

from collections import deque

queue = deque()
next_item = queue.popleft()
print(next_item)

Output:

IndexError: pop from an empty deque

The fix is to check truthiness first — an empty deque is falsy, just like an empty list — and only pop when there’s something there:

from collections import deque

def safe_dequeue(queue: deque) -> int | None:
    if not queue:
        return None
    return queue.popleft()


queue: deque[int] = deque()
print(safe_dequeue(queue))
queue.append(99)
print(safe_dequeue(queue))

Output:

None
99

The first call finds an empty queue and returns None instead of crashing; after 99 is enqueued, the second call safely pops and returns it.

Best Practices

• Use collections.deque for queue behavior in Python — never list.pop(0) or list.insert(0, x), both of which are O(n) and quietly turn linear algorithms quadratic.
• Reach for queue.Queue only when you specifically need thread-safety for a producer/consumer pattern across multiple threads; for single-threaded code, deque is simpler and faster.
• Use a queue whenever you need to process items in arrival order: BFS and shortest-path-in-unweighted-graphs, level-order tree traversal, job/task scheduling, rate limiting, and simulation of real-world waiting lines.
• Use deque(maxlen=n) when you need a fixed-size rolling window (e.g. “last n log lines”, “last n sensor readings”) — it automatically evicts the oldest element for you.
• Always guard a dequeue with an emptiness check (if not queue) or a try/except IndexError — don’t assume the queue is non-empty just because it was non-empty a moment ago, especially in concurrent code.
• If elements need to come out by priority rather than arrival order, that’s a different structure — a priority queue built on heapq — not a plain FIFO queue.

Practice Exercises

1. Write reverse_first_k(queue: deque, k: int) -> deque that reverses the order of only the first k elements of a queue, leaving the rest in their original order, using only queue operations (append, popleft) plus a stack (a list used with append/pop). Test it on deque([1, 2, 3, 4, 5]) with k = 3; the expected result is deque([3, 2, 1, 4, 5]).
2. Simulate round-robin CPU scheduling. Given tasks [("A", 5), ("B", 3), ("C", 8)] as (name, remaining_time) pairs and a fixed time quantum of 4, use a deque to decide execution order: pop a task from the front, run it for up to the quantum, and if time remains, push it back onto the rear. Print the name of the task that runs on each turn until all tasks finish.
3. Use two pointers popped from opposite ends of a deque to check whether a word is a palindrome, without recursion. Test it on "racecar" (expected: True) and "queue" (expected: False).

Summary

• A queue is a FIFO (first-in, first-out) structure: elements come out in the same order they went in.
• Use collections.deque for queues in Python — append/popleft are O(1), while list.pop(0) is O(n) because it has to shift every remaining element.
• A circular (ring) buffer gives O(1) enqueue/dequeue with a fixed-size array by wrapping indices with modulo arithmetic; deque(maxlen=n) gives you this behavior built in.
• Queues power breadth-first search, task/job scheduling, print spoolers, rate limiting, and any “process in arrival order” system.
• Always guard against dequeuing from an empty queue — check truthiness or catch IndexError.
• Space complexity for any queue holding n elements is O(n); a well-chosen implementation keeps enqueue and dequeue at O(1), but a plain list misused as a queue silently degrades dequeue to O(n).