撤销/重做（Ctrl+Z、Ctrl+Y）的最佳数据结构是什么？

嘿，这个问题问到点子上了——撤销/重做是很多应用（比如文本编辑器、绘图工具）的核心功能，咱们从实际场景和Java面向对象的角度来掰扯清楚～

先说说老师提到的栈：为啥是经典选择？ #

栈的后进先出（LIFO）特性天然匹配“撤销最近操作”的需求，但单纯一个栈没法处理重做，所以业界常用的是双栈实现：

• 一个undoStack：存储已经执行的操作，每次完成新操作就把对应的操作对象压入这里。
• 一个redoStack：存储被撤销的操作，每次执行撤销时，从undoStack弹出操作并执行反向逻辑，再把它压入redoStack。
• 重做时，从redoStack弹出操作执行正向逻辑，再压回undoStack。

这种实现的优势很明显：

• 撤销/重做操作的时间复杂度都是O(1)，性能拉满。
• 代码实现简洁，Java里直接用LinkedList（比自带的Stack类更推荐，因为Stack继承自Vector，线程安全但有额外开销）就能搞定。

结合面向对象的思路，咱们可以用命令模式来封装操作，让扩展性更好：

// 定义命令接口，统一操作的执行和撤销行为
interface Command {
    void execute();
    void undo();
}

// 示例：文本插入操作
class InsertTextCommand implements Command {
    private StringBuilder text;
    private String insertedContent;
    private int position;

    public InsertTextCommand(StringBuilder text, String content, int pos) {
        this.text = text;
        this.insertedContent = content;
        this.position = pos;
    }

    @Override
    public void execute() {
        text.insert(position, insertedContent);
    }

    @Override
    public void undo() {
        text.delete(position, position + insertedContent.length());
    }
}

// 撤销重做管理器
class UndoRedoManager {
    private Deque<Command> undoStack = new LinkedList<>();
    private Deque<Command> redoStack = new LinkedList<>();

    public void executeCommand(Command cmd) {
        cmd.execute();
        undoStack.push(cmd);
        redoStack.clear(); // 新操作会清空重做记录，符合用户直觉
    }

    public void undo() {
        if (!undoStack.isEmpty()) {
            Command cmd = undoStack.pop();
            cmd.undo();
            redoStack.push(cmd);
        }
    }

    public void redo() {
        if (!redoStack.isEmpty()) {
            Command cmd = redoStack.pop();
            cmd.execute();
            undoStack.push(cmd);
        }
    }
}

双向链表的实现思路：适合啥场景？ #

用双向链表实现的话，核心是维护一个当前节点指针：

• 每次执行新操作，在当前节点后新增一个操作节点，同时删除当前节点之后的所有节点（因为用户在撤销后做新操作，之前的重做路径应该失效）。
• 撤销就是把当前指针移到前一个节点，恢复到对应状态。
• 重做就是把当前指针移到后一个节点，恢复到对应状态。

这种方式的优势是可以直观地遍历所有操作历史，甚至支持跳转到任意历史状态，但缺点也很明显：

• 实现复杂度更高，需要维护节点的增删和当前指针的位置，状态恢复的逻辑如果是全量保存（比如保存整个文档状态），内存开销会很大；如果是增量操作，又要和命令模式结合，反而不如双栈简洁。
• 撤销/重做的时间复杂度虽然也是O(1)，但代码的维护成本更高。

有没有更优的数据结构？ #

其实双栈+命令模式已经是目前业界最主流、最优雅的实现方案了——它兼顾了性能、简洁性和扩展性。如果你的需求是支持“跳转到任意历史版本”，那可以考虑用链表+快照的方式，但这已经不属于单纯的数据结构选择，而是结合了状态存储的设计。

二选一：哪个更适配需求？ #

• 如果你的需求是常规的撤销/重做（只支持最近操作的撤销、重做，且操作是增量的）：选双栈实现，代码简单、性能高，符合面向对象的设计思想，扩展性也强。
• 如果你的需求是需要查看完整操作历史、支持跳转到任意历史状态：可以考虑双向链表，但要注意优化状态存储的内存开销。

内容的提问来源于stack exchange，提问作者Mahmoud Khalil