= Solution
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:
``
sml
datatype 'a queue = Q of 'a list * 'a list;
exception EmptyQueue;
fun check ([], rear) = Q (rev rear, [])
| check (front, rear) = Q (front, rear);
fun empty () = Q ([], []);
fun isEmpty (Q (front, _)) = null front;
fun enqueue x (Q (front, rear)) = check (front, x :: rear);
fun peek (Q ([], _)) = raise EmptyQueue
| peek (Q (x :: _, _)) = x;
fun dequeue (Q ([], _)) = raise EmptyQueue
| dequeue (Q (x :: front, rear)) = (x, check (front, rear));
``
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`.
Back to article page
