Question

towers of hanoi c++ program using stacks and singly linked lists.

Answer 1

#include <iostream>

#include <cmath>

#include <cstdlib>

#include <climits>

using namespace std;

struct Stack

{

unsigned capacity;

int top;

int *array;

};

Stack* createStack(unsigned capacity)

{

Stack* stack = (Stack*) malloc(sizeof(Stack));

stack->capacity = capacity;

stack->top = -1;

stack->array = new int[capacity];

return stack;

}

int isFull(Stack* stack)

{

return (stack->top == stack->capacity - 1);

}

int isEmpty(Stack* stack)

{

return (stack->top == -1);

}

void pushDisk(Stack *stack, int disk)

{

if (isFull(stack))

return;

stack->array[++stack -> top] = disk;

}

int popDisk(Stack* stack)

{

if (isEmpty(stack))

return INT_MIN;

return stack->array[stack -> top--];

}

void moveDisk(char fromTower, char toTower, int disk)

{

printf("Move the disk %d from Tower %c to Tower %c\n", disk, fromTower, toTower);

}

void moveDisksBetweenTwoTowers(Stack *src, Stack *dest, char s, char d)

{

int tower1TopDisk = popDisk(src);

int tower2TopDisk = popDisk(dest);

// when tower 1 is empty

if (tower1TopDisk == INT_MIN)

{

pushDisk(src, tower2TopDisk);

moveDisk(d, s, tower2TopDisk);

}

// when tower 2 is empty

else if (tower2TopDisk == INT_MIN)

{

pushDisk(dest, tower1TopDisk);

moveDisk(s, d, tower1TopDisk);

}

// when top disk of tower 1 is greater than top disk of tower 2

else if (tower1TopDisk > tower2TopDisk)

{

pushDisk(src, tower1TopDisk);

pushDisk(src, tower2TopDisk);

moveDisk(d, s, tower2TopDisk);

}

// when top disk of tower 1 is less than top disk of tower 2

else

{

pushDisk(dest, tower2TopDisk);

pushDisk(dest, tower1TopDisk);

moveDisk(s, d, tower1TopDisk);

}

}

void towersOfHanoi(int numDisks, Stack *start, Stack *middle, Stack *end)

{

int i, totalMoves;

char startSymbol = '1', endSymbol = '3', midSymbol = '2';

if (numDisks % 2 == 0)

{

char temp = endSymbol;

endSymbol = midSymbol;

midSymbol = temp;

}

totalMoves = pow(2, numDisks) - 1;

for (i = numDisks; i >= 1; i--)

{

pushDisk(start, i);

}

for (i = 1; i <= totalMoves; i++)

{

if (i % 3 == 1)

moveDisksBetweenTwoTowers(start, end, startSymbol, endSymbol);

else if (i % 3 == 2)

moveDisksBetweenTwoTowers(start, middle, startSymbol, midSymbol);

else if (i % 3 == 0)

moveDisksBetweenTwoTowers(middle, end, midSymbol, endSymbol);

}

}

int main()

{

unsigned numDisks;

Stack *start, *end, *mid;

cout << endl << "How many disks? ";

cin >> numDisks;

// create three stacks of size 'numDisks'

start = createStack(numDisks);

mid = createStack(numDisks);

end = createStack(numDisks);

cout << endl;

// start the puzzle

towersOfHanoi(numDisks, start, mid, end);

return 0;

}

******************************************************************* SCREENSHOT ********************************************************