java - 使用堆栈的汉诺塔 - 空堆栈异常

Question

我是一个编程新手。基本上我正在尝试使用堆栈实现汉诺塔。我引用了Cracking the Code Interview解决方案，它似乎有一个空堆栈异常错误。我重写了递归部分，但仍然出现此错误。为什么我会收到此错误？

import java.util.*;

public class Tower {

    private Stack<Integer> disks;
    private int index;
    public Tower(int i) {
        disks = new Stack<Integer>();
        index = i;
    }

    public int index() {
        return index;
    }

    public void add(int d) {
        if(!disks.isEmpty() && disks.peek() <= d) {
            System.out.println("Error placing disk: " + d);
        }
        else {
            disks.push(d);
        }
    }

    public void moveTopTo(Tower t) {
        int top = disks.pop();
        t.add(top);
        System.out.println("Move disk " + top
                           + " from " + index() + " to " + t.index());
    }

    public void moveDisks(int n, Tower origin, Tower buffer, Tower destination) {
        if(n == 1) {
            moveTopTo(destination);
        }
        else if(n > 0) {
            moveDisks(n - 1, origin, destination, buffer);
            moveTopTo(destination);
            moveDisks(n - 1, buffer, origin, buffer);
        }
    }

    public static void main(String[] args) {
        int n = 3;
        Tower[] towers = new Tower[n];
        for(int i = 0; i < 3; i++) {
            towers[i] = new Tower(i);
        }
        for(int i = n - 1; i >= 0; i--) {
            towers[0].add(i);
        }
        towers[0].moveDisks(n, towers[0], towers[1], towers[2]);
    }
}

Answer 1

看起来您将 moveDisks() 视为静态的:它采用三个塔参数。换句话说，它根本不是特定塔的实例方法。

但问题是，在该代码中，您调用 .moveToTop()，这当然是一个实例方法:它从这个特定的塔中移动磁盘。

作为解决方案的第一次尝试，我会尝试回到书中的解决方案，但稍微改变一下:

public void moveDisks(int n, Tower destination, Tower buffer) {
    if(n > 0) {
        moveDisks(n - 1, buffer, destination);
        moveTopTo(destination);
        buffer.moveDisks(n - 1, destination, this);
    }
}

最后一行是关键。我们说:

1. 使用目的地作为缓冲区，将 n-1 个磁盘从该塔移动到缓冲区。
2. 将塔顶的圆盘移至目的地。
3. (关键位)使用此塔作为缓冲区，将 n-1 个磁盘从缓冲区移动到目的地。

<小时/>

另一种选择是让你的方法发挥作用。如果您想这样做，请首先将 .moveDisks() 声明为 static。完成此操作后，编译器将提示 .moveToTop() 调用，该调用也需要设为静态。当您也将其设为静态时，您会发现需要通过两个塔:源和目的地。

<小时/>

目前，您混合了两种方法，这就是它出错的原因。