Queue

A queue is a linear collection enforcing FIFO order: First In, First Out — the oldest element is always the next to leave. Insertion (enqueue) happens at the rear; removal (dequeue) and inspection (peek/front) happen at the front. All four operations run in O(1). Queues are the data-structure twin of Breadth-First Search and the universal primitive for fair scheduling — task buffers, request queues, producer-consumer pipelines, page-replacement policies. The implementation choice (circular buffer vs linked list vs two-stack trick) makes a 100×–1000× performance difference in tight loops, and the Python-specific gotcha — never use list.pop(0) — is one of the costliest performance bugs a beginner can ship.

1. Intuition — The Ticket Counter Line

A movie theater ticket counter. Patrons join the back of the line and are served from the front. The first to arrive is the first to be served — the queue enforces temporal fairness. If you tried to serve from the back, the people who arrived later would jump ahead of those who waited longer; if you tried to add at the front, you’d be cutting the line. Both ends have a fixed role, and the role is preserved over the lifetime of the queue.

A second mental model: a print queue. Documents are submitted to a printer in some order; the printer processes them one at a time in arrival order. Submission is fast (just append to the queue); processing is slow (the print itself); the queue exists to decouple the rate of arrivals from the rate of service. That decoupling — the absorption of bursts — is why queues appear everywhere in real systems: thread pools, message brokers, OS scheduler run-queues, network packet buffers.

The deep reason FIFO is the right discipline for fairness: no element ever overtakes one that arrived earlier. In ordering theory this is called non-preemptive. Under FIFO, the maximum waiting time of an element is bounded by the time it takes to drain everything ahead of it — an analyzable property exploited in queueing theory (Kendall’s notation, Little’s Law) to predict latency in real systems.

2. Tiny Worked Example — Hot Potato (Round-Robin)

Five children sit in a circle and pass a hot potato. Every time the music stops (every 3 passes), the child holding the potato is eliminated. Last child remaining wins. We can model this with a queue of children’s names: dequeue the front, enqueue them at the back (they “pass” the potato), repeat 3 times, then dequeue and discard (eliminated). Continue until the queue has one element.

Initial: ['A', 'B', 'C', 'D', 'E'], count = 3.

Round	Queue (front→back)	Action
1	A B C D E	dequeue A, enqueue → B C D E A
1	B C D E A	dequeue B, enqueue → C D E A B
1	C D E A B	dequeue C, do NOT enqueue → eliminated
2	D E A B	dequeue D, enqueue → E A B D
2	E A B D	dequeue E, enqueue → A B D E
2	A B D E	dequeue A, eliminated
3	B D E	dequeue B, enqueue → D E B
3	D E B	dequeue D, enqueue → E B D
3	E B D	dequeue E, eliminated
4	B D	dequeue B, enqueue → D B
4	D B	dequeue D, enqueue → B D
4	B D	dequeue B, eliminated
done	D	winner

This is a faithful queue-only solution to the Josephus problem special case. Notice every operation is dequeue (front) or enqueue (back) — never indexing into the middle. That’s the discipline.

3. Pseudocode

Queue ADT:
    enqueue(x):    insert x at the back              O(1)
    dequeue():     remove and return front element   O(1), undefined if empty
    peek()/front(): return front without removing    O(1)
    is_empty():    true iff size == 0                O(1)
    size():        number of elements                O(1)

The “all four are O(1)” promise is what differentiates a real queue from “a list someone calls a queue.” When you see pop(0) on a Python list, you don’t have a queue — you have a buggy queue.

4. Python Implementations

4.1 Idiomatic — collections.deque

from collections import deque
 
q: deque[int] = deque()
q.append(3)        # enqueue at the back
q.append(7)
q.append(1)
front = q[0]       # peek → 3
x = q.popleft()    # dequeue → 3
empty = not q      # False

collections.deque is the canonical Python queue. Both append (right) and popleft (left) are O(1) — guaranteed by the CPython documentation. Internally deque is implemented as a doubly-linked list of fixed-size blocks (typically 64 elements per block in CPython); enqueue and dequeue allocate or free a block only when one fills or empties, so amortized cost is dominated by simple pointer arithmetic plus occasional block allocation. This block-list structure also gives deque good cache locality within each block while keeping both ends mutable in true O(1).

4.2 The Wrong Way — list.pop(0)

q = []
q.append(3)
q.append(7)
q.append(1)
x = q.pop(0)        # ← O(n), DO NOT DO THIS

list.pop(0) is O(n): every remaining element must shift down by one slot in the underlying array buffer. For a queue of n = 10⁶ elements, processing all of them via pop(0) is ~10¹² element-shift operations — minutes of CPU on a problem that should take milliseconds. This is the classic Python performance trap. The bug compiles, runs, and gives correct answers; it’s just thousands of times slower than a deque. See §7.1 Pitfalls.

4.3 Class Wrapper

from collections import deque
from typing import Generic, TypeVar
T = TypeVar("T")
 
class Queue(Generic[T]):
    def __init__(self) -> None:
        self._dq: deque[T] = deque()
 
    def enqueue(self, x: T) -> None:
        self._dq.append(x)
 
    def dequeue(self) -> T:
        if not self._dq:
            raise IndexError("dequeue from empty queue")
        return self._dq.popleft()
 
    def peek(self) -> T:
        if not self._dq:
            raise IndexError("peek on empty queue")
        return self._dq[0]
 
    def is_empty(self) -> bool:
        return not self._dq
 
    def __len__(self) -> int:
        return len(self._dq)

4.4 Thread-Safe — queue.Queue

For multi-threaded producer-consumer code, queue.Queue is thread-safe and implements blocking semantics — get() waits until an element is available, put() waits when bounded and full. Internally it wraps a deque plus locks and condition variables. Use it only when you actually have multiple threads; the lock overhead per operation is significant compared to a bare deque.

For multi-process settings (separate Python interpreters), use multiprocessing.Queue, which uses pipes and OS-level synchronization.

4.5 Other Languages — Quick Reference

• Java: ArrayDeque<T> is the recommended single-threaded queue (also recommended over Stack). For thread-safe variants: LinkedBlockingQueue, ArrayBlockingQueue, ConcurrentLinkedQueue.
• C++: std::queue<T> is a container adaptor over std::deque<T> by default. Use push/pop/front/back.
• Go: no built-in; idiomatic patterns use a slice (with the pop(0) shift-cost problem) for small queues, or a custom linked list / circular buffer for large ones. Channels (chan T) are the concurrency-safe primitive but they’re more than queues — they synchronize.

5. Implementations Under the Hood

5.1 Circular Buffer (Array-Backed Fixed-Capacity Queue)

A circular buffer is a fixed-size array buf[0..capacity-1] with two indices, head (front) and tail (rear), and a count. Enqueue writes to buf[tail]; tail advances modulo capacity. Dequeue reads buf[head]; head advances modulo capacity. The “circular” comes from the modular arithmetic: when tail or head wraps past capacity - 1, it returns to 0, reusing the cells freed by past dequeues.

class CircularQueue:
    def __init__(self, capacity: int) -> None:
        self._buf: list = [None] * capacity
        self._capacity = capacity
        self._head = 0
        self._tail = 0
        self._size = 0
 
    def enqueue(self, x) -> None:
        if self._size == self._capacity:
            raise OverflowError("queue is full")
        self._buf[self._tail] = x
        self._tail = (self._tail + 1) % self._capacity
        self._size += 1
 
    def dequeue(self):
        if self._size == 0:
            raise IndexError("dequeue from empty queue")
        x = self._buf[self._head]
        self._buf[self._head] = None        # release reference for GC
        self._head = (self._head + 1) % self._capacity
        self._size -= 1
        return x

Pros. Excellent cache locality (contiguous memory, no per-node allocation). Constant-time per operation with no amortization wiggle. Bounded memory — useful in embedded systems and lock-free queue designs.

Cons. Fixed capacity. To grow, you must reallocate and copy (either ad-hoc or by using a “double when full” geometric strategy that re-introduces amortization). Distinguishing “full” from “empty” requires either tracking size separately or sacrificing one cell so that head == tail is unambiguously empty.

LeetCode 622 (“Design Circular Queue”) asks you to implement exactly this. Real-world circular buffers also underlie the kernel’s kfifo (Linux kernel lib/kfifo.c), the audio ring buffer in PortAudio/JACK, and the lockfree single-producer-single-consumer queues used in trading systems.

5.2 Linked List Backing (Singly Linked, Two Pointers)

Maintain a head pointer (front) and a tail pointer (back), with each node holding value and next. enqueue appends a node at tail and advances tail; dequeue reads the head and advances head. Both are O(1) worst-case, and the queue can grow without bound (subject to memory).

This is what a Singly Linked List looks like when both ends are exposed. The trade-offs are identical to those discussed for Stack § 5.2 — pointer stability and unbounded growth at the cost of cache locality and per-node overhead.

5.3 Two-Stack Queue (LeetCode 232)

A clever construction that simulates a queue using two stacks inbox and outbox. Enqueues push onto inbox. Dequeues pop from outbox; if outbox is empty, first transfer everything from inbox to outbox (which reverses the order, putting the oldest on top of outbox).

class QueueViaStacks:
    def __init__(self) -> None:
        self._inbox: list = []
        self._outbox: list = []
 
    def enqueue(self, x) -> None:
        self._inbox.append(x)
 
    def dequeue(self):
        if not self._outbox:
            while self._inbox:
                self._outbox.append(self._inbox.pop())
        if not self._outbox:
            raise IndexError("dequeue from empty queue")
        return self._outbox.pop()

Amortized analysis. Each element is moved from inbox to outbox at most once, then popped from outbox at most once — three constant-time operations across its entire lifetime in the queue. Across n enqueues and n dequeues, total work is O(n), so amortized O(1) per operation. Worst-case a single dequeue can be O(n) (when it triggers a full transfer); for real-time guarantees this isn’t a queue you want, but for amortized-bound interview problems it’s a beautiful construction. The dual problem — Stack via Queues (LC 225) — exists too but is a less natural construction.

6. Complexity

Operation	Circular buffer	Linked list	collections.deque	list (append + pop(0))
enqueue	O(1)	O(1)	O(1) amortized	O(1) amortized
dequeue	O(1)	O(1)	O(1)	O(n) ← BUG
peek	O(1)	O(1)	O(1)	O(1)
is_empty	O(1)	O(1)	O(1)	O(1)

Space: O(n) for n elements; circular buffer has fixed allocation, linked list pays per-node header overhead, deque pays per-block overhead.

The “amortized” qualifier on deque enqueue covers the rare case when CPython needs to allocate a new internal block (every ~64 elements, by default).

7. Pitfalls

7.1 The list.pop(0) Trap (Python-Specific Disaster)

This is the queue pitfall that costs the most production-debugging time. Symptoms:

# Looks reasonable. Compiles. Runs. Gives correct answers.
q = []
for task in stream_of_tasks:        # n = 10⁶ tasks
    q.append(task)
    if some_condition:
        next_task = q.pop(0)        # ← silent O(n) every time
        process(next_task)

The code “works” in the unit-test sense, but as n grows, runtime explodes quadratically. A naive Breadth-First Search using q.pop(0) on a 10⁶-node graph will appear to hang for tens of minutes when it should run in milliseconds. Diagnosis is hard: profilers correctly identify pop as the hot spot, but the fix (“use deque”) is non-obvious to engineers who think “a Python list is a queue.”

The fix is one line: from collections import deque; q = deque() then q.popleft(). This is the single most important Python performance correction for queue code.

The cost ratio at n = 10⁶: list-based ~ 10¹² element shifts; deque-based ~ 10⁶ pointer moves. A factor of 10⁶ — six orders of magnitude. Any time a Python program is “mysteriously slow” and somewhere a queue is in play, check for pop(0) first.

Why Python doesn't optimize pop(0) automatically

Python’s list is required to be a contiguous array (the C API exposes PyListObject->ob_item as a PyObject **). Making pop(0) O(1) would require a different layout (a circular buffer or linked structure), which would break the contract that &list[i] is a stable pointer for all i between calls. The fix is structural — use deque — not magical.

7.2 Confusing Queue with Stack

LIFO vs FIFO. Breadth-First Search needs a queue; Depth-First Search needs a Stack. Replacing one with the other in a graph traversal silently changes the algorithm — sometimes correct (BFS and DFS both produce some spanning tree, just different ones), often catastrophic (BFS produces shortest paths in unweighted graphs; DFS does not).

7.3 Empty-Queue Dequeue/Peek

Both raise; guard with if q:. In a multithreaded context, queue.Queue.get() blocks by default — different semantics than the data-structure-level “raise on empty.”

7.4 Capacity Confusion in Bounded Queues

queue.Queue(maxsize=N) blocks producers when full and consumers when empty. If you forget the maxsize argument, you get an unbounded queue and silently leak memory under producer-consumer rate mismatch. Always set a sensible bound for production message queues.

7.5 Iterating While Mutating

for x in q:           # iterates from front to back
    if some_condition(x):
        q.popleft()   # ← mutates while iterating; undefined behavior

Iterate by draining: while q: x = q.popleft(); ....

7.6 Off-By-One in Circular Buffer Implementation

A common bug: using (head == tail) to mean “empty” without separately tracking size means you can’t distinguish empty from full (both states have head == tail). Solutions: (a) maintain an explicit size counter, or (b) sacrifice one buffer cell so tail can never catch up to head from behind — full is then (tail + 1) % capacity == head.

7.7 Reference Leakage in Circular Buffer

After dequeue, the cell still holds the reference. In a garbage-collected language, that prevents the dequeued object from being collected. Always set buf[head] = None (or null) after read to release the reference.

7.8 deque Random Indexing

deque[i] for general i (not the ends) is O(n), not O(1) — block-list traversal. If you need O(1) random access and queue semantics, you need either a different data structure or a circular buffer with explicit indexing. The CPython documentation says: “Indexed access is O(1) at both ends but slows to O(n) in the middle.”

8. Diagram — Circular Buffer Wrap-Around

flowchart TD
    subgraph t0["t = 0: empty (head = tail = 0)"]
        A0["[ _ , _ , _ , _ , _ ]\n  ↑\nhead, tail"]
    end
    subgraph t1["t = 1: enq A, B, C"]
        A1["[ A , B , C , _ , _ ]\n  ↑       ↑\n head    tail"]
    end
    subgraph t2["t = 2: deq → A; enq D, E, F (wraps)"]
        A2["[ F , B , C , D , E ]\n  ↑   ↑\n tail head"]
    end
    subgraph t3["t = 3: deq → B"]
        A3["[ F , _ , C , D , E ]\n  ↑       ↑\n tail    head"]
    end
    t0 --> t1
    t1 --> t2
    t2 --> t3

What this diagram shows. Four snapshots of a circular-buffer queue with capacity 5 across an enqueue/dequeue sequence. The arrows point at the head (next-to-dequeue position) and tail (next-to-enqueue position) within the array. At t = 2 the buffer has wrapped: after dequeueing A and enqueueing four more elements, tail has wrapped from index 5 back to index 0 to reuse the cell that A vacated, and the queue contains B, C, D, E, F in logical order even though they are stored as F, B, C, D, E in the array. Tracking the head/tail cursors is what makes this storage layout look like a FIFO from the outside while preserving O(1) operations and a fixed memory footprint.

9. Common Interview Problems

#	Problem	Queue Role
LC 622	Design Circular Queue	Direct circular-buffer implementation
LC 232	Implement Queue using Stacks	Two-stack amortized construction
LC 225	Implement Stack using Queues	Dual problem (less natural)
LC 933	Number of Recent Calls	Sliding-window queue (drop old timestamps)
LC 346	Moving Average from Data Stream	Fixed-size queue + running sum
LC 102	Binary Tree Level Order Traversal	BFS with a queue
LC 199	Binary Tree Right Side View	BFS, take last per level
LC 994	Rotting Oranges	Multi-source BFS via queue
LC 542	01 Matrix	Multi-source BFS distance
LC 1091	Shortest Path in Binary Matrix	BFS shortest path
LC 207	Course Schedule	Topological Sort, Kahn’s algorithm uses a queue
LC 752	Open the Lock	BFS with a queue + visited set
LC 950	Reveal Cards In Increasing Order	Reverse-simulate a queue
LC 1670	Design Front Middle Back Queue	Two deques

10. Open Questions

• What is the exact growth/block-allocation strategy of CPython deque? Documentation says O(1) on both ends but doesn’t pin down the constant; profiling under sustained churn would clarify.
• When does the two-stack queue (amortized O(1)) lose to a real linked-list queue (worst-case O(1)) in practice? Any benchmarks isolating worst-case-latency-sensitive workloads?
• How do lock-free MPMC (multi-producer-multi-consumer) queues — Vyukov’s, Michael-Scott’s — relate to the data-structure-level queue presented here? They’re the same ADT but with vastly different concurrent semantics.

11. See Also

• Stack — the LIFO sibling
• Deque — the double-ended generalization; what collections.deque actually is
• Breadth-First Search — the canonical queue-driven traversal
• 01-BFS — uses a deque, but conceptually a queue with priority short-circuits
• Multi-Source BFS — multiple seeds enqueued simultaneously
• Topological Sort — Kahn’s algorithm uses a queue of zero-indegree nodes
• Singly Linked List — common backing for linked-list queues
• Big-O Notation — for the amortized claims
• SWE Interview Preparation MOC