基于Python栈实现Undo/Redo功能：解决递归溢出的实现方案

原有代码的错误根源 #

• 递归触发原因：push方法内调用undo，undo方法又反过来调用push，形成无限循环，直接触发递归深度溢出。
• 逻辑设计问题：把Undo/Redo的业务逻辑硬绑定在通用栈的push操作里，栈本身是通用LIFO（后进先出）结构，不应该内置特殊业务逻辑。
• 基础栈缺陷：原有pop方法仅移动栈顶指针，没有返回被弹出的节点，无法实现节点在两个栈之间的转移，自然没法支撑Redo逻辑。

正确实现思路 #

Undo/Redo不需要修改基础栈的通用逻辑，核心是用两个独立栈分离状态：

• current_stack：存储当前所有处于显示状态的节点，栈顶为最后添加的节点
• removed_stack：存储所有被Undo操作移除的节点，栈顶为最近被移除的节点，专门用于Redo

操作逻辑完全匹配预期的交互：

1. 新增节点时：直接把节点push到current_stack，同时清空removed_stack（一旦有新的操作历史，之前的Redo缓存直接失效，符合常规软件的交互规则）
2. 触发Ctrl+Z（Undo）时：把current_stack的栈顶节点弹出，push到removed_stack
3. 触发Ctrl+Y（Redo）时：把removed_stack的栈顶节点弹出，push回current_stack

可运行代码示例 #

class Node:
    def __init__(self, data=None):
        self.data = data
        self.next = None


class Stack:
    def __init__(self):
        self.top = None

    def push(self, item):
        # 自动包装非Node类型的输入
        if not isinstance(item, Node):
            item = Node(item)
        item.next = self.top
        self.top = item

    def pop(self):
        # 修正原方法的缺陷：返回被弹出的节点
        if self.is_empty():
            return None
        popped_node = self.top
        self.top = self.top.next
        popped_node.next = None
        return popped_node

    def is_empty(self):
        return self.top is None

    def __str__(self):
        if self.is_empty():
            return "[]"
        res = []
        current = self.top
        while current:
            res.append(str(current.data))
            current = current.next
        return f"[{'->'.join(res)}]"


class UndoRedoManager:
    # 单独封装Undo/Redo业务逻辑，和基础栈解耦
    def __init__(self):
        self.current_stack = Stack()
        self.removed_stack = Stack()

    def add_element(self, data):
        """对应新增屏幕节点的操作"""
        self.current_stack.push(data)
        # 新增操作清空所有重做缓存
        self.removed_stack = Stack()

    def undo(self):
        """对应Ctrl+Z操作"""
        if self.current_stack.is_empty():
            print("没有可撤销的操作")
            return
        popped_node = self.current_stack.pop()
        self.removed_stack.push(popped_node)

    def redo(self):
        """对应Ctrl+Y操作"""
        if self.removed_stack.is_empty():
            print("没有可重做的操作")
            return
        popped_node = self.removed_stack.pop()
        self.current_stack.push(popped_node)

    def __str__(self):
        return f"当前栈结构：{self.current_stack}"


# 测试流程，完全匹配描述的预期
if __name__ == "__main__":
    manager = UndoRedoManager()
    # 依次添加1-5
    manager.add_element(1)
    manager.add_element(2)
    manager.add_element(3)
    manager.add_element(4)
    manager.add_element(5)
    print(manager)  # 输出：当前栈结构：[5->4->3->2->1]

    # 连续按两次Ctrl+Z
    manager.undo()
    print(manager)  # 移除栈顶5，输出：当前栈结构：[4->3->2->1]
    manager.undo()
    print(manager)  # 移除栈顶4，输出：当前栈结构：[3->2->1]

    # 连续按两次Ctrl+Y
    manager.redo()
    print(manager)  # 恢复最近移除的4，输出：当前栈结构：[4->3->2->1]
    manager.redo()
    print(manager)  # 恢复最近移除的5，输出：当前栈结构：[5->4->3->2->1]

设计说明 #

• 不需要把Undo/Redo逻辑强行塞到基础Stack类里，单独封装管理器类更符合职责分离的原则，后续要扩展批量撤销、历史记录跳转等功能时不需要改动基础栈的代码。
• 代码里的removed_stack直接复用了通用Stack的能力，没有重写任何基础栈的方法，扩展性更强。

内容的提问来源于stack exchange，提问作者Asad Sheikh