A queue removes items in the order they arrived. An immutable queue keeps that first-in, first-out behavior without changing an existing queue: Enqueue and Dequeue return new versions. The challenge is making operations at opposite ends cheap when an immutable linked list offers cheap access at only one end. section 2.4
Listing 2.6 An immutable queue interface
interface IImQueue<T> : IEnumerable<T>
{
IImQueue<T> Enqueue(T item);
T Peek();
IImQueue<T> Dequeue();
bool IsEmpty { get; }
}
The C# interface makes the immutable contract concrete: Enqueue and Dequeue return queues, while Peek reads the next item. section 2.4
Use two immutable stacks. One accepts enqueues; the other exposes the next item to dequeue. The first item goes directly onto the dequeue stack. Later enqueues push onto the other stack. Dequeue pops the front stack; when that empties, reversing the enqueue stack puts its oldest item at the front. An empty queue can be a shared singleton. Peek and Dequeue on an empty queue rely on the empty stack’s error handling. section 2.4 section 2.6.3
Keep every version
Starting from [], enqueue 10, 20, and 30 to obtain [10], [10, 20], and [10, 20, 30]. Successive dequeues produce [20, 30], [30], and []. Each result is another queue; earlier versions remain available. section 2.4
Figure 2.2 The example includes six immutable queues and six immutable stacks. Because the data structures are persistent and immutable, objects can be reused across different queues.
The diagram shows how persistent queues reuse stack objects across versions rather than copying every item. section 2.4
Enqueue is cheap, but a Dequeue that reverses a stack can take O(n) time. Across a straightforward sequence of operations, those occasional reversals suggest a small average cost. Persistence complicates that argument: after enqueuing 100 items, dequeue once, restore the earlier queue, and dequeue again. Both dequeues can reverse the same 99-item stack. An average-cost claim must account for revisiting old versions, not just advancing through one sequence. section 2.0 section 2.6.3
The same persistent versions make undo and redo practical. A mutable wrapper can store queue states on undo and redo stacks. Each saved queue adds only O(1) memory on average because it shares most of its structure with its predecessor. Redo can restore a saved state in O(1), even when creating that state originally required an expensive reversal. section 2.6.3
Listing 2.11 A mutable undoable queue
class UndoRedoQueue<T> : IEnumerable<T>
{
private UndoRedo<IImQueue<T>> q =
new UndoRedo<IImQueue<T>>(ImQueue<T>.Empty);
public void Enqueue(T item) => q.Do(q.State.Enqueue(item));
public T Peek() => q.State.Peek();
public T Dequeue()
{
T item = q.State.Peek();
q.Do(q.State.Dequeue());
return item;
}
public bool IsEmpty => q.State.IsEmpty;
public bool CanUndo => q.CanUndo;
public void Undo() => q.Undo();
public bool CanRedo => q.CanRedo;
public void Redo() => q.Redo();
public IEnumerator<T> GetEnumerator() => q.State.GetEnumerator();
IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
}
The wrapper demonstrates a mutable queue API built by saving immutable queue states for undo and redo. section 2.6.3
