What structure would you use for undo functionality in an application?

For undo functionality in an application, you would typically use a data structure known as a stack.

A stack is a linear data structure that follows a particular order in which operations are performed. The order may be LIFO (Last In First Out) or FILO (First In Last Out). Mainly the following three basic operations are performed in the stack:

1. Push: Adds an element to the collection.
2. Pop: Removes an element from the collection.
3. Peek or Top: Returns the top element of the collection.

In the context of undo functionality, each action performed by a user is 'pushed' onto the stack. When the user wants to undo an action, the most recent action is 'popped' from the stack and reversed. This is why the LIFO order is crucial, as it allows easy access to the most recent action, which is the one that needs to be undone.

For example, consider a text editor application. Each time a user types a character, deletes a character, or performs any other editable action, that action is pushed onto the stack. If the user decides to undo their last action, the application pops the action from the stack and reverses it, effectively undoing the action.

The stack can also be used to implement redo functionality. When an action is undone, instead of being discarded, it can be pushed onto a second stack. If the user decides to redo the action, it can be popped from the second stack and reapplied.

In conclusion, a stack is a simple yet powerful data structure that can be used to implement undo and redo functionality in an application. Its LIFO order makes it ideal for storing a sequence of actions in the order they were performed, allowing easy access to the most recent action when needed.