UndoStack

undoStack is a data structure used to implement undo and redo functionality in interactive applications. It records a history of actions or document states so that previous states can be restored.

A common implementation uses two stacks: an undo stack and a redo stack. When an operation completes, a reversible command or a state delta is created and pushed onto the undo stack. On performing an undo, the most recent command is popped from the undo stack, its inverse is applied (or the previous state is restored), and the command is pushed onto the redo stack. A redo pops from the redo stack and re-applies the operation. Performing a new action typically clears the redo stack, ensuring redo only replays actions from the most recent editing path.

There are two main design approaches. In command-based undo stacks, each action is encapsulated as a command with execute and undo methods, or as a delta that can be reversed. In state-based approaches, the stack stores full or partial snapshots of the document, which can simplify undo logic but may increase memory usage. Hybrid approaches may merge small edits into compound actions to support meaningful user-level undos.

Common considerations include memory usage, as full snapshots can be costly, and the desire to support multi-level or grouped undos, time-based grouping of edits, or merging related edits. Implementations must handle edge cases such as initial states, redos after new actions, and concurrency in multi-threaded applications.

Applications include text editors, graphic design tools, IDEs, and other software requiring reversible operations. The undoStack concept is closely related to the redo stack and the command design pattern.