For this machine problem you are to program a solution to the Towers of

Hanoi problem. Instead of a recursive program you are to implement a

solution using a loop and a stack. The algorithm you are to implement is:

PROCEDURE HANOI

$/*$ Move n disks from pole $1$ to pole $2$ using pole $3*/$

S $$ empty stack

S $($n$,1,2,3)$

while $($S $=$ empty $)$

$($n$,$ i$,$ j$,$ k$)$ S

if n $=1$ then

move the top disk from pole i to pole k

else

S $($n $1,$ j$,$ i$,$ k$)$

S $(1,$ i$,$ j$,$ k$)$

S $($n $1,$ i$,$ k$,$ j$)$

end HANOI

S $($n$,1,2,3)$ means push $($n$,1,2,3)$ onto the stack S

$($n$,$ i$,$ j$,$ k$)$ S means to pop S and store the result in $($n$,$ i$,$ j$,$ k$)$

This notation has been used in examples in class. As usual the move statement should be implemented as output.

The stack is to be implemented using a linked list. You are to fill in the

missing parts of the provided program. Use cassert for error conditions where

ever appropriate. You should test your program for $1$ disk, $2$ disks and for $3$

disks.

#include

#include

using namespace std;

$1$

struct HanoiRecord $\{$

int $\_$numberDisks;

int $\_$sourcePole, $\_$sparePole, $\_$destinationPole;

HanoiRecord$()\{\_$sourcePole $=\_$sparePole $=\_$destinationPole $=0$;

$\_$numberDisks $=0$;

$\}$

HanoiRecord$($int numberDisks, int sourcePole, int sparePole,

int destinationPole$)\{$

$\_$numberDisks $=$ numberDisks;

$\_$sourcePole $=$ sourcePole;

$\_$sparePole $=$ sparePole;

$\_$destinationPole $=$ destinationPole;

$\}$

$\}$;

class stack $\{$

private:

struct HanoiRecordLink $\{$

HanoiRecord value;

HanoiRecordLink $*$ next;

$\}$;

HanoiRecordLink $*\_$top;

public:

stack$()\{/*$ missing code $*/\}$

void push$($ HanoiRecord $)$;

HanoiRecord pop$()$;

HanoiRecord top$()\{$

$/*$ missing code $*/$

$\}$

bool is$\_$empty$()\{/*$ missing code $*/\}$

$\}$;

void stack::push$(/*$ missing code $*/)\{$

$/*$ missing code $*/$

$\}$

HanoiRecord stack::pop$()\{$

$2$

$/*$ missing code $*/$

$\}$

$//-----------$end of stack class definition$-------------$

int main$()\{$

int numberOfDisks $=0$;

HanoiRecord tRecord;

stack HanoiStack;

cout $<<$ "How many disks? $"<<$ flush;

cin $>>$ numberOfDisks;

HanoiStack.push$(/*$ missing code $*/)$;

$/*$ missing code $*/$

$\}$