The Queue Data Structure: FIFO, Circular Buffers, and Why BFS Can't Live Without It

You need to process a stream of events in the order they arrived. Or traverse a tree level by level. Or spread rot across a grid of oranges, one minute at a time. Each time, the right tool is the same: the queue data structure. A line where first in means first out and nobody cuts.

This reference covers everything: the circular-buffer mechanics that make enqueue and dequeue genuinely O(1), the full/empty detection gotcha that trips up every homegrown implementation, why Python lists silently destroy queue performance, and how to recognize queue problems in the wild before you reach for the wrong tool.

The Contract

A queue is a sequence where insertions happen at one end (the back) and removals happen at the other end (the front). That is the entire contract. Everything else, the backing array, the linked-list blocks, the modulo arithmetic, is implementation detail.

Think of it as a pipe. Push work in at the right end. Pull results from the left end. Order is preserved. The contract is short. The implementation has exactly one surprise.

How It Works Internally

Option 1: Linked List

The naive approach backs a queue with a singly-linked list and keeps pointers to both the head node and the tail node. Enqueue appends a new node at the tail in O(1). Dequeue removes the head node in O(1). No shifting, no compaction.

Python's collections.deque does something more sophisticated. It uses a doubly-linked list of fixed-size blocks, where each block holds 64 object pointers. Python's engineers did not mail this one in. Reducing the overhead to one pair of prev/next links per block (rather than per element) also improves cache behavior compared to a classic node-per-element linked list.

The downside of any linked approach: each node allocates separately on the heap. With millions of items that means millions of allocations, significant GC pressure, and poor spatial locality.

Option 2: The Circular Buffer (Ring Buffer)

The circular buffer is the standard backing for high-performance queues. It allocates a contiguous fixed-size array and maintains two integer indices: head (where to dequeue next) and tail (where to enqueue next). Both start at 0.

Initial state:
 [ _ | _ | _ | _ | _ | _ | _ | _ ]
   ^
 head=0, tail=0, size=0

After enqueue A, B, C:
 [ A | B | C | _ | _ | _ | _ | _ ]
   ^       ^
 head=0  tail=3

After dequeue (removes A):
 [ _ | B | C | _ | _ | _ | _ | _ ]
       ^       ^
     head=1  tail=3

After enqueue D, E, F, G, H:
 [ _ | B | C | D | E | F | G | H ]
       ^                           ^
     head=1                      tail wraps to 0!

When tail reaches the end of the array, it wraps back to index 0 using modulo arithmetic:

tail = (tail + 1) % capacity
head = (head + 1) % capacity

This is the circular buffer. The array does not physically wrap. The indices do.

The dead space left behind by dequeued elements is reclaimed automatically as tail wraps around and fills those slots.

Circular buffer with head and tail pointers, showing the wrap-around arc head chases tail around the ring. The array stays put.

Why `head == tail` Is Ambiguous

There is one gotcha that bites every homegrown implementation: when head == tail, the queue could be empty (just created, or the last element was dequeued) or full (every slot is occupied and tail just caught up to head). You cannot tell from the indices alone. Genuinely diabolical.

Two standard solutions:

Keep a separate size counter. Increment on enqueue, decrement on dequeue. Empty when size == 0, full when size == capacity. Simple and common.
Sacrifice one slot. Treat the queue as full when (tail + 1) % capacity == head. This wastes one array slot but avoids the extra variable.

Most production implementations use the size counter.

Side-by-side empty vs full states both showing head == tail == 2 Same indices. Completely different states. Track size.

What Happens When It's Full

A fixed-capacity queue fails when it fills up. Dynamic queues double their array when full, copy existing elements into the new array (respecting head/tail positions), and reset head to 0 and tail to the old size.

The doubling strategy gives amortized O(1) enqueue. Say "amortized" when you explain this in an interview. They will appreciate it. The accounting argument: when you resize a capacity-n array, you copy n elements. But those n elements were each enqueued after the previous resize, so n enqueue operations paid for that one copy. Each enqueue pays a cost of 2 (one for itself, one amortized toward the next resize). The total cost per enqueue stays constant.

Resize cost timeline (capacity starting at 4):

cap 4  → full → copy 4 elements → cap 8
cap 8  → full → copy 8 elements → cap 16
cap 16 → full → copy 16 elements → ...

Total copies after N enqueues:
  4 + 8 + 16 + ... + N/2 < N
  (geometric series, sum < 2N)

Amortized cost per enqueue: O(1)

Core Operations

Operation	Time	Space	Notes
enqueue (push_back)	O(1) amortized	O(1)	O(n) on resize, but amortized O(1)
dequeue (pop_front)	O(1)	O(1)	Just advances head
peek / front	O(1)	O(1)	Read `array[head]` without removing
isEmpty	O(1)	O(1)	Check `size == 0` or `head == tail`
size	O(1)	O(1)	Maintained as counter
Build from n elements	O(n)	O(n)	Sequential enqueue

Dequeue is always O(1) because the circular buffer simply advances the head index. No element is moved or shifted. The old slot is logically freed and will be overwritten when tail wraps around to it.

Contrast this with a naive array queue that shifts elements on dequeue: O(n), and it will silently murder performance at scale. That is why list.pop(0) in Python is the wrong tool for queues. Python lists are backed by a contiguous array, so removing the first element shifts every remaining pointer one position forward. That is not a bug. It is the correct behavior of the wrong data structure for this job.

Implementations

from collections import deque

queue: deque = deque()

# Enqueue
queue.append("a")
queue.append("b")
queue.append("c")

# Dequeue
front = queue.popleft()   # "a"

# Peek
front = queue[0]          # "b"

# Size / empty check
size = len(queue)
is_empty = len(queue) == 0

Use collections.deque, never a plain list. list.pop(0) is O(n). deque.popleft() is O(1).

What Problems It Solves

Three use cases account for most queue problems in interviews. Know them cold.

Breadth-First Traversal. BFS on trees or graphs works by keeping a frontier of nodes to visit. You dequeue the current node, process it, and enqueue its unvisited neighbors. Because the queue preserves insertion order, you naturally visit all nodes at depth d before any node at depth d+1. Level-by-level traversal falls out for free.

Shortest path in unweighted graphs. BFS gives the shortest path from a source to every reachable node in an unweighted graph. The first time BFS reaches a node is the shortest path, because the queue guarantees you have explored all paths of length k before exploring any of length k+1. Dijkstra is overkill here. BFS with a queue is exact and simpler.

Streaming and pipeline work. Queues decouple producers from consumers. The producer enqueues work items as fast as it can. The consumer dequeues and processes them at its own rate. The queue absorbs the difference. This pattern underpins message brokers, background job systems, and event loops.

Recognizing the Queue Pattern in Interviews

These signals point toward a queue:

Process things in the order they arrive. If the problem says "handle events in order" or "simulate time steps in sequence," the queue models the timeline.
Layer-by-layer or wave-front expansion. "Find the minimum number of steps," "return nodes at each depth," "spread this effect one hop per round." If the problem mentions "each minute" or "each round," start sketching a queue before you finish reading the statement.
Multiple starting points that spread simultaneously. Multi-source BFS seeds the queue with all starting points before the first iteration. Every source spreads at the same rate.
You want the shortest path and the graph is unweighted. Dijkstra is overkill. BFS with a queue is exact and simpler.

Worked Example 1: Binary Tree Level Order Traversal

Problem: Given a binary tree, return the values of each level as a separate list.

Why a queue fits: you must visit all nodes at depth d before depth d+1. The queue holds the current frontier. When you process a node, you enqueue its children. The size of the queue at the start of each iteration tells you exactly how many nodes are on the current level.

from collections import deque
from typing import Optional

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def level_order(root: Optional[TreeNode]) -> list[list[int]]:
    if not root:
        return []
    result = []
    queue = deque([root])
    while queue:
        level_size = len(queue)
        level = []
        for _ in range(level_size):
            node = queue.popleft()
            level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        result.append(level)
    return result

The key insight: snapshotting len(queue) before the inner loop captures exactly the number of nodes at the current depth. Everything enqueued during this iteration belongs to the next level.

Binary tree with three color-coded levels showing the queue state at each step snapshot len(queue) at the start of each outer iteration. That number tells you the level width.

Worked Example 2: Rotting Oranges (Multi-Source BFS)

Problem: A grid contains 0 (empty), 1 (fresh orange), or 2 (rotten orange). Every minute, a rotten orange rots all adjacent fresh oranges. Return the minimum minutes until no fresh oranges remain, or -1 if impossible.

Why a queue fits: all rotten oranges spread simultaneously, one hop per minute. This is multi-source BFS. Seed the queue with every rotten orange before the first iteration. Each BFS level represents one minute.

from collections import deque

def oranges_rotting(grid: list[list[int]]) -> int:
    rows, cols = len(grid), len(grid[0])
    queue = deque()
    fresh = 0

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 2:
                queue.append((r, c, 0))  # (row, col, minutes)
            elif grid[r][c] == 1:
                fresh += 1

    if fresh == 0:
        return 0

    minutes = 0
    directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]

    while queue:
        row, col, time = queue.popleft()
        for dr, dc in directions:
            nr, nc = row + dr, col + dc
            if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
                grid[nr][nc] = 2
                fresh -= 1
                minutes = max(minutes, time + 1)
                queue.append((nr, nc, time + 1))

    return minutes if fresh == 0 else -1

The non-obvious part: seeding all rotten oranges into the queue before the first popleft is what makes spreading parallel. Miss this, and every candidate who gets it right beats you on runtime. If you BFS from each rotten orange separately, you over-count the minutes.

Three-step grid showing rot spreading from two sources simultaneously both wavefronts expand at the same rate because they share one queue, not two

Recap

A queue is FIFO: enqueue at the back, dequeue from the front.
Circular buffer backing gives O(1) amortized enqueue and O(1) dequeue by advancing a head index with modulo arithmetic.
The full/empty ambiguity (head == tail) is resolved with a size counter or by sacrificing one array slot.
Resize on overflow doubles the buffer. The amortized cost per enqueue stays O(1). Say "amortized."
Python list.pop(0) is O(n). Use collections.deque.popleft() instead.
Java: prefer ArrayDeque over LinkedList for better cache locality.
BFS is inseparable from the queue. Level-order, shortest path, and multi-source flood-fill all follow the same pattern: seed the queue, process level by level, enqueue neighbors.
The snapshot trick (level_size = len(queue) before the inner loop) separates BFS levels without a second queue.

If you want to feel the pressure of choosing the right tool in real time, SpaceComplexity runs voice-based mock interviews with rubric feedback. Find out whether you'd reach for a queue, or spend two minutes staring at the problem before reinventing a stack.

For related interview patterns, see how queues pair with BFS thinking in Stuck in a Coding Interview? Don't Go Silent. and how to communicate the tradeoffs once you have picked your structure in Technical Interview Communication: You Solved the Problem. So Why No Offer?