Picture a line at a checkout counter. New shoppers join at the back; the shopper at the front is served next. A queue works the same way: it processes elements in the order they arrived. This rule is called first in, first out, or FIFO. section 9.18 section 9.2
A queue has two core operations:
- enqueue(value) adds a value at the rear, also called the tail. section 9.3
- dequeue() removes and returns the value at the front, also called the head. It cannot remove an arbitrary value from the middle. section 9.3 section 9.18
A small queue in action
Enqueue A, then B, then C. The first dequeue returns A; the next returns B. C remains at the front. That makes a queue useful when arrival order matters, such as reviewing bug reports from oldest to newest. A report returned to the rear waits its turn again. section 9.2 section 9.4
A queue defines behavior, not a particular storage layout. Unlike a stack, which adds and removes at the same end and processes the newest element first, a queue adds at one end and removes at the other. A priority queue makes a different choice again: it returns the most urgent item rather than necessarily the oldest. section 9.3 section 1.10
Two practical implementations offer different tradeoffs:
- Linked list: keep access to both ends, add at the rear, and remove from the front. Enqueue and dequeue take O(1) time in the worst case, and the queue can grow or shrink. section 9.6 section 9.18
- Static array: choose a capacity in advance. A simple linear queue eventually runs out of positions at the rear even after removals free earlier cells. A circular queue reuses those cells by wrapping its indexes around; it takes more implementation work but can be memory-efficient and fast in practice. section 9.7 section 9.9
For a circular array queue, front identifies the next value to remove, rear identifies the next cell to fill, and size tracks how many values are stored. After either index reaches the end, modulo arithmetic brings it back to the beginning. Size also distinguishes an empty queue from a full one when front and rear coincide. Enqueuing to a full fixed-capacity queue and dequeuing from an empty one are errors. section 9.10 section 9.11 section 9.12
def enqueue(self, value):
if self.is_full():
raise ValueError('The queue is already full!')
self._data[self._rear] = value
self._rear = (self._rear + 1) % self._max_size
self._size += 1
The enqueue implementation shows the rear index wrapping with modulo arithmetic after a value is stored. section 9.11
Use a queue when work should be handled in arrival order: incoming web requests, printer jobs, and breadth-first search are examples. If urgency must override arrival order, consider a priority queue instead. section 9.16 section 9.17 section 9.14 section 1.10
