力扣算法100个实际应用场景(2)-代码编辑器的撤销重做功能

项目简介

这个项目展示了100道经典LeetCode算法题在实际工程中的应用场景，帮助学员理解算法的实用价值，建立理论与实践的桥梁。

核心目标

让算法学习更有意义，不再是纸上谈兵
帮助面试者理解算法背后的工程价值
为工程师提供算法选择的实际参考

这是栈/队列应用的第二篇：代码编辑器的撤销重做功能

视频讲解与源码领取：https://www.bilibili.com/video/BV1VYtBzpEUJ/

实际应用

在代码编辑器中，程序员经常需要撤销最近的编辑操作（Ctrl+Z），或者重做被撤销的操作（Ctrl+Y）。这需要维护一个操作历史栈，记录每次编辑的详细信息，支持复杂的多步骤撤销和重做。

撤销重做示意图

对应算法

LeetCode题目: 20. 有效的括号：https://leetcode.cn/problems/valid-parentheses/

核心思想: 编辑器撤销重做系统的核心是命令模式 + 双栈架构，这是对LeetCode 20"括号匹配"思想的深度拓展：

🔑 算法精髓：

1.命令封装的数学模型：

Command接口: C = {execute(), undo(), getState()}
操作空间: Op = {Insert, Delete, Replace, Move, ...}
状态映射: φ: State × Command → State'
逆映射: φ⁻¹: State' × Command → State

2.双栈状态机设计：

undoStack：存储可撤销的命令序列 [c₁, c₂, ..., cₙ]
redoStack：存储可重做的命令序列 [r₁, r₂, ..., rₘ]
不变性：undoStack.top() + redoStack.bottom() = 完整操作历史

3.操作可逆性保证：

幂等性：undo(undo(op)) = op（双重撤销回到原状态）
交换律约束：某些操作可交换，某些必须严格按序
补偿事务：复杂操作的逆操作可能是多步骤的补偿动作

4.内存管理与压缩：

操作合并：连续的同类操作自动合并（如连续字符输入）
快照机制：定期保存完整状态快照，减少操作链长度
LRU淘汰：超出内存限制时淘汰最老的操作记录

🎯 高级算法技巧：

1.操作压缩算法：

// 智能合并策略
if (newCmd.type == INSERT && lastCmd.type == INSERT && 
    newCmd.position == lastCmd.position + lastCmd.length) {
    // 合并连续插入操作
    lastCmd.text += newCmd.text;
}

2.分层撤销机制：

字符级撤销：撤销单个字符
词级撤销：撤销整个单词
行级撤销：撤销整行操作
语义级撤销：撤销完整的语义块（函数、类等）

3.并发安全保证：

操作原子性：使用事务确保命令执行的原子性
版本冲突检测：多用户协作时的冲突解决
操作时间戳：基于Lamport时钟的操作排序

深层技术洞察：

1.为什么选择命令模式？

解耦性：操作逻辑与UI逻辑分离
可扩展性：新操作类型无需修改现有代码
可测试性：每个命令都是独立的可测试单元
序列化：命令可持久化，支持会话恢

2.与函数式编程的关系：

每个编辑操作都是纯函数：State → State'
撤销操作是逆函数：State' → State
操作组合符合函数组合规律

3.空间-时间权衡：

全量快照：空间O(n×m)，撤销时间O(1)
增量命令：空间O(k)，撤销时间O(k)
混合策略：快照+增量的平衡方案

代码示例：参见 src/002_code_editor_undo.cpp - 完整的工业级实现

应用领域

图像编辑软件 - Photoshop、GIMP中的历史记录和撤销功能
办公软件 - Word、Excel中的编辑操作撤销和重做
数据库事务 - 数据库系统中的事务回滚和提交机制

代码示例

// 编辑器撤销重做系统 - 基于命令模式和栈结构
class EditCommand {
public:
    virtual ~EditCommand() = default;
    virtual void execute() = 0;     // 执行操作
    virtual void undo() = 0;        // 撤销操作
    virtual string getDescription() = 0;
};

class InsertTextCommand : public EditCommand {
private:
    string& document;
    int position;
    string text;
    
public:
    InsertTextCommand(string& doc, int pos, const string& txt) 
        : document(doc), position(pos), text(txt) {}
    
    void execute() override {
        document.insert(position, text);
    }
    
    void undo() override {
        document.erase(position, text.length());
    }
    
    string getDescription() override {
        return "插入文本: " + text;
    }
};

class UndoRedoManager {
private:
    stack<unique_ptr<EditCommand>> undo_stack;  // 撤销栈
    stack<unique_ptr<EditCommand>> redo_stack;  // 重做栈
    
public:
    /**
     * @brief 执行新的编辑命令
     * @param command 要执行的命令
     */
    void executeCommand(unique_ptr<EditCommand> command) {
        // 执行命令
        command->execute();
        
        // 将命令压入撤销栈
        undo_stack.push(move(command));
        
        // 清空重做栈（执行新操作后，之前的重做历史失效）
        while (!redo_stack.empty()) {
            redo_stack.pop();
        }
    }
    
    /**
     * @brief 撤销最后一个操作
     * @return 是否成功撤销
     */
    bool undo() {
        if (undo_stack.empty()) return false;
        
        // 获取最后一个命令
        auto command = move(undo_stack.top());
        undo_stack.pop();
        
        // 执行撤销操作
        command->undo();
        
        // 将命令移到重做栈
        redo_stack.push(move(command));
        
        return true;
    }
    
    /**
     * @brief 重做最后一个被撤销的操作
     * @return 是否成功重做
     */
    bool redo() {
        if (redo_stack.empty()) return false;
        
        // 获取最后一个被撤销的命令
        auto command = move(redo_stack.top());
        redo_stack.pop();
        
        // 重新执行命令
        command->execute();
        
        // 将命令移回撤销栈
        undo_stack.push(move(command));
        
        return true;
    }
    
    /**
     * @brief 检查是否可以撤销
     */
    bool canUndo() const {
        return !undo_stack.empty();
    }
    
    /**
     * @brief 检查是否可以重做
     */
    bool canRedo() const {
        return !redo_stack.empty();
    }
};

#c++##实习工作，你找得还顺利吗？##秋招##算法##牛客创作赏金赛#