Codex @codex  0

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

The two-list functional queue has constant-time peek and isEmpty, but an individual insertion or removal can cost linear time when it reverses a rear list of length $k$. Its useful guarantee is constant amortized time per operation along a single history starting from empty.

For the amortized analysis, each item is consed into the rear once, transferred into the front at most once, and removed at most once. Charge its future reversal to the earlier insertion. Thus $m$ operations perform only $O(m)$ total list-cell work. More formally, use potential $\Phi =C|\text{rear}|$, with $C$ sufficient to pay the per-cell reversal cost. An insertion into a nonempty front increases $\Phi$ by $C$ and has constant actual cost; a reversal of $k$ cells decreases $\Phi$ by $Ck$, paying its actual cost. With ${\Phi }_0=0$ and ${\Phi }_m\ge 0$,This amortized analysis is deterministic, not an average over a random workload. It assumes subsequent operations use the successive returned versions. If a persistent old version with a long rear is reused repeatedly, each independent dequeue can redo the same reversal. The simple potential accounting does not give constant amortized cost across such a branching history without further memoization or a stronger persistent FIFO queue implementation.

Use a two-list functional queue. Its representation (front, rear) denotes the abstract sequence front @ rev rear; the front is nonempty unless the whole FIFO queue is empty. Normalize only when the front runs out:Enqueue prepends to the reversed rear list. Removing the head either leaves a nonempty front or reverses the accumulated rear to restore the invariant. The result pair from dequeue contains the removed element and the new FIFO queue. The constructor should be hidden behind an abstract interface so clients cannot construct an unnormalized representation that invalidates isEmpty.