非递归Stack实现汉诺塔逻辑陷入无限循环的原因排查

我用Stack实现非递归汉诺塔，逻辑参考维基百科的迭代解法——核心规则是交替移动最小圆盘与非最小圆盘：最小圆盘按固定方向循环移动，两次最小圆盘移动之间，仅存在一种合法的非最小圆盘移动。我通过movedSmallest = false;来控制下一次移动最小圆盘，但输入5个圆盘时，程序运行到以下状态后陷入无限循环：

相关代码片段 #

if (tower[1].isEmpty() == false && tower[1].peek() != 1) {
    if (tower[2].isEmpty() || tower[1].peek() < tower[2].peek()) {
        int disk = tower[1].pop();
        tower[2].push(disk);
        movedSmallest = false;
        showTowers();
    } else if (tower[3].isEmpty() || tower[1].peek() < tower[3].peek()) {
        int disk = tower[1].pop();
        tower[3].push(disk);
        movedSmallest = false;
        showTowers();
    }
} else if (tower[2].isEmpty() == false && tower[2].peek() != 1) {
    if (tower[3].isEmpty() || tower[2].peek() < tower[3].peek()) {
        int disk = tower[2].pop();
        tower[3].push(disk);
        movedSmallest = false;
        showTowers();
    } if (tower[1].isEmpty() || (tower[2].isEmpty() == false && tower[2].peek() < tower[1].peek())) {
        int disk = tower[2].pop();
        tower[1].push(disk);
        movedSmallest = false;
        showTowers();
    }
} else if (tower[3].isEmpty() == false && tower[3].peek() != 1) {
        if (tower[2].isEmpty() || (tower[3].isEmpty() == false && tower[3].peek() < tower[2].peek())) {
        int disk = tower[3].pop();
        tower[2].push(disk);
        movedSmallest = false;
        showTowers();
    } else if (tower[1].isEmpty() || (tower[3].isEmpty() == false && tower[3].peek() < tower[1].peek())) {
         int disk = tower[3].pop();
         tower[1].push(disk);
        movedSmallest = false;
        showTowers();
    }
}

陷入循环前的程序输出状态 #

Enter number of disks
5
[5, 4, 3, 2, 1]
[]
[]
---------------------------------------------------------
[5, 4, 3, 2]
[]
[1]
---------------------------------------------------------
[5, 4, 3]
[2]
[1]
---------------------------------------------------------
[5, 4, 3]
[2, 1]
[]
---------------------------------------------------------
[5, 4]
[2, 1]
[3]
---------------------------------------------------------
[5, 4, 1]
[2]
[3]
---------------------------------------------------------
[5, 4, 1]
[]
[3, 2]
---------------------------------------------------------
[5, 4]
[]
[3, 2, 1]
---------------------------------------------------------
[5]
[4]
[3, 2, 1]
---------------------------------------------------------
[5]
[4, 1]
[3, 2]
---------------------------------------------------------

排查方向 #

• 检查非最小圆盘移动的分支逻辑错误：第二个else if块里的第二个判断用了if而非else if，这会导致同一轮循环中可能执行两次移动（比如从塔2移到塔3后，又尝试从塔2移到塔1），直接破坏"交替移动最小/非最小圆盘"的规则，导致状态混乱进入死循环。
• 验证movedSmallest的状态切换完整性：确认每次移动非最小圆盘后movedSmallest是否设为false，而移动最小圆盘后是否正确设为true。如果这个标志位没有正确切换，程序会一直重复同一类移动，触发死循环。
• 检查合法移动的判断条件冗余与正确性：比如第三个分支里的tower[3].isEmpty() == false属于冗余判断（外层已经确认塔3非空），且如果出现两个目标塔都满足放置条件的情况，会导致程序选择错误的移动，偏离维基百科的迭代规则，进而陷入循环。
• 跟踪循环内的状态变化：在每次循环前后打印movedSmallest的值和各塔的状态，确认死循环时程序是否在重复执行相同的无效操作，或者movedSmallest始终处于错误状态，无法切换到移动最小圆盘的逻辑。
• 确认终止条件是否有效：检查程序是否有判断"所有圆盘都移动到目标塔"的终止逻辑，若缺失或触发时机错误，也可能导致异常循环。

内容的提问来源于stack exchange，提问作者Jordan Qiu