Queues and deques

The classic functional queue keeps two lists: the front in order and the rear reversed, so adding at the back and removing from the front are both a cons. When the front runs out, the rear is reversed into a new front. Used once, that costs O(1) per operation on average, but if a program pops the same old version repeatedly it reverses the same rear each time. Okasaki’s banker’s queue uses lazy lists and rotates as soon as the rear is longer than the front, so the rotation is a memoized suspension that later versions share. Okasaki’s real-time queue goes further: each operation forces a little of the pending work, which makes every operation O(1) in the worst case.

Double-ended queues and concatenation are harder. Kaplan and Tarjan (1999) gave a purely functional deque with worst-case O(1) push, pop, inject, eject and catenation and no laziness at all, beating an earlier O(log* k) bound. Kaplan, Okasaki and Tarjan (2000) traded that for something much simpler: catenable deques with O(1) amortized operations that are purely functional if memoization is allowed. In 2003 Mihaescu and Tarjan described a simpler constant-time design in Princeton course notes, written for pure Lisp without lazy evaluation.

Pick a two-list queue when versions are not reused, a banker’s or real-time queue when they are, and a finger tree (Haskell’s Data.Sequence) when you also need indexing or splitting. Scala’s immutable Queue documents its enqueue and dequeue as constant time.