FIFO queue

A FIFO queue is a data structure with first-in, first-out behavior: enqueue inserts at the rear, dequeue removes and returns the front, and peek inspects the front without removing it. Removal and inspection require a nonempty FIFO queue, or an explicitly defined empty-case result. Enqueue $A,B,C$ in that order, dequeue $A$, then enqueue $D$: the remaining sequence is $B,C,D$, with $B$ next. A LIFO stack would remove the most recently inserted item instead. A FIFO queue models arrival-order service and supplies the next vertex for breadth-first search; a stochastic service model belongs to queueing theory. ^[ref]

The FIFO queue interface specifies removal order, not time complexity. A linked list with both front and rear pointers supports enqueue, dequeue and peek in $O(1)$ worst-case time under constant-cost pointer operations and allocation, as in Sedgewick and Wayne's implementation. A plain array that deletes its first entry by shifting the remaining $n-1$ entries takes $O(n)$ time per such removal. An array with advancing front and rear indices can avoid these shifts; storage and resizing policies still need analysis. The two-list functional queue gives a different implementation with constant amortized analysis cost along a single sequence of uses. These representation choices matter when deriving the linear time complexity of breadth-first search in Big O notation.

// Destination: computer-science.bigb

A communicating FIFO queue that accepts values on an input channel and emits them, in the same order, on an output channel. An unbounded FIFO buffer always has room for a new input, even when its oldest pending output is also available.

Represent the abstract sequence by front @ rev rear. Keep the front nonempty unless both lists are empty. Prepending to the rear enqueues; when the front is exhausted, reverse the rear once. Along a single sequence of uses, each element crosses between lists at most once, giving constant amortized analysis cost per operation. Reusing an old persistent version can repeat a reversal and needs a separate analysis.

// Destination: computer-science.bigb