Queues: First Come, First Served
The FIFO (first-in, first-out) discipline — the naive-array trap and the ring buffer, where queues shine (BFS, task processing), and how to write one in C, Java, C#, and Python
What a queue is: a checkout line
A queue is a container that allows only two things: joining at the back and leaving from the front. Just like a checkout line, a newcomer cannot cut in at the front. Adding is called enqueue, removing is called dequeue.
enqueue(40) dequeue() -> 10 | ^ v | back +------+------+------+------+ front ----> | 40 | 30 | 20 | 10 | ----> +------+------+------+------+ FIFO: First-In, First-Out
The first thing in is the first thing out — a discipline called FIFO (First-In, First-Out). The only difference from a stack is where the exit is: a stack's entrance and exit are at the same end, a queue's are at opposite ends.
The naive-array trap, and the ring buffer
If you build a queue on an array and shift every remaining element each time you take from the front, each dequeue costs O(n). The "arrays are bad at the front" lesson from the Arrays and Lists page shows up exactly here.
The fix is the ring buffer (circular buffer). Keep two indices — one pointing at the front, one at the back. Dequeue just advances the front index; enqueue writes at the back index and advances it. When an index reaches the end of the array, it wraps around to 0.
Ring buffer: when an index reaches the end, it wraps to 0 index: 0 1 2 3 4 +------+------+------+------+------+ | | 20 | 30 | 40 | | +------+------+------+------+------+ ^ ^ head tail dequeue: just advance head -> O(1) enqueue: write at tail and advance it -> O(1) after index 4 comes 0 (treat the array as a circle)
With no more shifting, both operations become O(1). When the buffer fills up, do what a dynamic array does: allocate a larger array and repack.
Where queues are used
Anywhere things must be processed in arrival order. Breadth-first search (BFS) uses a queue to explore "nearest places first" — a neat mirror image of DFS, which used a stack to go as deep as possible.
In practice, queues are everywhere as the buffer between producers and consumers of different speeds: task queues, job schedulers, message queues connecting systems, input buffers.
Two variants matter: a deque (double-ended queue) allows insertion and removal at both ends, and a priority queue releases elements by priority rather than arrival order.
Across languages: C, Java, C#, and Python
In C
/* C: build the ring buffer yourself */ int queue[8]; int head = 0, tail = 0; void enqueue(int v) { queue[tail] = v; tail = (tail + 1) % 8; } int dequeue(void) { int v = queue[head]; head = (head + 1) % 8; return v; }
In C you build the ring buffer yourself. Two indices (head / tail) plus the remainder operator (%) are all it takes to wrap around (full/empty checks omitted).
In Java
// The idiom: the Queue interface + the ArrayDeque implementation Queue<String> queue = new ArrayDeque<>(); queue.offer("a"); // join at the back queue.offer("b"); String head = queue.poll(); // "a" — first come, first served // Inside ArrayDeque is a ring buffer: // Object[] elements; int head; int tail; // When full, it repacks into a larger array (same idea as a // dynamic array).
Java's Queue is an interface: offer to add, poll to remove, peek to look at the front. The standard implementation is ArrayDeque — inside it is exactly the ring buffer above, holding an Object[] plus head / tail indices, and repacking into a larger array when full.
LinkedList also implements Queue (being doubly linked, both ends are O(1)), but the cache behavior we saw on the Arrays and Lists page (a contiguous array is faster to walk) makes ArrayDeque the standard choice. For priority order, use PriorityQueue — inside it is a heap, a tree structure related to the next page's topic.
In C#
// C#: the Queue<T> class (a ring buffer inside) var queue = new Queue<string>(); queue.Enqueue("a"); // join at the back queue.Enqueue("b"); string head = queue.Dequeue(); // "a" — first come, first served
C#'s Queue<T> is also a ring buffer inside, used through names that mirror the concept: Enqueue / Dequeue.
In Python
# Python: list.pop(0) is the O(n) trap — use collections.deque from collections import deque queue = deque() queue.append("a") # enqueue queue.append("b") head = queue.popleft() # "a" — O(1) removal from the front
In Python, list.pop(0) walks straight into the O(n) trap. Use the standard collections.deque (a double-ended queue): popleft is O(1).
Summary
A queue is a container with only enqueue / dequeue. The discipline is FIFO (first-in, first-out).
A naive array queue pays O(n) per dequeue — a ring buffer (head/tail indices that wrap around) makes both operations O(1).
The standard building block for processing in arrival order: BFS, task processing, message queues.
Java's ArrayDeque and C#'s Queue<T> are both ring buffers inside. Python has collections.deque (list.pop(0) is the O(n) trap). In C you build your own.