python汉诺塔堆栈（ListStack）实现

Question

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

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

附上输出格式

Answer 1

使用栈（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)

运行结果截图如下：