Undo-redo logic records successive program states so users can restore an earlier state and later reapply a reversed change. A mutable queue makes the problem concrete: dequeuing does not generally undo an enqueue, especially when the queue was not empty. section 2.6
Two conventional strategies reveal the main trade-offs:
- Clone the entire mutable state before each operation, then move states between undo and redo stacks. This is simple but costs O(n) time per copy and can consume O(n²) total space. section 2.6.1
- Represent every mutation with paired command objects, such as enqueue and dequeue commands. This works with mutable state but requires every undoable action and data structure to define its inverse. section 2.6.2
A reusable UndoRedo<T> helper takes a different route: keep the current immutable state, an undo stack, and a redo stack. Do pushes the previous state and clears redo; Undo moves the current state to redo and restores the previous state; Redo performs the opposite transfer. Persistent immutable structures share most state, so each saved version adds only O(1) space on average while stack operations remain O(1). section 2.6.3 section 2.8
An undoable immutable queue
An UndoRedoQueue<T> forwards Enqueue, Peek, and Dequeue to an immutable queue while routing state changes through UndoRedo<T>. Enqueue 10, 20, and 30; undo removes 30; redo restores it; dequeue removes 10; undo restores the full queue.
