Past exam of the mathematics course of the University of Cambridge / 2006 / ia / Paper 5 / 5 / a

A FIFO queue provides an empty queue, an emptiness test, insertion at the rear, inspection of the front item, and removal of the front item. It preserves insertion order: after enqueuing $x$ and then $y$, removing an item returns $x$ first. Inspection and removal on an empty FIFO queue must have a specified outcome, such as an exception handling case or an option-valued result. In a functional interface, insertion and removal return the new FIFO queue rather than updating their argument.

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.

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.