3.2 Queues: First In, First Out

Prerequisites: Choosing Arrays or Linked Lists, Stacks. This section begins with the FIFO contract, dissects the empty-full conditions of circular indexing, and examines how queues ensure BFS progresses level by level.

A Queue Honors Enqueue Order

First In, First Out (FIFO) means the earliest inserted element leaves first. An abstract data type that enforces this contract is a queue. It does not care which element feels urgent; cutting the line requires a separate priority contract.

A queue separates its two ends:

• The rear end accepts new elements; this operation is called enqueue;
• The front end removes the earliest-arriving element; this operation is called dequeue.

While a stack pushes and pops from the same end, a queue enters from one end and exits from the other. The difference lies in the public contract, not in the underlying implementation. Arrays, linked lists, and double-ended queues can all implement FIFO behavior.

Operations and Failure Contract

Operation	Meaning	Agreement when queue is empty or full
enqueue(x)	Add x to the end of the queue	Throw an exception, block, or return failure when the bounded queue is full
dequeue()	Remove and return front element	Throw exception or return null for empty queue
front()	Peek at the front, do not remove	Throw an exception or return null when the queue is empty
is_empty()	Whether there are no elements	Empty queue returns True
is_full()	Is the bounded queue full	Unbounded queues typically do not provide this semantics

"Bounded" is part of the interface. A network buffer might be fixed to hold at most N items; a dynamic queue in a typical application might expand as needed. The caller must know whether a full queue results in discarding, blocking, failure, or expansion.

Why Not Make the Left End of a Python List the Front of a Queue?

Python list.append(x) appends to the right end, and the amortized cost of consecutive operations is Θ(1). However, list.pop(0) deleting from the left end requires shifting all subsequent references forward, making each operation Θ(n).

A Python list can express FIFO, but deleting from its left end has a cost. When queue sizes remain small, this difference may not significantly impact performance. But when the queue grows or operations become frequent, it's better to use a container optimized for endpoint operations.

The Python standard library typically implements this as:

from collections import deque

jobs = deque(["job A", "job B"])
jobs.append("job C")
first = jobs.popleft()

assert first == "job A"
assert list(jobs) == ["job B", "job C"]

collections.deque supports appending and popping from both ends with near-O(1) performance. It also provides additional bidirectional operations, which will be fully detailed in the next section.

Circular Queue: Reusing Array Positions

Once an element leaves, its array slot should be reusable. Shifting every remaining element after each dequeue wastes that opportunity. A circular queue instead preserves two indices:

• head points to the current front of the queue;
• tail points to the next position where a new element will be written.

When either index reaches the end of the array, it wraps around to zero using modulo arithmetic:

next_index = (current_index + 1) % capacity

Below is an implementation of a fixed-capacity circular queue. It uses _size to distinguish between an empty and a full queue, so all capacity positions in the array are available.

from operator import index as integer_index

class CircularQueue:
    def __init__(self, capacity):
        capacity = integer_index(capacity)
        if capacity <= 0:
            raise ValueError("capacity must be positive")
        self._data = [None] * capacity
        self._capacity = capacity
        self._head = 0
        self._tail = 0
        self._size = 0

    def enqueue(self, item):
        if self.is_full():
            raise OverflowError("enqueue to full queue")
        self._data[self._tail] = item
        self._tail = (self._tail + 1) % self._capacity
        self._size += 1

    def dequeue(self):
        if self.is_empty():
            raise IndexError("dequeue from empty queue")
        value = self._data[self._head]
        self._data[self._head] = None
        self._head = (self._head + 1) % self._capacity
        self._size -= 1
        return value

    def front(self):
        if self.is_empty():
            raise IndexError("front from empty queue")
        return self._data[self._head]

    def is_empty(self):
        return self._size == 0

    def is_full(self):
        return self._size == self._capacity

    def to_list(self):
        return [
            self._data[(self._head + offset) % self._capacity]
            for offset in range(self._size)
        ]

    def __len__(self):
        return self._size

if __name__ == "__main__":
    queue = CircularQueue(4)
    for value in [1, 2, 3, 4]:
        queue.enqueue(value)
    print(f"After enqueue: {queue.to_list()}")

    print(f"Dequeue: {queue.dequeue()}")
    queue.enqueue(5)
    print(f"Wrap around: {queue.to_list()}")
    print(f"Queue is full: {queue.is_full()}")

    assert queue.front() == 2
    assert len(queue) == 4
    print("Queue check passed")

After enqueue: [1, 2, 3, 4]
Dequeue: 1
Wrap around: [2, 3, 4, 5]
Queue is full: True
Queue check passed

Manually Walk Through a Wrap-Around

With a capacity of 4, enqueue elements starting from 1, 2, 3, 4:

Moment	head	tail	size	Logical Order
Initial	0	0	0	[]
Enqueue 1 through 4	0	0	4	[1, 2, 3, 4]
Dequeue 1	1	0	3	[2, 3, 4]
Enqueue 5	1	1	4	[2, 3, 4, 5]

tail wraps around to zero after the array ends, writing value 5 into the now-empty slot. The physical array may appear as [5, 2, 3, 4], but the logical queue still reads from head=1 onward, so the sequence is [2, 3, 4, 5].

to_list is only used for inspection and requires scanning all elements, resulting in Θ(n) time complexity. In this fixed-capacity implementation, enqueue, dequeue, and front all operate in Θ(1) time. Construction initializes capacity slots, using Θ(capacity) time and storage. Since _size determines empty and full states, None can also be stored as an ordinary value.

Don't Mix the Two Empty/Full Detection Strategies

Circular queues commonly use one of two invariant approaches.

Strategy A: Track Size

This section uses this approach:

empty: size == 0
full:  size == capacity

head == tail may indicate either empty or full; size distinguishes them. The advantage is that all slots are always available, at the cost of maintaining and updating an extra counter.

Strategy B: Reserve One Empty Slot

An alternative implementation does not track size:

empty: head == tail
full:  (tail + 1) % storage_length == head

If you want to expose N usable positions, the underlying structure typically allocates N+1 slots. Using these conditions in a "track size" implementation would result in either one fewer slot than expected or confusion between empty and full states.

Fixed Capacity and Dynamic Expansion

This CircularQueue throws OverflowError when full, making it suitable for demonstrating bounded buffers. A dynamic circular queue can allocate a larger array when full and then logically copy the data in sequence:

def grow(old, head, size, new_capacity):
    if not old or not 0 <= head < len(old) or not 0 <= size <= len(old):
        raise ValueError("invalid circular buffer state")
    if new_capacity <= len(old):
        raise ValueError("new capacity must exceed old capacity")
    new = [None] * new_capacity
    for offset in range(size):
        new[offset] = old[(head + offset) % len(old)]
    return new

This helper requires integer head, size, and new_capacity arguments and returns only the new array. The caller must also reset head to 0, set tail to size, and update capacity. Otherwise the next dequeue still reads from an old position.

Initialization takes Θ(new_capacity) work and copying takes Θ(size). Starting empty with fixed initial capacity, and growing by a fixed factor greater than 1 whenever full, gives amortized Θ(1) enqueue cost. The growth factor belongs to the implementation, not the queue abstraction.

BFS: Who Discovers First, Who Expands First

Breadth-first search (BFS) expands the start first, then its neighbors, then the next layer. The queue holds discovered but unexpanded nodes; FIFO keeps earlier layers ahead of later ones.

Here is level-order traversal of a binary tree:

from collections import deque

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

def bfs_level_order(root):
    if root is None:
        return []

    levels = []
    queue = deque([root])
    while queue:
        level = []
        for _ in range(len(queue)):
            node = queue.popleft()
            level.append(node.value)
            if node.left is not None:
                queue.append(node.left)
            if node.right is not None:
                queue.append(node.right)
        levels.append(level)
    return levels

root = TreeNode(
    1,
    TreeNode(2, TreeNode(4), TreeNode(5)),
    TreeNode(3, None, TreeNode(6)),
)
assert bfs_level_order(root) == [[1], [2, 3], [4, 5, 6]]

At the start of each round, len(queue) fixes the current layer’s node count. The loop processes only this batch; children added during the process are deferred to the next round. The input must be a tree, with no cycles or shared children. Processing n nodes takes Θ(n) time. With maximum layer width w, the queue uses O(w) space; the returned levels use another Θ(n).

Let V and E count vertices and adjacency entries reachable from the start. With adjacency lists and constant-time hashing and queue-end operations, BFS takes Θ(V+E) time: each vertex is enqueued at most once according to the algorithm's rules, and each edge is checked at most a constant number of times. If instead list.pop(0) is used, each dequeue operation may require shifting references within the queue; when the queue width reaches Θ(V), shifting can cost Θ(V²) in the worst case, in addition to inspecting E adjacency entries. However, on a narrow chain, the queue remains small throughout, so it cannot be said that the algorithm necessarily degrades to quadratic complexity for all inputs.

from collections import deque

def bfs_distances(graph, start):
    distance = {start: 0}
    queue = deque([start])
    while queue:
        node = queue.popleft()
        for neighbor in graph[node]:
            if neighbor not in distance:
                distance[neighbor] = distance[node] + 1
                queue.append(neighbor)
    return distance

graph = {"A": ["B", "C"], "B": ["D"], "C": ["D"], "D": []}
assert bfs_distances(graph, "A") == {"A": 0, "B": 1, "C": 1, "D": 2}

bfs_distances requires the start and every reachable neighbor to have an adjacency list in the dictionary. Recording distance before enqueue also marks the node visited, preventing cycles or converging paths from enqueuing it again. The result gives minimum edge counts in an unweighted graph and includes only reachable vertices; it does not minimize weighted distance. The queue and distance table each use O(V) space.

Queue Interfaces in Common Languages

Language	Common Queue Operations	Enqueue / Dequeue / Peek	Failure and Cost
Python	collections.deque	append / popleft / q[0]	Both ends operations are approximately O(1); popping from an empty queue throws IndexError
Java 17	Queue<E> + ArrayDeque<E>	offer / poll / peek	poll and peek return null when empty; remove and element throw exceptions when empty; ArrayDeque prohibits null
C++	std::queue<T>	push / pop / front	Defaults to std::deque; check nonempty before front or pop; pop returns no element

Java’s Queue interface also permits non-FIFO implementations, such as priority queues. The table specifically uses ArrayDeque in its FIFO role. ArrayDeque is implemented as a growable array. The documentation describes most operations as amortized constant time. It is not thread-safe. A multi-step "check-then-act" workflow still requires external synchronization or a concurrent queue.

References:

• Python collections.deque
• Java Queue
• Java ArrayDeque
• C++ std::queue

How to Diagnose Common Errors

Symptom	First Check
Overwriting an element that hasn't been dequeued	Did you check if the queue is full before writing? Is tail representing the next write position?
Out-of-order traversal after wrap-around	Are you using (head + offset) % capacity to access the position?
Capacity is one less than expected	Did you accidentally mix in the "reserve empty slot" fullness rule into size logic?
Objects still held after dequeuing	Did you clear the old head slot into None?
BFS incorrectly merges two levels	Did you save the current level before adding children to the next level via len(queue)?
Graph BFS repeatedly visits nodes	Are you marking visited during enqueue, rather than after dequeuing?

Hands-on Verify Wraparound and Capacity

1. Starting from head=4, what are the physical indices of the three elements in a circular queue with capacity 5?
2. Modify the example to use a scheme that preserves empty slots. If the public capacity is 4, how long should the backing array be?
3. Design an expansion procedure for a dynamic circular queue. After expansion, what should be the values of head and tail?
4. Perform a BFS on a tree that has only right children. What is the maximum queue length during the traversal?
5. Advanced: Implement a FIFO queue using two stacks, and explain the transfer cost using amortized analysis.

Final Check of the FIFO Invariants

Keep the empty/full invariants consistent. Tracking size lets the queue use every slot; reserving an empty slot requires one extra position. Then specify what happens when the queue is empty, full, or resized. BFS depends on the same FIFO rule: nodes discovered first are expanded first.

The next section covers double-ended queues, which preserve an ordering contract while allowing operations at both ends.