Queues

A queue is a first-in-first-out container with constant-time enqueue and dequeue, the natural structure for fair, in-order processing.

First in, first out

A queue adds elements at the back with enqueue and removes them from the front with dequeue. The oldest element leaves first, a discipline called FIFO. This models any situation where items should be served in arrival order: print jobs, task schedulers, and message pipelines.

Implementations

A naive array queue that dequeues from index 0 is O(n) per dequeue because every remaining element shifts. The fix is a circular buffer: keep head and tail indices that wrap around a fixed array using modular arithmetic, giving O(1) at both ends. A linked list with head and tail pointers is the other standard implementation.

• Enqueue at back: O(1)
• Dequeue from front: O(1)
• Peek at front: O(1)
• Search: O(n)

The ring buffer

class RingQueue:
    def __init__(self, cap):
        self.buf = [None]*cap
        self.cap = cap
        self.head = self.tail = self.n = 0
    def enqueue(self, x):
        self.buf[self.tail] = x
        self.tail = (self.tail + 1) % self.cap
        self.n += 1
    def dequeue(self):
        x = self.buf[self.head]
        self.head = (self.head + 1) % self.cap
        self.n -= 1
        return x

Variants worth knowing

Several specialised queues extend the basic idea. A priority queue serves the most important element rather than the oldest, breaking the FIFO rule. A blocking queue makes a consumer wait when empty and a producer wait when full, coordinating threads safely. A concurrent lock-free queue lets many threads enqueue and dequeue without locks, using atomic compare-and-swap operations.

Where queues appear

Queues drive breadth-first search, which visits nodes in order of distance from the start. They sit at the core of operating-system scheduling, buffering between producers and consumers running at different speeds, request handling in web servers, and event loops. When both ends need insertion and removal, a deque generalises the queue; when order should follow importance, a priority queue replaces it.