Tower of Hanoi in Data Structures

public class TowerOfHanoi {

    public static void towerOfHanoi(int N, char sourceRod, char destRod, char auxRod) {
        // Base case: if N is 0, return
        if (N == 0) {
            return;
        }

        // Calling the recursive function following the observed pattern
        towerOfHanoi(N - 1, sourceRod, auxRod, destRod);

        // Printing the move that just happened
        System.out.println("Move disk " + N + " from rod " + sourceRod + " -> " + destRod);

        // Calling the recursive function following the observed pattern
        towerOfHanoi(N - 1, auxRod, destRod, sourceRod);
    }

    public static void main(String[] args) {
        // Number of disks in the given Tower of Hanoi
        int N = 3;

        // Calling the recursive function where 'A' -> source rod, 'C' -> destination rod, 'B' -> auxiliary rod
        towerOfHanoi(N, 'A', 'C', 'B');
    }
}
    

// C++ program for the Tower of Hanoi using recursion
#include 
using namespace std;
 
void TowerOfHanoi(int N, char source_rod, char dest_rod, char aux_rod){
    // Base case if n==0 return 
    if (N == 0){
        return;
    }
    // calling the recursive function by following the pattern observed
    TowerOfHanoi(N - 1, source_rod, aux_rod, dest_rod);
    
    // printing the move which happened just
    cout << "Move disk " << N << " from rod " << source_rod << " -> " << dest_rod << endl;
    
    // calling the recursive function by following the pattern observed
    TowerOfHanoi(N - 1, aux_rod, dest_rod, source_rod);
}
 
// Driver code
int main(){
    // Number of disks in the given tower of Hanoi 
    int N = 3; 
    // calling the recursive function where A-> source rod, B-> auxiliary rod, C-> destination rod
    TowerOfHanoi(N, 'A', 'C', 'B'); 
    return 0;
}

    

class Stack {
    int size;
    int top;
    int[] array;

    public Stack(int size) {
        this.size = size;
        this.top = -1;
        this.array = new int[size];
    }
}

public class TowerOfHanoiIterative {
    public static Stack createStack(int size) {
        return new Stack(size);
    }

    public static boolean isFull(Stack stack) {
        return stack.top == stack.size - 1;
    }

    public static boolean isEmpty(Stack stack) {
        return stack.top == -1;
    }

    public static void push(Stack stack, int element) {
        if (isFull(stack)) {
            return;
        }
        stack.array[++stack.top] = element;
    }

    public static int pop(Stack stack) {
        if (isEmpty(stack)) {
            return Integer.MIN_VALUE;
        }
        return stack.array[stack.top--];
    }

    public static void printDisk(char sourceRod, char destRod, int disk) {
        System.out.println("Move the disk " + disk + " from " + sourceRod + " -> " + destRod);
    }

    public static void moveDisks(Stack src, Stack dest, char s, char d) {
        int pole1 = pop(src);
        int pole2 = pop(dest);

        if (pole1 == Integer.MIN_VALUE) {
            push(src, pole2);
            printDisk(d, s, pole2);
        } else if (pole2 == Integer.MIN_VALUE) {
            push(dest, pole1);
            printDisk(s, d, pole1);
        } else if (pole1 > pole2) {
            push(src, pole1);
            push(src, pole2);
            printDisk(d, s, pole2);
        } else {
            push(dest, pole2);
            push(dest, pole1);
            printDisk(s, d, pole1);
        }
    }

    public static void tohIterative(int N, Stack src, Stack aux, Stack dest) {
        char s = 'A', d = 'C', a = 'B';

        if (N % 2 == 0) {
            char temp = d;
            d = a;
            a = temp;
        }

        int totalMoves = (int) Math.pow(2, N) - 1;

        for (int i = N; i >= 1; i--) {
            push(src, i);
        }

        for (int i = 1; i <= totalMoves; i++) {
            if (i % 3 == 1) {
                moveDisks(src, dest, s, d);
            } else if (i % 3 == 2) {
                moveDisks(src, aux, s, a);
            } else if (i % 3 == 0) {
                moveDisks(aux, dest, a, d);
            }
        }
    }

    public static void main(String[] args) {
        int N = 3;
        Stack sourceRod = createStack(N);
        Stack auxRod = createStack(N);
        Stack destRod = createStack(N);
        tohIterative(N, sourceRod, auxRod, destRod);
    }
}
    

#include 
#include 
using namespace std;
 
// Stack representation
struct Stack{
//initializing stack size, top 
unsigned size;
int top;
int *array;
};
 
// function to create a stack of the given size.
struct Stack* Create_Stack(unsigned size){
    struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack));
    stack -> size = size;
    // initialise top to -1
    stack -> top = -1;
    //dynamically allocating the memory for stack
    stack -> array = (int*) malloc(stack -> size * sizeof(int));
    return stack;   
    
}
 
// Function to check whether stack is full
int Is_Full(struct Stack* stack){
    // stack is full when top == size-1
return (stack->top == stack->size - 1);
}
 
// Function to check whether there tack is empty
int Is_Empty(struct Stack* stack){
// Stack is considered to be empty when top==-1
return (stack->top == -1);
}
 
// Function to add an item to stack. It increases top by 1
void push(struct Stack *stack, int element){
    // if the stack is full you cannot add the item to the stack
    if (Is_Full(stack))
        return;
    stack -> array[++stack -> top] = element;
}
 
// Function to remove an item from the stack. It decreases the top by 1
int pop(struct Stack* stack){
    // if the stack is empty you cannot remove any 
    if (Is_Empty(stack))
        return INT_MIN;
    return stack -> array[stack -> top--];
}
 
//Function to show the movement of disks
void printdisk(char source_rod, char dest_rod, int disk){
    cout <<"Move the disk " << disk <<" from " << source_rod << " -> "<< dest_rod << endl;
}
 
// Function to implement legal movement between two poles
void MoveDisks(struct Stack *src, struct Stack *dest, char s, char d){
    int pole1 = pop(src);
    int pole2 = pop(dest);
 
    // When pole 1 is empty
    if (pole1 == INT_MIN){
        push(src, pole2);
        //  to print the movement which just happened
        printdisk(d, s, pole2);
    }
 
    // When pole2 pole is empty
    else if (pole2 == INT_MIN){
        push(dest, pole1);
        // to print the movement which justhappenedd
        printdisk(s, d, pole1);
    }
 
    // When top disk of pole1 > top disk of pole2
    else if (pole1 > pole2){
        push(src, pole1);
        push(src, pole2);
        // to print the movement which just happend
        printdisk(d, s, pole2);
    }
 
    // When top disk of pole1 < top disk of pole2
    else{
        push(dest, pole2);
        push(dest, pole1);
        // to print the movement which just happened
        printdisk(s, d, pole1);
    }
}
 
//Function to implement TOH puzzle
void TohIterative(int N, struct Stack *src, struct Stack *aux, struct Stack *dest){
    int i, total_moves;
    char s = 'A', d = 'C', a = 'B';
 
    //If number of disks is even, then interchange the destination pole and auxiliary pole
    if (N % 2 == 0){
        char temp = d;
        d = a;
        a = temp;
    }
    total_moves = pow(2, N) - 1;
 
    //Larger disks will be pushed first
    for (i = N; i >= 1; i--)
        push(src, i);
 
    for (i = 1; i <= total_moves; i++){
        if (i % 3 == 1)
        MoveDisks(src, dest, s, d);
 
        else if (i % 3 == 2)
        MoveDisks(src, aux, s, a);
 
        else if (i % 3 == 0)
        MoveDisks(aux, dest, a, d);
    }
}
 
// Driver Program
int main(){
   
    // Total number of disks in the source peg
    unsigned N = 3;
 
    struct Stack *source_rod, *aux_rod, *dest_rod;
 
    // Create three stacks to represent three pegs and of size number of disks to hold the disks
    source_rod = Create_Stack(N);
    aux_rod = Create_Stack(N);
    dest_rod = Create_Stack(N);
 
    // Calling the Tower of Hanoi iterative approach function
    TohIterative(N, source_rod, aux_rod, dest_rod);
    return 0;
}