Implement tower of hanoi using stack
Here given code implementation process.
// C program
// Implement tower of hanoi using stack
#include <stdio.h>
#include <stdlib.h>
// Define stack node
struct StackNode
{
int disk;
int source;
int auxiliary;
int destination;
struct StackNode *next;
};
// Define a custom stack
struct MyStack
{
struct StackNode *top;
int size;
};
struct MyStack *newStack()
{
//Make a stack
struct MyStack *stack = (struct MyStack *) malloc(sizeof(struct MyStack));
if (stack != NULL)
{
//Set node values
stack->top = NULL;
stack->size = 0;
}
else
{
printf("\nMemory overflow when create new stack\n");
}
}
//Create a new node of stack
struct StackNode *newNode(int disk, int source, int destination, int auxiliary)
{
//Make a new node
struct StackNode *node = (struct StackNode *) malloc(sizeof(struct StackNode));
if (node == NULL)
{
printf("\nMemory overflow when create new stack Node \n");
}
else
{
node->disk = disk;
node->source = source;
node->destination = destination;
node->auxiliary = auxiliary;
}
return node;
}
// add node at the top of stack
void push(struct MyStack *stack, struct StackNode *node)
{
node->next = stack->top;
stack->top = node;
stack->size++;
}
int isEmpty(struct MyStack *stack)
{
if (stack->size > 0 && stack->top != NULL)
{
return 0;
}
else
{
return 1;
}
}
// return top element of stack
struct StackNode *peek(struct MyStack *stack)
{
return stack->top;
}
// Remove top element of stack
void pop(struct MyStack *stack)
{
if (stack->size > 0 && stack->top != NULL)
{
struct StackNode *temp = stack->top;
// Change top element of stack
stack->top = temp->next;
// remove previous top
free(temp);
temp = NULL;
stack->size--;
}
}
// Display the movement of current disk
void printResult(struct StackNode *node)
{
printf(" Move disk %d from tower [%d] to [%d]\n", node->disk, node->source, node->destination);
}
// Iterative tower of hanoi implementation
void towerOfHanoi(int total_disk)
{
if (total_disk > 0)
{
// Display total disk
printf("\n Total Disk %d \n", total_disk);
int disk = total_disk;
// Set the poles tag
int source = 1;
int auxiliary = 2;
int destination = 3;
// Create a stack which is hold information of execute steps
struct MyStack *stack = newStack();
struct StackNode *node = NULL;
int temp = 0;
while (disk > 0 || isEmpty(stack) == 0)
{
if (disk > 0)
{
node = newNode(disk, source, destination, auxiliary);
// Add stack node
push(stack, node);
// Change execution variables
temp = destination;
destination = auxiliary;
auxiliary = temp;
// Reduce disk size
disk--;
}
else
{
// Get top element of stack
node = peek(stack);
// Display movement of disk
printResult(node);
// Get new execution info
source = node->auxiliary;
destination = node->destination;
disk = node->disk - 1;
auxiliary = node->source;
// Remove stack elemnt
pop(stack);
}
}
}
}
int main()
{
// Test case
towerOfHanoi(4);
towerOfHanoi(3);
return 0;
}
Output
Total Disk 4
Move disk 1 from tower [1] to [2]
Move disk 2 from tower [1] to [3]
Move disk 1 from tower [2] to [3]
Move disk 3 from tower [1] to [2]
Move disk 1 from tower [3] to [1]
Move disk 2 from tower [3] to [2]
Move disk 1 from tower [1] to [2]
Move disk 4 from tower [1] to [3]
Move disk 1 from tower [2] to [3]
Move disk 2 from tower [2] to [1]
Move disk 1 from tower [3] to [1]
Move disk 3 from tower [2] to [3]
Move disk 1 from tower [1] to [2]
Move disk 2 from tower [1] to [3]
Move disk 1 from tower [2] to [3]
Total Disk 3
Move disk 1 from tower [1] to [3]
Move disk 2 from tower [1] to [2]
Move disk 1 from tower [3] to [2]
Move disk 3 from tower [1] to [3]
Move disk 1 from tower [2] to [1]
Move disk 2 from tower [2] to [3]
Move disk 1 from tower [1] to [3]
/*
Java Program
Implement tower of hanoi using stack
*/
// Define stack node
class StackNode
{
public int disk;
public int source;
public int auxiliary;
public int destination;
public StackNode next;
public StackNode(int disk,int source,int destination,int auxiliary)
{
this.disk = disk;
this.source = source;
this.destination = destination;
this.auxiliary = auxiliary;
}
// Display the movement of current disk
public void printResult()
{
System.out.print(" Move disk " + this.disk + " from tower [" + this.source + "] to [" + this.destination + "]\n");
}
}
// Define a custom stack
class MyStack
{
public StackNode top;
public int size;
public MyStack()
{
//Set node values
this.top = null;
this.size = 0;
}
// Add node at the top of stack
public void push(StackNode node)
{
node.next = this.top;
this.top = node;
this.size++;
}
public boolean isEmpty()
{
if (this.size > 0 && this.top != null)
{
return false;
}
else
{
return true;
}
}
// Remove top element of stack
public void pop()
{
if (this.size > 0 && this.top != null)
{
StackNode temp = this.top;
// Change top element of stack
this.top = temp.next;
// remove previous top
temp = null;
this.size--;
}
}
// return top element of stack
public StackNode peek()
{
return this.top;
}
}
public class TowerOfHanoi
{
public MyStack stack;
public TowerOfHanoi()
{
this.stack = new MyStack();
}
// Iterative tower of hanoi implementation
public void towerOfHanoi(int total_disk)
{
if (total_disk > 0)
{
// Display total disk
System.out.print("\n Total Disk " + total_disk + " \n");
int disk = total_disk;
// Set the poles tag
int source = 1;
int auxiliary = 2;
int destination = 3;
StackNode node = null;
int temp = 0;
while (disk > 0 || this.stack.isEmpty() == false)
{
if (disk > 0)
{
node = new StackNode(disk, source, destination, auxiliary);
// Add stack node
this.stack.push(node);
// Change execution variables
temp = destination;
destination = auxiliary;
auxiliary = temp;
// Reduce disk size
disk--;
}
else
{
// Get top element of stack
node = this.stack.peek();
// Display movement of disk
node.printResult();
// Get new execution info
source = node.auxiliary;
destination = node.destination;
disk = node.disk - 1;
auxiliary = node.source;
// Remove stack elemnt
this.stack.pop();
}
}
}
}
public static void main(String[] args)
{
TowerOfHanoi process = new TowerOfHanoi();
// Test case
process.towerOfHanoi(4);
process.towerOfHanoi(3);
}
}
Output
Total Disk 4
Move disk 1 from tower [1] to [2]
Move disk 2 from tower [1] to [3]
Move disk 1 from tower [2] to [3]
Move disk 3 from tower [1] to [2]
Move disk 1 from tower [3] to [1]
Move disk 2 from tower [3] to [2]
Move disk 1 from tower [1] to [2]
Move disk 4 from tower [1] to [3]
Move disk 1 from tower [2] to [3]
Move disk 2 from tower [2] to [1]
Move disk 1 from tower [3] to [1]
Move disk 3 from tower [2] to [3]
Move disk 1 from tower [1] to [2]
Move disk 2 from tower [1] to [3]
Move disk 1 from tower [2] to [3]
Total Disk 3
Move disk 1 from tower [1] to [3]
Move disk 2 from tower [1] to [2]
Move disk 1 from tower [3] to [2]
Move disk 3 from tower [1] to [3]
Move disk 1 from tower [2] to [1]
Move disk 2 from tower [2] to [3]
Move disk 1 from tower [1] to [3]
// Include header file
#include <iostream>
using namespace std;
/*
C++ Program
Implement tower of hanoi using stack
*/
// Define stack node
class StackNode
{
public: int disk;
int source;
int auxiliary;
int destination;
StackNode *next;
StackNode(int disk, int source, int destination, int auxiliary)
{
this->disk = disk;
this->source = source;
this->destination = destination;
this->auxiliary = auxiliary;
}
// Display the movement of current disk
void printResult()
{
cout << " Move disk " << this->disk << " from tower [" << this->source << "] to [" << this->destination << "]\n";
}
};
// Define a custom stack
class MyStack
{
public: StackNode *top;
int size;
MyStack()
{
//Set node values
this->top = NULL;
this->size = 0;
}
// Add node at the top of stack
void push(StackNode *node)
{
node->next = this->top;
this->top = node;
this->size++;
}
bool isEmpty()
{
if (this->size > 0 && this->top != NULL)
{
return false;
}
else
{
return true;
}
}
// Remove top element of stack
void pop()
{
if (this->size > 0 && this->top != NULL)
{
StackNode *temp = this->top;
// Change top element of stack
this->top = temp->next;
// remove previous top
temp = NULL;
this->size--;
}
}
// return top element of stack
StackNode *peek()
{
return this->top;
}
};
class TowerOfHanoi
{
public: MyStack *stack;
TowerOfHanoi()
{
this->stack = new MyStack();
}
// Iterative tower of hanoi implementation
void towerOfHanoi(int totalDisk)
{
if (totalDisk > 0)
{
// Display total disk
cout << "\n Total Disk " << totalDisk << " \n";
int disk = totalDisk;
// Set the poles tag
int source = 1;
int auxiliary = 2;
int destination = 3;
StackNode *node = NULL;
int temp = 0;
while (disk > 0 || this->stack->isEmpty() == false)
{
if (disk > 0)
{
// Reduce disk size
node = new StackNode(disk, source, destination, auxiliary);
// Add stack node
this->stack->push(node);
// Change execution variables
temp = destination;
destination = auxiliary;
auxiliary = temp;
disk--;
}
else
{
// Get top element of stack
node = this->stack->peek();
// Display movement of disk
node->printResult();
// Get new execution info
source = node->auxiliary;
destination = node->destination;
disk = node->disk - 1;
auxiliary = node->source;
// Remove stack elemnt
this->stack->pop();
}
}
}
}
};
int main()
{
TowerOfHanoi process = TowerOfHanoi();
// Test case
process.towerOfHanoi(4);
process.towerOfHanoi(3);
return 0;
}
Output
Total Disk 4
Move disk 1 from tower [1] to [2]
Move disk 2 from tower [1] to [3]
Move disk 1 from tower [2] to [3]
Move disk 3 from tower [1] to [2]
Move disk 1 from tower [3] to [1]
Move disk 2 from tower [3] to [2]
Move disk 1 from tower [1] to [2]
Move disk 4 from tower [1] to [3]
Move disk 1 from tower [2] to [3]
Move disk 2 from tower [2] to [1]
Move disk 1 from tower [3] to [1]
Move disk 3 from tower [2] to [3]
Move disk 1 from tower [1] to [2]
Move disk 2 from tower [1] to [3]
Move disk 1 from tower [2] to [3]
Total Disk 3
Move disk 1 from tower [1] to [3]
Move disk 2 from tower [1] to [2]
Move disk 1 from tower [3] to [2]
Move disk 3 from tower [1] to [3]
Move disk 1 from tower [2] to [1]
Move disk 2 from tower [2] to [3]
Move disk 1 from tower [1] to [3]
// Include namespace system
using System;
/*
C# Program
Implement tower of hanoi using stack
*/
// Define stack node
public class StackNode
{
public int disk;
public int source;
public int auxiliary;
public int destination;
public StackNode next;
public StackNode(int disk, int source, int destination, int auxiliary)
{
this.disk = disk;
this.source = source;
this.destination = destination;
this.auxiliary = auxiliary;
}
// Display the movement of current disk
public void printResult()
{
Console.Write(" Move disk " + this.disk + " from tower [" + this.source + "] to [" + this.destination + "]\n");
}
}
// Define a custom stack
public class MyStack
{
public StackNode top;
public int size;
public MyStack()
{
//Set node values
this.top = null;
this.size = 0;
}
// Add node at the top of stack
public void push(StackNode node)
{
node.next = this.top;
this.top = node;
this.size++;
}
public Boolean isEmpty()
{
if (this.size > 0 && this.top != null)
{
return false;
}
else
{
return true;
}
}
// Remove top element of stack
public void pop()
{
if (this.size > 0 && this.top != null)
{
StackNode temp = this.top;
// Change top element of stack
this.top = temp.next;
// remove previous top
temp = null;
this.size--;
}
}
// return top element of stack
public StackNode peek()
{
return this.top;
}
}
public class TowerOfHanoi
{
public MyStack stack;
public TowerOfHanoi()
{
this.stack = new MyStack();
}
// Iterative tower of hanoi implementation
public void towerOfHanoi(int totalDisk)
{
if (totalDisk > 0)
{
// Display total disk
Console.Write("\n Total Disk " + totalDisk + " \n");
int disk = totalDisk;
// Set the poles tag
int source = 1;
int auxiliary = 2;
int destination = 3;
StackNode node = null;
int temp = 0;
while (disk > 0 || this.stack.isEmpty() == false)
{
if (disk > 0)
{
// Reduce disk size
node = new StackNode(disk, source, destination, auxiliary);
// Add stack node
this.stack.push(node);
// Change execution variables
temp = destination;
destination = auxiliary;
auxiliary = temp;
disk--;
}
else
{
// Get top element of stack
node = this.stack.peek();
// Display movement of disk
node.printResult();
// Get new execution info
source = node.auxiliary;
destination = node.destination;
disk = node.disk - 1;
auxiliary = node.source;
// Remove stack elemnt
this.stack.pop();
}
}
}
}
public static void Main(String[] args)
{
TowerOfHanoi process = new TowerOfHanoi();
// Test case
process.towerOfHanoi(4);
process.towerOfHanoi(3);
}
}
Output
Total Disk 4
Move disk 1 from tower [1] to [2]
Move disk 2 from tower [1] to [3]
Move disk 1 from tower [2] to [3]
Move disk 3 from tower [1] to [2]
Move disk 1 from tower [3] to [1]
Move disk 2 from tower [3] to [2]
Move disk 1 from tower [1] to [2]
Move disk 4 from tower [1] to [3]
Move disk 1 from tower [2] to [3]
Move disk 2 from tower [2] to [1]
Move disk 1 from tower [3] to [1]
Move disk 3 from tower [2] to [3]
Move disk 1 from tower [1] to [2]
Move disk 2 from tower [1] to [3]
Move disk 1 from tower [2] to [3]
Total Disk 3
Move disk 1 from tower [1] to [3]
Move disk 2 from tower [1] to [2]
Move disk 1 from tower [3] to [2]
Move disk 3 from tower [1] to [3]
Move disk 1 from tower [2] to [1]
Move disk 2 from tower [2] to [3]
Move disk 1 from tower [1] to [3]
<?php
/*
Php Program
Implement tower of hanoi using stack
*/
// Define stack node
class StackNode
{
public $disk;
public $source;
public $auxiliary;
public $destination;
public $next;
function __construct($disk, $source, $destination, $auxiliary)
{
$this->disk = $disk;
$this->source = $source;
$this->destination = $destination;
$this->auxiliary = $auxiliary;
}
// Display the movement of current disk
public function printResult()
{
echo " Move disk ". $this->disk ." from tower [". $this->source ."] to [". $this->destination ."]\n";
}
}
// Define a custom stack
class MyStack
{
public $top;
public $size;
function __construct()
{
//Set node values
$this->top = null;
$this->size = 0;
}
// Add node at the top of stack
public function push($node)
{
$node->next = $this->top;
$this->top = $node;
$this->size++;
}
public function isEmpty()
{
if ($this->size > 0 && $this->top != null)
{
return false;
}
else
{
return true;
}
}
// Remove top element of stack
public function pop()
{
if ($this->size > 0 && $this->top != null)
{
$temp = $this->top;
// Change top element of stack
$this->top = $temp->next;
// remove previous top
$temp = null;
$this->size--;
}
}
// return top element of stack
public function peek()
{
return $this->top;
}
}
class TowerOfHanoi
{
public $stack;
function __construct()
{
$this->stack = new MyStack();
}
// Iterative tower of hanoi implementation
public function towerOfHanoi($totalDisk)
{
if ($totalDisk > 0)
{
// Display total disk
echo "\n Total Disk ". $totalDisk ." \n";
$disk = $totalDisk;
// Set the poles tag
$source = 1;
$auxiliary = 2;
$destination = 3;
$node = null;
$temp = 0;
while ($disk > 0 || $this->stack->isEmpty() == false)
{
if ($disk > 0)
{
// Reduce disk size
$node = new StackNode($disk, $source, $destination, $auxiliary);
// Add stack node
$this->stack->push($node);
// Change execution variables
$temp = $destination;
$destination = $auxiliary;
$auxiliary = $temp;
$disk--;
}
else
{
// Get top element of stack
$node = $this->stack->peek();
// Display movement of disk
$node->printResult();
// Get new execution info
$source = $node->auxiliary;
$destination = $node->destination;
$disk = $node->disk - 1;
$auxiliary = $node->source;
// Remove stack elemnt
$this->stack->pop();
}
}
}
}
}
function main()
{
$process = new TowerOfHanoi();
// Test case
$process->towerOfHanoi(4);
$process->towerOfHanoi(3);
}
main();
Output
Total Disk 4
Move disk 1 from tower [1] to [2]
Move disk 2 from tower [1] to [3]
Move disk 1 from tower [2] to [3]
Move disk 3 from tower [1] to [2]
Move disk 1 from tower [3] to [1]
Move disk 2 from tower [3] to [2]
Move disk 1 from tower [1] to [2]
Move disk 4 from tower [1] to [3]
Move disk 1 from tower [2] to [3]
Move disk 2 from tower [2] to [1]
Move disk 1 from tower [3] to [1]
Move disk 3 from tower [2] to [3]
Move disk 1 from tower [1] to [2]
Move disk 2 from tower [1] to [3]
Move disk 1 from tower [2] to [3]
Total Disk 3
Move disk 1 from tower [1] to [3]
Move disk 2 from tower [1] to [2]
Move disk 1 from tower [3] to [2]
Move disk 3 from tower [1] to [3]
Move disk 1 from tower [2] to [1]
Move disk 2 from tower [2] to [3]
Move disk 1 from tower [1] to [3]
/*
Node Js Program
Implement tower of hanoi using stack
*/
// Define stack node
class StackNode
{
constructor(disk, source, destination, auxiliary)
{
this.disk = disk;
this.source = source;
this.destination = destination;
this.auxiliary = auxiliary;
}
// Display the movement of current disk
printResult()
{
process.stdout.write(" Move disk " + this.disk + " from tower [" + this.source + "] to [" + this.destination + "]\n");
}
}
// Define a custom stack
class MyStack
{
constructor()
{
//Set node values
this.top = null;
this.size = 0;
}
// Add node at the top of stack
push(node)
{
node.next = this.top;
this.top = node;
this.size++;
}
isEmpty()
{
if (this.size > 0 && this.top != null)
{
return false;
}
else
{
return true;
}
}
// Remove top element of stack
pop()
{
if (this.size > 0 && this.top != null)
{
var temp = this.top;
// Change top element of stack
this.top = temp.next;
// remove previous top
temp = null;
this.size--;
}
}
// return top element of stack
peek()
{
return this.top;
}
}
class TowerOfHanoi
{
constructor()
{
this.stack = new MyStack();
}
// Iterative tower of hanoi implementation
towerOfHanoi(totalDisk)
{
if (totalDisk > 0)
{
// Display total disk
process.stdout.write("\n Total Disk " + totalDisk + " \n");
var disk = totalDisk;
// Set the poles tag
var source = 1;
var auxiliary = 2;
var destination = 3;
var node = null;
var temp = 0;
while (disk > 0 || this.stack.isEmpty() == false)
{
if (disk > 0)
{
// Reduce disk size
node = new StackNode(disk, source, destination, auxiliary);
// Add stack node
this.stack.push(node);
// Change execution variables
temp = destination;
destination = auxiliary;
auxiliary = temp;
disk--;
}
else
{
// Get top element of stack
node = this.stack.peek();
// Display movement of disk
node.printResult();
// Get new execution info
source = node.auxiliary;
destination = node.destination;
disk = node.disk - 1;
auxiliary = node.source;
// Remove stack elemnt
this.stack.pop();
}
}
}
}
}
function main()
{
var process = new TowerOfHanoi();
// Test case
process.towerOfHanoi(4);
process.towerOfHanoi(3);
}
main();
Output
Total Disk 4
Move disk 1 from tower [1] to [2]
Move disk 2 from tower [1] to [3]
Move disk 1 from tower [2] to [3]
Move disk 3 from tower [1] to [2]
Move disk 1 from tower [3] to [1]
Move disk 2 from tower [3] to [2]
Move disk 1 from tower [1] to [2]
Move disk 4 from tower [1] to [3]
Move disk 1 from tower [2] to [3]
Move disk 2 from tower [2] to [1]
Move disk 1 from tower [3] to [1]
Move disk 3 from tower [2] to [3]
Move disk 1 from tower [1] to [2]
Move disk 2 from tower [1] to [3]
Move disk 1 from tower [2] to [3]
Total Disk 3
Move disk 1 from tower [1] to [3]
Move disk 2 from tower [1] to [2]
Move disk 1 from tower [3] to [2]
Move disk 3 from tower [1] to [3]
Move disk 1 from tower [2] to [1]
Move disk 2 from tower [2] to [3]
Move disk 1 from tower [1] to [3]
# Python 3 Program
# Implement tower of hanoi using stack
# Define stack node
class StackNode :
def __init__(self, disk, source, destination, auxiliary) :
self.disk = disk
self.source = source
self.destination = destination
self.auxiliary = auxiliary
# Display the movement of current disk
def printResult(self) :
print(" Move disk [{0}] from tower [{1}] to [{2}]".format(self.disk,self.source,self.destination))
# Define a custom stack
class MyStack :
def __init__(self) :
# Set node values
self.top = None
self.size = 0
# Add node at the top of stack
def push(self, node) :
node.next = self.top
self.top = node
self.size += 1
def isEmpty(self) :
if (self.size > 0 and self.top != None) :
return False
else :
return True
# Remove top element of stack
def pop(self) :
if (self.size > 0 and self.top != None) :
temp = self.top
# Change top element of stack
self.top = temp.next
# remove previous top
temp = None
self.size -= 1
# return top element of stack
def peek(self) :
return self.top
class TowerOfHanoi :
def __init__(self) :
self.stack = MyStack()
# Iterative tower of hanoi implementation
def towerOfHanoi(self, totalDisk) :
if (totalDisk > 0) :
# Display total disk
print("\n Total Disk ", totalDisk ," ")
disk = totalDisk
# Set the poles tag
source = 1
auxiliary = 2
destination = 3
node = None
temp = 0
while (disk > 0 or self.stack.isEmpty() == False) :
if (disk > 0) :
node = StackNode(disk, source, destination, auxiliary)
# Add stack node
self.stack.push(node)
# Change execution variables
temp = destination
destination = auxiliary
auxiliary = temp
# Reduce disk size
disk -= 1
else :
# Get top element of stack
node = self.stack.peek()
# Display movement of disk
node.printResult()
# Get new execution info
source = node.auxiliary
destination = node.destination
disk = node.disk - 1
auxiliary = node.source
# Remove stack elemnt
self.stack.pop()
def main() :
process = TowerOfHanoi()
# Test case
process.towerOfHanoi(4)
process.towerOfHanoi(3)
if __name__ == "__main__": main()
Output
Total Disk 4
Move disk [1] from tower [1] to [2]
Move disk [2] from tower [1] to [3]
Move disk [1] from tower [2] to [3]
Move disk [3] from tower [1] to [2]
Move disk [1] from tower [3] to [1]
Move disk [2] from tower [3] to [2]
Move disk [1] from tower [1] to [2]
Move disk [4] from tower [1] to [3]
Move disk [1] from tower [2] to [3]
Move disk [2] from tower [2] to [1]
Move disk [1] from tower [3] to [1]
Move disk [3] from tower [2] to [3]
Move disk [1] from tower [1] to [2]
Move disk [2] from tower [1] to [3]
Move disk [1] from tower [2] to [3]
Total Disk 3
Move disk [1] from tower [1] to [3]
Move disk [2] from tower [1] to [2]
Move disk [1] from tower [3] to [2]
Move disk [3] from tower [1] to [3]
Move disk [1] from tower [2] to [1]
Move disk [2] from tower [2] to [3]
Move disk [1] from tower [1] to [3]
# Ruby Program
# Implement tower of hanoi using stack
# Define stack node
class StackNode
# Define the accessor and reader of class StackNode
attr_reader :disk, :source, :auxiliary, :destination, :next
attr_accessor :disk, :source, :auxiliary, :destination, :next
def initialize(disk, source, destination, auxiliary)
self.disk = disk
self.source = source
self.destination = destination
self.auxiliary = auxiliary
end
# Display the movement of current disk
def printResult()
print(" Move disk ", self.disk ," from tower [", self.source ,"] to [", self.destination ,"]\n")
end
end
# Define a custom stack
class MyStack
# Define the accessor and reader of class MyStack
attr_reader :top, :size
attr_accessor :top, :size
def initialize()
# Set node values
self.top = nil
self.size = 0
end
# Add node at the top of stack
def push(node)
node.next = self.top
self.top = node
self.size += 1
end
def isEmpty()
if (self.size > 0 && self.top != nil)
return false
else
return true
end
end
# Remove top element of stack
def pop()
if (self.size > 0 && self.top != nil)
temp = self.top
# Change top element of stack
self.top = temp.next
# remove previous top
temp = nil
self.size -= 1
end
end
# return top element of stack
def peek()
return self.top
end
end
class TowerOfHanoi
# Define the accessor and reader of class TowerOfHanoi
attr_reader :stack
attr_accessor :stack
def initialize()
self.stack = MyStack.new()
end
# Iterative tower of hanoi implementation
def towerOfHanoi(totalDisk)
if (totalDisk > 0)
# Display total disk
print("\n Total Disk ", totalDisk ," \n")
disk = totalDisk
# Set the poles tag
source = 1
auxiliary = 2
destination = 3
node = nil
temp = 0
while (disk > 0 || self.stack.isEmpty() == false)
if (disk > 0)
node = StackNode.new(disk, source, destination, auxiliary)
# Add stack node
self.stack.push(node)
# Change execution variables
temp = destination
destination = auxiliary
auxiliary = temp
# Reduce disk size
disk -= 1
else
# Get top element of stack
node = self.stack.peek()
# Display movement of disk
node.printResult()
# Get new execution info
source = node.auxiliary
destination = node.destination
disk = node.disk - 1
auxiliary = node.source
# Remove stack elemnt
self.stack.pop()
end
end
end
end
end
def main()
process = TowerOfHanoi.new()
# Test case
process.towerOfHanoi(4)
process.towerOfHanoi(3)
end
main()
Output
Total Disk 4
Move disk 1 from tower [1] to [2]
Move disk 2 from tower [1] to [3]
Move disk 1 from tower [2] to [3]
Move disk 3 from tower [1] to [2]
Move disk 1 from tower [3] to [1]
Move disk 2 from tower [3] to [2]
Move disk 1 from tower [1] to [2]
Move disk 4 from tower [1] to [3]
Move disk 1 from tower [2] to [3]
Move disk 2 from tower [2] to [1]
Move disk 1 from tower [3] to [1]
Move disk 3 from tower [2] to [3]
Move disk 1 from tower [1] to [2]
Move disk 2 from tower [1] to [3]
Move disk 1 from tower [2] to [3]
Total Disk 3
Move disk 1 from tower [1] to [3]
Move disk 2 from tower [1] to [2]
Move disk 1 from tower [3] to [2]
Move disk 3 from tower [1] to [3]
Move disk 1 from tower [2] to [1]
Move disk 2 from tower [2] to [3]
Move disk 1 from tower [1] to [3]
/*
Scala Program
Implement tower of hanoi using stack
*/
// Define stack node
class StackNode(var disk: Int , var source: Int , var auxiliary: Int , var destination: Int , var next: StackNode)
{
def this(disk: Int, source: Int, destination: Int, auxiliary: Int)
{
this(disk, source, auxiliary, destination, null);
}
// Display the movement of current disk
def printResult(): Unit = {
print(" Move disk " + this.disk + " from tower [" + this.source + "] to [" + this.destination + "]\n");
}
}
// Define a custom stack
class MyStack(var top: StackNode , var size: Int)
{
def this()
{
this(null, 0);
}
// Add node at the top of stack
def push(node: StackNode): Unit = {
node.next = this.top;
this.top = node;
this.size += 1;
}
def isEmpty(): Boolean = {
if (this.size > 0 && this.top != null)
{
return false;
}
else
{
return true;
}
}
// Remove top element of stack
def pop(): Unit = {
if (this.size > 0 && this.top != null)
{
var temp: StackNode = this.top;
// Change top element of stack
this.top = temp.next;
// remove previous top
temp = null;
this.size -= 1;
}
}
// return top element of stack
def peek(): StackNode = {
return this.top;
}
}
class TowerOfHanoi(var stack: MyStack)
{
def this()
{
this(new MyStack());
}
// Iterative tower of hanoi implementation
def towerOfHanoi(totalDisk: Int): Unit = {
if (totalDisk > 0)
{
// Display total disk
print("\n Total Disk " + totalDisk + " \n");
var disk: Int = totalDisk;
// Set the poles tag
var source: Int = 1;
var auxiliary: Int = 2;
var destination: Int = 3;
var node: StackNode = null;
var temp: Int = 0;
while (disk > 0 || this.stack.isEmpty() == false)
{
if (disk > 0)
{
// Reduce disk size
node = new StackNode(disk, source, destination, auxiliary);
// Add stack node
this.stack.push(node);
// Change execution variables
temp = destination;
destination = auxiliary;
auxiliary = temp;
disk -= 1;
}
else
{
// Get top element of stack
node = this.stack.peek();
// Display movement of disk
node.printResult();
// Get new execution info
source = node.auxiliary;
destination = node.destination;
disk = node.disk - 1;
auxiliary = node.source;
// Remove stack elemnt
this.stack.pop();
}
}
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var process: TowerOfHanoi = new TowerOfHanoi();
// Test case
process.towerOfHanoi(4);
process.towerOfHanoi(3);
}
}
Output
Total Disk 4
Move disk 1 from tower [1] to [2]
Move disk 2 from tower [1] to [3]
Move disk 1 from tower [2] to [3]
Move disk 3 from tower [1] to [2]
Move disk 1 from tower [3] to [1]
Move disk 2 from tower [3] to [2]
Move disk 1 from tower [1] to [2]
Move disk 4 from tower [1] to [3]
Move disk 1 from tower [2] to [3]
Move disk 2 from tower [2] to [1]
Move disk 1 from tower [3] to [1]
Move disk 3 from tower [2] to [3]
Move disk 1 from tower [1] to [2]
Move disk 2 from tower [1] to [3]
Move disk 1 from tower [2] to [3]
Total Disk 3
Move disk 1 from tower [1] to [3]
Move disk 2 from tower [1] to [2]
Move disk 1 from tower [3] to [2]
Move disk 3 from tower [1] to [3]
Move disk 1 from tower [2] to [1]
Move disk 2 from tower [2] to [3]
Move disk 1 from tower [1] to [3]
/*
Swift 4 Program
Implement tower of hanoi using stack
*/
// Define stack node
class StackNode
{
var disk: Int;
var source: Int;
var auxiliary: Int;
var destination: Int;
var next: StackNode? ;
init(_ disk: Int, _ source: Int, _ destination: Int, _ auxiliary: Int)
{
self.disk = disk;
self.source = source;
self.destination = destination;
self.auxiliary = auxiliary;
}
// Display the movement of current disk
func printResult()
{
print(" Move disk [\(self.disk)] from tower [\(self.source)] to [\(self.destination)]");
}
}
// Define a custom stack
class MyStack
{
var top: StackNode? ;
var size: Int;
init()
{
//Set node values
self.top = nil;
self.size = 0;
}
// Add node at the top of stack
func push(_ node: StackNode? )
{
node!.next = self.top;
self.top = node;
self.size += 1;
}
func isEmpty()->Bool
{
if (self.size > 0 && self.top != nil)
{
return false;
}
else
{
return true;
}
}
// Remove top element of stack
func pop()
{
if (self.size > 0 && self.top != nil)
{
var temp: StackNode? = self.top;
// Change top element of stack
self.top = temp!.next;
// remove previous top
temp = nil;
self.size -= 1;
}
}
// return top element of stack
func peek()->StackNode?
{
return self.top;
}
}
class TowerOfHanoi
{
var stack: MyStack? ;
init()
{
self.stack = MyStack();
}
// Iterative tower of hanoi implementation
func towerOfHanoi(_ totalDisk: Int)
{
if (totalDisk > 0)
{
// Display total disk
print("\n Total Disk ", totalDisk ," ");
var disk: Int = totalDisk;
// Set the poles tag
var source: Int = 1;
var auxiliary: Int = 2;
var destination: Int = 3;
var node: StackNode? = nil;
var temp: Int = 0;
while (disk > 0 || self.stack!.isEmpty() == false)
{
if (disk > 0)
{
// Reduce disk size
node = StackNode(disk, source, destination, auxiliary);
// Add stack node
self.stack!.push(node);
// Change execution variables
temp = destination;
destination = auxiliary;
auxiliary = temp;
disk -= 1;
}
else
{
// Get top element of stack
node = self.stack!.peek();
// Display movement of disk
node!.printResult();
// Get new execution info
source = node!.auxiliary;
destination = node!.destination;
disk = node!.disk - 1;
auxiliary = node!.source;
// Remove stack elemnt
self.stack!.pop();
}
}
}
}
}
func main()
{
let process: TowerOfHanoi = TowerOfHanoi();
// Test case
process.towerOfHanoi(4);
process.towerOfHanoi(3);
}
main();
Output
Total Disk 4
Move disk [1] from tower [1] to [2]
Move disk [2] from tower [1] to [3]
Move disk [1] from tower [2] to [3]
Move disk [3] from tower [1] to [2]
Move disk [1] from tower [3] to [1]
Move disk [2] from tower [3] to [2]
Move disk [1] from tower [1] to [2]
Move disk [4] from tower [1] to [3]
Move disk [1] from tower [2] to [3]
Move disk [2] from tower [2] to [1]
Move disk [1] from tower [3] to [1]
Move disk [3] from tower [2] to [3]
Move disk [1] from tower [1] to [2]
Move disk [2] from tower [1] to [3]
Move disk [1] from tower [2] to [3]
Total Disk 3
Move disk [1] from tower [1] to [3]
Move disk [2] from tower [1] to [2]
Move disk [1] from tower [3] to [2]
Move disk [3] from tower [1] to [3]
Move disk [1] from tower [2] to [1]
Move disk [2] from tower [2] to [3]
Move disk [1] from tower [1] to [3]
/*
Kotlin Program
Implement tower of hanoi using stack
*/
// Define stack node
class StackNode
{
var disk: Int;
var source: Int;
var auxiliary: Int;
var destination: Int;
var next: StackNode ? = null;
constructor(disk: Int, source: Int, destination: Int, auxiliary: Int)
{
this.disk = disk;
this.source = source;
this.destination = destination;
this.auxiliary = auxiliary;
}
// Display the movement of current disk
fun printResult(): Unit
{
print(" Move disk " + this.disk + " from tower [" + this.source + "] to [" + this.destination + "]\n");
}
}
// Define a custom stack
class MyStack
{
var top: StackNode ? ;
var size: Int;
constructor()
{
//Set node values
this.top = null;
this.size = 0;
}
// Add node at the top of stack
fun push(node: StackNode ? ): Unit
{
node?.next = this.top;
this.top = node;
this.size += 1;
}
fun isEmpty(): Boolean
{
if (this.size>0 && this.top != null)
{
return false;
}
else
{
return true;
}
}
// Remove top element of stack
fun pop(): Unit
{
if (this.size>0 && this.top != null)
{
var temp: StackNode? = this.top;
// Change top element of stack
this.top = temp?.next;
this.size -= 1;
}
}
// return top element of stack
fun peek(): StackNode ?
{
return this.top;
}
}
class TowerOfHanoi
{
var stack: MyStack;
constructor()
{
this.stack = MyStack();
}
// Iterative tower of hanoi implementation
fun towerOfHanoi(totalDisk: Int): Unit
{
if (totalDisk>0)
{
// Display total disk
print("\n Total Disk " + totalDisk + " \n");
var disk: Int = totalDisk;
// Set the poles tag
var source: Int = 1;
var auxiliary: Int = 2;
var destination: Int = 3;
var node: StackNode? ;
var temp: Int ;
while (disk>0 || this.stack.isEmpty() == false)
{
if (disk > 0)
{
// Reduce disk size
node = StackNode(disk, source, destination, auxiliary);
// Add stack node
this.stack.push(node);
// Change execution variables
temp = destination;
destination = auxiliary;
auxiliary = temp;
disk -= 1;
}
else
{
// Get top element of stack
node = this.stack.peek();
// Display movement of disk
node?.printResult();
if(node!=null)
{
// Get new execution info
source = node.auxiliary;
destination = node.destination;
disk = node.disk - 1;
auxiliary = node.source;
}
// Remove stack elemnt
this.stack.pop();
}
}
}
}
}
fun main(args: Array<String>): Unit
{
var process: TowerOfHanoi = TowerOfHanoi();
// Test case
process.towerOfHanoi(4);
process.towerOfHanoi(3);
}
Output
Total Disk 4
Move disk 1 from tower [1] to [2]
Move disk 2 from tower [1] to [3]
Move disk 1 from tower [2] to [3]
Move disk 3 from tower [1] to [2]
Move disk 1 from tower [3] to [1]
Move disk 2 from tower [3] to [2]
Move disk 1 from tower [1] to [2]
Move disk 4 from tower [1] to [3]
Move disk 1 from tower [2] to [3]
Move disk 2 from tower [2] to [1]
Move disk 1 from tower [3] to [1]
Move disk 3 from tower [2] to [3]
Move disk 1 from tower [1] to [2]
Move disk 2 from tower [1] to [3]
Move disk 1 from tower [2] to [3]
Total Disk 3
Move disk 1 from tower [1] to [3]
Move disk 2 from tower [1] to [2]
Move disk 1 from tower [3] to [2]
Move disk 3 from tower [1] to [3]
Move disk 1 from tower [2] to [1]
Move disk 2 from tower [2] to [3]
Move disk 1 from tower [1] to [3]
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment