Python如何实现带有撤销功能的栈_基于两个列表模拟操作历史

先说结论：Python里要实现一个可靠的撤销栈，核心思路是用两个列表——一个存当前数据，一个存操作日志。为什么非要用两个？因为撤销本质上不是简单地把操作弹出，而是状态快照回滚。你想想，如果用户连续 push(1)、push(2)、push(3)，然后撤了两次，接着再 push(4)，这时候历史栈里第3步之后的所有操作都得丢掉——如果只有一个列表，你根本不知道哪些东西是用户主动操作的，哪些是回退产生的。

问题的核心就在这里：必须把「当前数据」和「操作日志」彻底分开。data 只管当前栈顶是什么，history 则按顺序记录每次有效变更的痕迹。每条日志存成一个 (op, value) 元组，比如 push(5) 记作 ('push', 5)，pop() 记作 ('pop', x)，其中 x 是被弹出的那个值。这样撤销的时候，只需要反向执行对应的逆操作就行——不用额外保存快照，内存开销也小。

几个设计上的关键细节

history 的追加规则很简单：只有 push() 和 pop() 成功执行时才写入日志。空栈调用 pop() 不记，这点很关键，不然 history 会留下一堆无意义的记录。每次执行 undo() 的时候，从 history 末尾取出一条，根据操作类型反向执行：碰到 'push' 就执行 pop，碰到 'pop' 就往回 push 当初被弹出去的那个值。注意，这个逆操作里不能调用 self.push() 或 self.pop()——那是直接操作 self.data，否则会再次写日志，造成循环记录，history 会指数级膨胀。

更值得警惕的是边界处理。撤销之后如果用户又做了新操作（比如 push 了一个新值），那之前被撤销但还没重做的那些未来历史必须清空。标准做法是引入一个游标 position，指向当前生效的历史终点；新操作追加时直接截断。但在两个列表的模型里，更简单的方法是用切片处理：每次撤销只递减光标，新操作前执行 history = history[: cursor]。如果可以接受不要 redo()，那实现会干净很多——用户撤销后继续输入，直接清空 history 即可。大多数实际场景下，这个设定是合理的。

还有几个容易踩的坑：空栈时调用 pop() 或 undo() 应该静默失败，不要抛异常；undo() 执行前一定要检查 history 是否为空；最容易被忽略的一点——不在 undo() 里复用公开的 pop() 和 push() 方法，所有修改应该直操作 self.data。

一个够用的最小实现

下面这段代码去掉注释不到30行，覆盖 push、pop、undo 三个核心行为，没有任何外部依赖：

class UndoStack:
    def __init__(self):
        self.data = []
        self.history = []

    def push(self, x):
        self.data.append(x)
        self.history.append(('push', x))

    def pop(self):
        if not self.data:
            return None
        x = self.data.pop()
        self.history.append(('pop', x))
        return x

    def undo(self):
        if not self.history:
            return
        op, val = self.history.pop()
        if op == 'push':
            self.data.pop()      # 逆 push = pop
        elif op == 'pop':
            self.data.append(val) # 逆 pop = 把被弹出的值推回去

注意看 undo() 方法里，没有调用 self.pop() 或 self.push()——所有操作都是直接操纵 self.data。这个细节一旦写错，history 就会指数级膨胀，调试起来非常头疼。

其实写这段代码本身并不难，真正让人卡壳的是想清楚「哪些操作必须进 history，哪些只是内部状态调整」。比如清空未来历史那一步，初学者永远容易漏掉，结果撤销之后 push 进去一个值，再按 redo 整栈就乱了。能把这个逻辑理清楚，才算是真正理解了撤销栈的运作方式。