Implementing a Queue

A queue is a linear data structure that enforces a First-In, First-Out (FIFO) ordering: the element that has waited the longest is always the first one to be removed. Queues appear everywhere in computing — from scheduling processes in an operating system and buffering network packets, to managing print jobs and implementing breadth-first graph traversal. Understanding how to implement a queue well means understanding the two dominant strategies — arrays and linked lists — and knowing when each is the right tool. This topic walks through both approaches in depth, examines every core operation with real code, analyzes the subtle edge cases that trip up real implementations, and compares time and space complexity so you can make informed design decisions.

Array-Based Queue Implementation

The most intuitive way to build a queue is to back it with an array. You maintain two integer indices — front (pointing to the oldest element) and rear (pointing to where the next element will be written) — and the FIFO rule is enforced simply by always reading from front and always writing to rear.

A naive approach moves rear forward on every enqueue and front forward on every dequeue. The problem is that, after enough operations, rear reaches the end of the array even though there may be plenty of free slots at the beginning (vacated by earlier dequeues). The solution is a circular array: both indices wrap around using modulo arithmetic so that the array is treated as a ring. The key formulas are:

rear  = (rear  + 1) % capacity   // after writing the new element
front = (front + 1) % capacity   // after reading the front element

Below is a complete, self-contained Python implementation of a fixed-capacity circular array queue:

class ArrayQueue:
    def __init__(self, capacity=8):
        self._data     = [None] * capacity
        self._capacity = capacity
        self._front    = 0          # index of the oldest element
        self._size     = 0          # number of live elements

    # --- core operations ---

    def enqueue(self, value):
        if self._size == self._capacity:
            raise OverflowError("Queue is full")
        rear = (self._front + self._size) % self._capacity
        self._data[rear] = value
        self._size += 1

    def dequeue(self):
        if self._size == 0:
            raise IndexError("Dequeue from empty queue")
        value = self._data[self._front]
        self._data[self._front] = None          # release reference (GC-friendly)
        self._front = (self._front + 1) % self._capacity
        self._size -= 1
        return value

    def peek(self):
        if self._size == 0:
            raise IndexError("Peek at empty queue")
        return self._data[self._front]

    # --- auxiliary operations ---

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

    def __repr__(self):
        items = [(self._data[(self._front + i) % self._capacity])
                 for i in range(self._size)]
        return f"ArrayQueue({items})"

Notice that rear is not stored as a separate field; it is computed on demand as (front + size) % capacity. Tracking size independently is the cleanest way to distinguish a completely full queue from a completely empty one — two states that would otherwise look identical if you only compared front and rear pointers.

A fixed-size array like the one above has a hard upper bound; when it is full, you must either reject new elements (raising an error, as above), drop the oldest element to make room (a "ring buffer" variant common in audio/streaming systems), or resize. A dynamic array — such as Python's built-in list or Java's ArrayList — sidesteps the hard limit by doubling its internal storage whenever it runs out of room. Doubling keeps the amortized cost of a single enqueue at O(1), but individual resize events cost O(n) and can cause latency spikes in real-time systems.

Array-based queues have excellent cache locality: all elements live in a single contiguous block of memory, so iterating through the queue touches cache lines that are already warm. For workloads dominated by sequential access this is a significant practical advantage over pointer-linked structures.

Linked List-Based Queue Implementation

The alternative is to use a singly linked list. Each node holds a value and a pointer to the next node. The queue keeps two sentinel references: head (the front, dequeued first) and tail (the rear, where new nodes are appended). Both operations are O(1) and require no index arithmetic:

class _Node:
    __slots__ = ("value", "next")   # saves memory vs. a plain dict-backed object
    def __init__(self, value):
        self.value = value
        self.next  = None

class LinkedQueue:
    def __init__(self):
        self._head = None   # front of queue
        self._tail = None   # rear of queue
        self._size = 0

    # --- core operations ---

    def enqueue(self, value):
        node = _Node(value)
        if self._tail is None:          # queue was empty
            self._head = node
            self._tail = node
        else:
            self._tail.next = node
            self._tail = node
        self._size += 1

    def dequeue(self):
        if self._head is None:
            raise IndexError("Dequeue from empty queue")
        value = self._head.value
        self._head = self._head.next
        if self._head is None:          # queue is now empty
            self._tail = None           # avoid dangling tail reference
        self._size -= 1
        return value

    def peek(self):
        if self._head is None:
            raise IndexError("Peek at empty queue")
        return self._head.value

    # --- auxiliary operations ---

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

    def __repr__(self):
        items, cur = [], self._head
        while cur:
            items.append(cur.value)
            cur = cur.next
        return f"LinkedQueue({items})"

Because every enqueue allocates a brand-new node, the linked list never needs to be resized. It can grow to whatever size heap memory allows, making it naturally suited to workloads where the maximum queue depth is unknown or highly variable. The cost, however, is that each node carries an extra pointer field (8 bytes on a 64-bit system) beyond the payload, and — more importantly — successive nodes may be scattered across heap memory, causing cache misses when the processor has to fetch each node's data from a different cache line. For a queue with millions of elements this can be measurably slower in practice than a circular array queue, even though both are O(1) per operation.

Core Queue Operations in Code

Regardless of the underlying storage, every queue exposes the same logical interface. The table below maps the standard operation names used in different languages and contexts:

Enqueue is the producer-side operation. In the circular array it writes the value at the computed rear index and increments size. In the linked list it allocates a node and links it after the current tail. Either way the caller should always check for a full condition (array) or out-of-memory condition (linked list) in production code.

Dequeue is the consumer-side operation. It is the one most likely to fail — if a consumer tries to dequeue from an empty queue, the implementation must not silently return garbage. Good designs either raise an exception (IndexError, NoSuchElementException) or return a special sentinel value (None, -1, a wrapped Optional) that the caller is expected to check. Returning None silently can hide bugs; raising an exception is generally safer during development.

Peek is a non-destructive read. A common use is in simulation or scheduling code where you want to examine the next task's priority or timestamp before committing to removing it. Because peek does not modify the queue, it is idempotent and safe to call repeatedly.

isEmpty and size are guard operations. Best practice is to call is_empty() before every dequeue or peek rather than catching exceptions after the fact, especially in tight loops where exception handling has overhead.

Trade-Offs: Arrays vs. Linked Lists

Choosing between an array-backed and a linked-list-backed queue is a design decision that depends on your runtime constraints. The following comparison captures the most important dimensions:

When the maximum queue depth is known in advance — for example, a bounded task queue with at most 1,024 jobs — a fixed circular array is almost always preferable. It avoids per-element allocation overhead, keeps data in cache, and its capacity limit is a built-in safety valve against runaway growth. When the queue size is highly variable and worst-case latency matters more than average throughput — for example, a real-time message broker — a linked list avoids the sudden O(n) pause that comes with array resizing.

Handling Edge Cases in Implementation

Robust queue implementations must anticipate and explicitly handle several boundary conditions that arise in real use.

Empty-queue dequeue and peek. Both operations are undefined on an empty queue. The safest practice is to check is_empty() first and raise a descriptive exception if the queue is empty. Returning a default value such as None or -1 can work, but only if the caller always checks the return value — an easy contract to break. In Java's Queue interface, remove() throws NoSuchElementException while poll() returns null, giving callers the choice.

Enqueue into a full array. A fixed-size circular array becomes full when size == capacity. There are three principled responses:

• Reject: raise an OverflowError. The caller must decide what to do. This is the safest default.
• Resize: allocate a new, larger array, copy elements in logical order (front → rear), and update front to 0. This makes the queue "dynamic" at the cost of an occasional O(n) operation.
• Overwrite: advance front by one (discarding the oldest element) before writing the new one. This "ring buffer" strategy is common in audio processing and logging, where losing old data is acceptable but blocking is not.

Distinguishing full from empty in a circular array. If you only track front and rear without a separate size field, both an empty and a full queue satisfy front == rear. Two classical fixes exist: (1) keep a separate size counter (the approach used in the code above — cleanest and unambiguous); (2) leave one slot permanently unused so a full queue satisfies (rear + 1) % capacity == front while an empty queue satisfies front == rear. The unused-slot approach wastes one array position but avoids the extra integer field.

Resetting tail after the last dequeue. In the linked list implementation, after removing the last node, head becomes None. If tail is not also reset to None, it continues pointing to the now-garbage-collected (or dangling) old node. The next enqueue would then link a new node to a dead object. Every correct linked list dequeue must include:

if self._head is None:
    self._tail = None   # critical — prevents dangling tail reference

Missing this single line is one of the most common bugs in student queue implementations.

Thread safety. Neither implementation above is thread-safe. If multiple threads enqueue and dequeue concurrently, the size field (or the front/rear pointers) can be corrupted by race conditions. Production concurrent queues require atomic operations or locks — e.g., Python's queue.Queue, Java's ConcurrentLinkedQueue, or a mutex-protected wrapper.

Time and Space Complexity Analysis

The formal complexity of both implementations is summarized below:

The amortized O(1) enqueue for dynamic arrays deserves a brief proof sketch. Suppose the array doubles in capacity each time it fills. The i-th resize copies i elements. Starting from capacity 1 and performing n insertions, the total copy work is 1 + 2 + 4 + … + n ≈ 2n. Dividing by n insertions gives an amortized cost of 2 — i.e., O(1) — per enqueue. The key insight is that the expensive resize events are rare enough that their cost, spread across many cheap enqueues, becomes negligible.

Regarding space: a circular array of capacity c always occupies exactly c slots regardless of how many are in use — potentially wasteful if the queue is usually small but occasionally spikes. A dynamic array wastes up to a factor of 2× due to pre-allocated spare capacity after a resize. A linked list uses exactly as many allocations as there are live elements, but each allocation is larger than a pure array slot by the size of a pointer (and usually by alignment padding too). In memory-constrained environments — embedded systems, kernels, microcontrollers — this per-node overhead can be decisive.

In summary: both array and linked list queues achieve the same asymptotic complexity, but they differ substantially in constant factors, memory layout, and behavioral guarantees under stress. The best queue implementation is the one that matches your known constraints on size, latency, and memory budget.