 S.Zhang - 2 years ago 133
Java Question

Using stacks to solve tower of Hanoi (java)

public static enum Action {
No, LToM, MToL, MToR, RToM
}

public static int hanoiProblem2(int num, String left, String mid, String right) {
Stack<Integer> lS = new Stack<Integer>();
Stack<Integer> mS = new Stack<Integer>();
Stack<Integer> rS = new Stack<Integer>();
lS.push(Integer.MAX_VALUE);
mS.push(Integer.MAX_VALUE);
rS.push(Integer.MAX_VALUE);
for (int i = num; i > 0; i--) {
lS.push(i);
}
Action[] record = { Action.No };
int step = 0;
while (rS.size() != num + 1) {
step += fStackTotStack(record, Action.MToL, Action.LToM, lS, mS, left, mid);
step += fStackTotStack(record, Action.LToM, Action.MToL, mS, lS, mid, left);
step += fStackTotStack(record, Action.RToM, Action.MToR, mS, rS, mid, right);
step += fStackTotStack(record, Action.MToR, Action.RToM, rS, mS, right, mid);
}
return step;
}

public static int fStackTotStack(Action[] record, Action preNoAct,
Action nowAct, Stack<Integer> fStack, Stack<Integer> tStack,
String from, String to) {
if (record != preNoAct && fStack.peek() < tStack.peek()) {
tStack.push(fStack.pop());
System.out.println("Move " + tStack.peek() + " from " + from + " to " + to);
record = nowAct;
return 1;
}
return 0;
}

public static void main(String[] args) {
int num = 4;

// solution 2
int steps2 = hanoiProblem2(num, "left", "mid", "right");
System.out.println("It will move " + steps2 + " steps.");
System.out.println("===================================");

}

This is a code for solving tower of Hanoi. It uses three stacks to simulate 3 towers.
My question is that why does it define the record variable as an array?
Action[] record = { Action.No };
record = nowAct;

I tried to change them to
Action record = Action.No;
record = nowAct;
then the code is failed to run.

I don't know the reason. I really appreciate it if someone could explain the reason.
Thanks. Steven Jeffries

In your example, record is being defined as an array because its value is being changed within the fStackTotStack method.

The simplest explanation for this is because Java passes variables by value, not by reference. It passes Object references by value as well.

Take, for example, the following code:

public void foo(int bar) {
bar += 4;
System.out.println("Foo's bar: " + bar);
}

public static void main(String[] args) {
int bar = 5;
new Foo().foo(bar);
System.out.println("Main's bar: " + bar);
}

This will print out:

Foo's bar: 9
Main's bar: 5

This is because the bar variable inside the foo function is a different variable than the one inside the main function. The value is just copied over when the method is called.

When you pass an array, the variables themselves are still different:

public void foo(int[] bar) {
bar = new int[]{9};
System.out.println("Foo's bar: " + bar);
}

public static void main(String[] args) {
int[] bar = {5};
new Foo().foo(bar);
System.out.println("Main's bar: " + bar);
}

This will yield the same results as before, because foo's bar is different than main's bar.

However, Object references are passed by value. This means that while the variables are different, the values they represent are the same. Therefore this:

public void foo(int[] bar) {
bar += 4;
System.out.println("Foo's bar: " + bar);
}

public static void main(String[] args) {
int[] bar = {5};
new Foo().foo(bar);
System.out.println("Main's bar: " + bar);
}

Will print out something different than before:

Foo's bar: 9
Main's bar: 9

This is because while foo's bar variable and main's bar variable are different variables, they point to the same underlying object. So, changes to the object itself, and not just the variable, will persist.

In your example above, the line Action[] record = { Action.No }; is creating an array that gets passed into the fStackTotStack method. Since the variable record is not being changed itself (there is no record = new Action[] {} anywhere), the array it points to is still the same one that was passed. This means that you can make changes to the object itself (in this case, an array).

Here is an article that can explain it better than I can.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download