Queues and Deques

The stack gives priority to the most recently added element. In some problems, the expected behavior is exactly the reverse: in a job queue, the first to arrive must be processed first; in a network buffer, packets must preserve their arrival order.

The queue is the abstract data type that defines this rule: first in, first out.

Queue Operations

Operation	Meaning	Target cost
enqueue	Adds an element to the end	$O(1)$
dequeue	Removes and returns the front element	$O(1)$
front	Shows the front element without removing it	$O(1)$
is_empty	Reports whether the queue is empty	$O(1)$

Its only difference from the stack is which end removal happens at. This small difference makes the implementation noticeably harder: in a stack, both operations are at the same end so a single index suffices, while in a queue the two ends must be tracked separately.

The Problem with a Naive Array Implementation

If a queue is built with a dynamic array, appending at the end is cheap, but taking from the front requires shifting every element one position to the left — $O(n)$. In a thousand-element queue, every dequeue call does a thousand shifts.

The first idea for avoiding the shift is to advance a head index: the element is not deleted, it is just counted as “no longer in the queue.” This makes dequeue constant time but creates a new problem — space at the start of the array becomes free and is never reclaimed. A queue that runs continuously grows its unused space without bound.

Circular Buffer

The solution is to wrap around to the start when the end of the array is reached. A fixed-capacity block is treated as if its ends were joined together; this structure is called a circular buffer.

Two indices are kept: head points to the next element to be taken; tail points to the next position to be written. Advancing is done by taking the remainder modulo capacity:

$$\text{new position} = (\text{position} + 1) \bmod \text{capacity}$$

The modulo operator was introduced in the Operators lesson; this use of it is its canonical example.

class CircularBuffer:
    """Fixed-capacity queue; wraps around to the start when it reaches the ends."""

    def __init__(self, capacity: int) -> None:
        self._data: list = [None] * capacity
        self._capacity = capacity
        self._head = 0
        self._count = 0

    def __len__(self) -> int:
        return self._count

    def is_full(self) -> bool:
        return self._count == self._capacity

    def is_empty(self) -> bool:
        return self._count == 0

    def enqueue(self, value) -> None:
        if self.is_full():
            raise OverflowError("buffer is full")
        tail = (self._head + self._count) % self._capacity   # position to write
        self._data[tail] = value
        self._count += 1

    def dequeue(self):
        if self.is_empty():
            raise IndexError("cannot dequeue from an empty buffer")
        value = self._data[self._head]
        self._data[self._head] = None                        # drop the reference
        self._head = (self._head + 1) % self._capacity       # wrap to the start
        self._count -= 1
        return value


queue = CircularBuffer(3)
queue.enqueue(12); queue.enqueue(18); queue.enqueue(7)
print(len(queue), queue.is_full())        # 3 True

print(queue.dequeue(), queue.dequeue())   # 12 18
queue.enqueue(25); queue.enqueue(14)      # written into freed slots by wrapping to the start
print(len(queue))                         # 3
print(queue.dequeue(), queue.dequeue(), queue.dequeue())   # 7 25 14

A buffer with capacity three has carried five elements: the new elements were written into the freed positions by wrapping around to the start. No element was shifted, no reallocation happened.

What happens on insertion into a full buffer is a design choice. Three options are common: raising an error (as above), blocking the caller, or overwriting the oldest element. The third is preferred in logging buffers that keep only the last $k$ measurements.

A Queue with a Linked List

If a capacity limit is not wanted, a linked list that keeps both a head and a tail pointer is used: appending at the end is done in constant time with the tail pointer, and taking from the front with the head pointer.

Its cost was defined in the previous lesson: per-node pointer overhead and scattered layout. The common practical solution is a combination of the two — the linked list’s nodes carry not a single element but small contiguous blocks. This achieves both unbounded growth and reasonable cache behavior.

Deque

A deque permits insertion and removal at both ends. It encompasses both the stack and the queue: it behaves like a stack if only one end is used, and like a queue if the two ends are used separately.

The circular buffer naturally supports the deque as well; the head index can also wrap backward.

Its typical use is sliding-window problems: a new measurement enters at one end, and whatever falls outside the window leaves at the other. This is the data-structure counterpart of the sliding window pattern introduced in the Programming Fundamentals course.

Use Cases

• Job queues. In a producer–consumer arrangement, jobs are queued; order is preserved.
• Buffering. A circular buffer is used between two components running at different speeds; device communication in the How Computers Work course follows this arrangement.
• Breadth-first search. As will be seen in this course’s final topic, layer-by-layer traversal in graphs runs on a queue.
• Scheduling. An operating system’s ready-process list follows queue order under fair sharing.

In situations where what determines order is not arrival but priority, a queue is not enough; a priority queue is required. That structure will be taken up in the heap lesson of the trees topic.

Queue Length Is a Metric

A queue is not only a data structure; it is an indicator of the speed difference between two components. If queue length keeps growing, production is outpacing consumption.

In an unbounded-capacity queue, this can stay hidden for a long time: no sign appears until memory fills up, and then the system suddenly collapses. In a bounded-capacity queue, a decision becomes necessary once the limit is reached — blocking the producer, rejecting new work, or dropping the oldest item.

Blocking the producer is slowness propagating back toward the source, and it is called backpressure. This concept, which came up in device-to-device communication in the How Computers Work course, works the same way in distributed systems.

For this reason, queue length is a monitored metric in production: its trend directly shows where the bottleneck is.

Cost Table

Structure	Take from front	Insert at end	Insert at start	Capacity
Dynamic array (naive queue)	$O(n)$	$O(1)$ amortized	$O(n)$	Unbounded
Circular buffer	$O(1)$	$O(1)$	$O(1)$	Fixed
Linked list (head + tail)	$O(1)$	$O(1)$	$O(1)$	Unbounded
Deque	$O(1)$	$O(1)$	$O(1)$	Varies

Summary

• The queue is defined by the first-in-first-out rule; its only difference from the stack is which end removal happens at.
• In a naive array implementation, taking from the front requires shifting; advancing a head index instead accumulates unused space.
• The circular buffer joins the ends with the modulo operator and makes both operations constant time with fixed capacity.
• Behavior on a full buffer — error, blocking, or overwriting — is a design decision.
• A linked list with head and tail pointers gives an unbounded-capacity queue; its cost is pointer overhead and locality.
• The deque permits both ends and is the natural structure for sliding-window problems.

Next Step

So far, sequential access and operations at the ends have been covered. Search in a sorted data set, however, is still linear: binary search cannot be done on a linked list, because there is no jumping to the middle element. The next lesson takes up a probabilistic solution that makes this jump possible by adding layers to the linked structure.