= Two-list functional queue
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
Back to article page
