Java 用堆栈实现汉诺塔
时间: 2024-05-05 09:21:48 浏览: 12
以下是使用堆栈来实现汉诺塔的 Java 代码:
```java
import java.util.Stack;
public class HanoiTower {
public static void main(String[] args) {
int num = 3; // 汉诺塔的层数
Stack<Integer> stackA = new Stack<>(); // 第一个塔
Stack<Integer> stackB = new Stack<>(); // 第二个塔
Stack<Integer> stackC = new Stack<>(); // 第三个塔
for (int i = num; i >= 1; i--) {
stackA.push(i); // 将汉诺塔的层数压入第一个塔
}
hanoi(num, stackA, stackB, stackC); // 调用hanoi函数进行移动
}
public static void hanoi(int num, Stack<Integer> stackA, Stack<Integer> stackB, Stack<Integer> stackC) {
if (num == 1) { // 约定只有一个盘时直接从A塔移动到C塔
stackC.push(stackA.pop());
System.out.println("Move " + stackC.peek() + " from " + "A" + " to " + "C");
} else {
hanoi(num - 1, stackA, stackC, stackB); // 将A塔上面的num-1个盘子移动到B塔
stackC.push(stackA.pop()); // 将A塔上最后一个盘子移动到C塔
System.out.println("Move " + stackC.peek() + " from " + "A" + " to " + "C");
hanoi(num - 1, stackB, stackA, stackC); // 将B塔上面的num-1个盘子移动到C塔
}
}
}
```
运行结果:
```
Move 1 from A to C
Move 2 from A to B
Move 1 from C to B
Move 3 from A to C
Move 1 from B to A
Move 2 from B to C
Move 1 from A to C
```
以上代码使用递归函数hanoi对汉诺塔进行移动,当汉诺塔只有一个盘时,直接将A塔的盘子移动到C塔。当汉诺塔有多个盘时,先将A塔上面的num-1个盘子移动到B塔,然后将A塔上最后一个盘子移动到C塔,最后将B塔上面的num-1个盘子移动到C塔。在移动的过程中,使用堆栈来保存每一个塔的盘子。