Queues and deques
A queue is first-in, first-out: items leave in the order they arrived, like people waiting in line. Queues are everywhere in computing, from printers to web servers.
The queue ADT
A queue supports enqueue (add at the back), dequeue (remove from the front), peek at the front, and isEmpty. The order is FIFO: first in, first out. Queues model fairness: requests are served in arrival order, which makes them central to scheduling and buffering.
Why a plain array is a poor queue
Removing from the front of an array shifts every remaining element, costing O(n) per dequeue. Python's list.pop(0) has exactly this problem, so Python provides collections.deque instead. A good queue needs O(1) operations at both the front and the back.
Circular buffers
A circular buffer, or ring buffer, stores a queue in a fixed array with head and tail indexes that wrap around using modulo arithmetic: the next index after the last slot is 0. Enqueue writes at tail and advances it; dequeue reads at head and advances it. Both are O(1). Keeping a count distinguishes a full buffer from an empty one, since head equals tail in both cases.
Linked-list queues
A singly linked list with both head and tail pointers is also a natural queue: enqueue appends at the tail, dequeue removes at the head, both O(1) and with no capacity limit. The cost is a pointer per element and poorer cache behaviour than a ring buffer.
Deques
A double-ended queue, or deque, allows insertion and removal at both ends in O(1). It can act as either a stack or a queue. Implementations include doubly linked lists, circular buffers that grow, and blocks of arrays, as in C++ std::deque and Python's collections.deque.
Queues in systems
Operating systems keep ready queues of processes; printers queue jobs; network routers buffer packets in queues and drop them when full; web servers queue incoming requests; and message queues such as RabbitMQ and Kafka pass work between services so producers and consumers can run at different speeds.
Breadth-first search and sliding windows
Breadth-first search explores a graph level by level using a queue: dequeue a node, then enqueue its unvisited neighbours. A deque solves the sliding-window maximum problem in O(n): it keeps indexes of potentially useful elements in decreasing value order, dropping expired ones from the front and dominated ones from the back.
Worked example
A ring buffer of capacity 4, initially empty with head = tail = 0. Enqueue A, B, C: slots 0 to 2 filled, tail = 3, count = 3. Dequeue returns A, head = 1, count = 2. Enqueue D at slot 3, tail = (3 + 1) mod 4 = 0. Enqueue E at slot 0, tail = 1, count = 4: full. The buffer reused slot 0 without shifting anything.
Key takeaways
A queue is FIFO with enqueue at the back and dequeue at the front. Array front-removal is O(n), so use proper structures. Circular buffers wrap indexes with modulo for O(1) operations in fixed space; track count to tell full from empty. Linked lists with head and tail pointers give unbounded O(1) queues. Deques support both ends and can act as stacks or queues. Queues underpin scheduling, buffering, message passing, breadth-first search, and sliding-window algorithms.
Flashcard
First-in, first-out collection
Check your understanding
Why should Python programmers use collections.deque rather than a list for a queue?