Queue

A queue is a FIFO (first-in, first-out) container with enqueue (add to back) and dequeue (remove from front). Use collections.deque in Python — O(1) at both ends. A list as a queue is O(n) per dequeue and a common performance bug.

Complexity

How it works

Backed by a circular buffer or doubly-linked list with head and tail pointers. Enqueue advances tail; dequeue advances head. Both are pointer-bumps, so O(1). Indexing or searching by value still requires a scan — O(n).

Python implementation

from collections import deque

q = deque()
q.append("a")          # enqueue
q.append("b")
q.append("c")
print(q.popleft())     # "a"  — dequeue, O(1)
print(q.popleft())     # "b"


# DON'T do this — list.pop(0) is O(n):
# q = []
# q.append("a"); q.pop(0)   # shifts every remaining element


# Explicit class:
class Queue:
    def __init__(self):
        self._d = deque()
    def enqueue(self, x):  # O(1)
        self._d.append(x)
    def dequeue(self):     # O(1)
        if not self._d:
            raise IndexError("dequeue from empty queue")
        return self._d.popleft()
    def peek(self):        # O(1)
        return self._d[0]
    def __len__(self):
        return len(self._d)

Trade-offs

• O(1) enqueue and dequeue with deque; O(n) per dequeue with list — always reach for deque.
• FIFO order is what BFS, task queues, and producer/consumer pipelines need.
• Variants: queue.Queue (thread-safe), asyncio.Queue (async), multiprocessing.Queue (cross-process).
• Priority queues use a heap, not a queue — see heapq.

← Back to Algorithms