= Solution
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 \b[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\lvert\texttt{rear}\rvert$, 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\geq0$,
$$
\sum_{i=1}^m c_i=\sum_{i=1}^m\bigl(c_i+\Phi_i-\Phi_{i-1}\bigr)-\Phi_m=O(m).
$$
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.
Back to article page
