Queue visualization

A queue is a collection that adds elements at the back and removes them from the front. The element added first is the first one removed, which is why it is called first in, first out (FIFO). It works like a line at a shop: you join at the end and the person who has waited longest is served first.

How it works

A queue has three operations. The code here keeps the elements in an array and a number head, the index of the oldest element.

1. enqueue(x) puts x after the last element, at the back.
2. dequeue() returns the element at head and moves head one slot to the right.
3. peek() returns the element at head and leaves it in place.

When dequeue runs, nothing is shifted. The slot it leaves behind is shown hatched, and the front simply steps over it. That is why dequeue stays fast.

Time and space complexity

• Time, O(1) for enqueue, dequeue and peek: each one writes or reads one slot, or moves one number. None of them depends on how many elements are waiting.
• Space, O(n): the queue stores its n waiting elements. This simple version also keeps the hatched slots, so a long-running queue wastes room. Real implementations reuse them in a circular buffer, where the end of the array wraps around to its start.

A worked example

Add 4, 8, 1, 6 and 3 in that order, with one removal after every second addition, as the lesson's run does. Then peek, remove everything that is left, and remove once more from the empty queue. The table lists the waiting elements from the front, and the value of head after each operation.

The values went in as 4, 8, 1, 6, 3 and came out in the same order, 4, 8, 1, 6, 3. That is the whole guarantee of a queue. Notice that the array never lost a slot: after the last dequeue it still holds all five values, and head is 5, one past the last slot. The run counts 10 writes (five enqueues and five moves of head) and 6 comparisons, one emptiness check for each dequeue.

Pseudocode

Q.items is the array, Q.head is the index of the oldest element, and NIL stands for the undefined that the code returns.

ENQUEUE(Q, x)
    Q.items[Q.items.length] = x

DEQUEUE(Q)
    if Q.head == Q.items.length
        return NIL            // underflow
    x = Q.items[Q.head]
    Q.head = Q.head + 1
    return x

PEEK(Q)
    if Q.head == Q.items.length
        return NIL
    return Q.items[Q.head]

The queue is empty exactly when head has reached the end of the array. A circular buffer wraps both the head index and the index where new elements go with mod capacity, so the freed slots are reused.

When to use it, and when not to

Use a queue whenever things must be handled in the order they arrived:

• Waiting lines: print jobs, support tickets and requests to a server.
• Buffers: data that is produced faster than it is consumed.
• Breadth-first search: the queue holds the nodes that were found first, so the search moves outward one level at a time.

Do not use it when the newest item must go first. That is a stack. If the item with the highest priority must go first, whatever its arrival time, use a priority queue, as in Dijkstra's algorithm.

Where it is used

• Task and job queues. A print spooler or a server's list of waiting requests serves jobs in the order they arrived. That is fair: a later job can never pass an earlier one. The producer adds at the back, the workers take from the front, and the two do not have to run at the same speed.
• Breadth-first search. The search enqueues the unvisited neighbors of a node and then dequeues the next node to expand. First in, first out means every node at distance 1 leaves the queue before any node at distance 2, so the first time the search reaches a node it has used the fewest possible edges.
• Buffers and scheduling. Keyboard input and network packets arrive in bursts. A fixed-size circular buffer holds them until the program reads them in order. Round-robin CPU scheduling also uses a queue: take the process at the front, run it for a short time slice, and put it at the back.

Common mistake and edge cases

Variations and related ideas

A circular buffer reuses the slots that dequeue leaves behind. A deque allows adding and removing at both ends. A queue can also be built on a linked list that keeps a pointer to its last node, which makes both ends O(1), or from two stacks, where one takes the new elements and the other hands them out in reverse. A priority queue drops the arrival order and always returns the smallest item first; the binary heap implements it, and Dijkstra's algorithm depends on it. Breadth-first search is the standard use of a plain queue.