python汉诺塔堆栈（ListStack）实现

汉诺塔问题用递归实现非常简单，但是如何把递归转换成栈（stack）
请用ListStack解法
附上测试方法

if __name__ == '__main__':
    n = 3
    result_list = HanoiTower(n)
    for item in result_list:
        print(item)

附上输出格式

使用栈（stack）解决汉诺塔问题，可以记录每一步的状态，并将其压入栈中。当需要移动盘子时，再从栈中弹出状态，然后执行这一步。

• 使用一个状态类来存储每一步的状态。这个类应该包含源柱子，辅助柱子和目标柱子的名称。
• 使用一个ListStack类来存储每一步的状态。在每次移动盘子时，我们可以将新的状态压入栈中。

下面是使用ListStack类解决汉诺塔问题的代码，以及测试用例，望采纳：

class ListStack:
    def __init__(self):
        self.items = []
    
    def push(self, item):
        self.items.append(item)
    
    def pop(self):
        return self.items.pop()
    
    def is_empty(self):
        return self.items == []
    
    def peek(self):
        return self.items[-1]
    
def HanoiTower(n, from_rod ='A', aux_rod ='B', to_rod ='C'):
    result_list = []
    stack = ListStack()
    stack.push((n, from_rod, aux_rod, to_rod))
    while not stack.is_empty():
        n, from_rod, aux_rod, to_rod = stack.pop()
        if n == 1:
            result_list.append(f"{from_rod} --> {to_rod}")
        else:
            stack.push((n-1, aux_rod, from_rod, to_rod))
            stack.push((1, from_rod, aux_rod, to_rod))
            stack.push((n-1, to_rod, aux_rod, from_rod))
    return result_list

if __name__ == '__main__':
    n = 3
    result_list = HanoiTower(n)
    for item in result_list:
        print(item)

运行结果截图如下：

class ListStack:
    def __init__(self):
        self.items = []

    def is_empty(self):
        return not self.items

    def push(self, item):
        self.items.append(item)

    def pop(self):
        return self.items.pop()

    def peek(self):
        return self.items[-1]

def hanoi(n, start, end, temp):
    if n == 1:
        print(f"Move disk {n} from {start} to {end}")
        return

    hanoi(n - 1, start, temp, end)
    print(f"Move disk {n} from {start} to {end}")
    hanoi(n - 1, temp, end, start)

def hanoi_stack(n, start, end, temp):
    stack = ListStack()
    stack.push((n, start, end, temp))

    while not stack.is_empty():
        n, start, end, temp = stack.pop()
        if n == 1:
            print(f"Move disk {n} from {start} to {end}")
        else:
            stack.push((n - 1, temp, end, start))
            stack.push((1, start, end, temp))
            stack.push((n - 1, start, temp, end))

# 调用递归版本的汉诺塔
hanoi(3, "A", "B", "C")

# 调用栈版本的汉诺塔
hanoi_stack(3, "A", "B", "C")

您好，我是有问必答小助手，您的问题已经有小伙伴帮您解答，感谢您对有问必答的支持与关注！
PS：问答VIP年卡 【限时加赠：IT技术图书免费领】，了解详情>>> https://vip.csdn.net/askvip?utm_source=1146287632