Java > Java Collections Framework > Queue and Deque > Deque Interface (ArrayDeque)

ArrayDeque as a Stack: Implementing Undo/Redo

This snippet demonstrates using ArrayDeque as a stack to implement a simple undo/redo functionality.

Core Implementation

This code uses two ArrayDeque instances: history to store the previous states for undo and redoStack to store the states for redo. The type() method simulates typing text, the undo() method reverts to the previous state, and the redo() method restores the next state. The push() and pop() methods of ArrayDeque are used to implement the stack behavior.

import java.util.ArrayDeque;

public class UndoRedoExample {
    private ArrayDeque<String> history = new ArrayDeque<>();
    private ArrayDeque<String> redoStack = new ArrayDeque<>();
    private String currentText = "";

    public void type(String text) {
        history.push(currentText); // Push the current state to history
        redoStack.clear(); // Clear redo stack on new action
        currentText += text;
        System.out.println("Typed: " + text + ", Current text: " + currentText);
    }

    public void undo() {
        if (!history.isEmpty()) {
            redoStack.push(currentText); // Store current state for redo
            currentText = history.pop(); // Revert to previous state
            System.out.println("Undo, Current text: " + currentText);
        } else {
            System.out.println("Nothing to undo.");
        }
    }

    public void redo() {
        if (!redoStack.isEmpty()) {
            history.push(currentText); // Push current state to history
            currentText = redoStack.pop(); // Restore next state
            System.out.println("Redo, Current text: " + currentText);
        } else {
            System.out.println("Nothing to redo.");
        }
    }

    public static void main(String[] args) {
        UndoRedoExample editor = new UndoRedoExample();
        editor.type("Hello ");
        editor.type("World");
        editor.undo();
        editor.redo();
        editor.undo();
        editor.undo();
        editor.redo();
    }
}

Concepts Behind the Snippet

This example leverages the LIFO (Last-In-First-Out) nature of a stack, which is effectively implemented using ArrayDeque's push() and pop() methods. The history deque keeps track of the previous states, allowing the undo() operation to revert to them. The redoStack deque keeps track of states that have been undone, allowing the redo() operation to restore them.

Real-Life Use Case

This pattern is commonly used in text editors, IDEs, and graphic design software to provide undo and redo functionality. It allows users to easily revert to previous states of their work and then restore them if needed. This enhances the user experience and provides a safety net for accidental changes.

When to Use Them

Use ArrayDeque with push() and pop() methods when you need LIFO capabilities. It is preferable over LinkedList for most stack operations due to its superior performance.

← ArrayDeque Example: Adding and Removing Elements ArrayList vs LinkedList: Basic Operations →

FAQ

  • Why is ArrayDeque suitable for implementing undo/redo functionality?

    ArrayDeque provides efficient stack operations (push() and pop()) which are essential for maintaining the history of actions. Its resizable nature also allows it to accommodate a varying number of actions without a fixed size limit.
  • How can I limit the size of the history in the undo/redo example?

    You can limit the size of the history by checking the size of the history deque before pushing a new state. If the size exceeds a certain limit, remove the oldest element from the queue (using removeLast()) before adding the new one.