Java Reference
In-Depth Information
publicenumoperation{MOVE,TOH}
classTOHobj{
publicoperationop;
publicintnum;
publicPolestart,goal,temp;
/
**
Recursivecalloperation
*
/
TOHobj(operationo,intn,Poles,Poleg,Polet)
{op=o;num=n;start=s;goal=g;temp=t;}
/
**
MOVEoperation
*
/
TOHobj(operationo,Poles,Poleg)
{op=o;start=s;goal=g;}
}
staticvoidTOH(intn,Polestart,
Polegoal,Poletemp){
//Makeastackjustbigenough
Stack<TOHobj>S=newAStack<TOHobj>(2
*
n+1);
S.push(newTOHobj(operation.TOH,n,
start,goal,temp));
while(S.length()>0){
TOHobjit=S.pop();//Getnexttask
if(it.op==operation.MOVE)//Doamove
move(it.start,it.goal);
elseif(it.num>0){//ImitateTOHrecursive
//solution(inreverse)
S.push(newTOHobj(operation.TOH,it.num-1,
it.temp,it.goal,it.start));
S.push(newTOHobj(operation.MOVE,it.start,
it.goal));//Amovetodo
S.push(newTOHobj(operation.TOH,it.num-1,
it.start,it.temp,it.goal));
}
}
}
Figure4.23
Stack-based implementation for Towers of Hanoi.
move operation actually needs only to store information about two poles.
Thus, there are two constructors: one to store the state when imitating a
recursive call, and one to store the state for a move operation.
An array-based stack is used because we know that the stack will need
to store exactly 2n+1 elements. The new version of
TOH
begins by placing
on the stack a description of the initial problem for n rings. The rest of
the function is simply a
while
loop that pops the stack and executes the
appropriate operation. In the case of a
TOH
operation (for n > 0), we
store on the stack representations for the three operations executed by the
recursive version. However, these operations must be placed on the stack
in reverse order, so that they will be popped off in the correct order.
