-
Notifications
You must be signed in to change notification settings - Fork 0
/
Q1.cpp
94 lines (83 loc) · 1.83 KB
/
Q1.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include<iostream>
using namespace std;
struct node{
int data;
node* next;
node(int data){
this ->data = data;
this ->next = NULL;
}
};
class Stack{
private:
node* top;
public:
Stack(){
top = NULL;
}
//push method
void push(int d){
node *newnode = new node(d);
newnode->next = top;
top = newnode;
}
// pop method
int pop(){
if(isempty()){
cout<<"stack underflow "<<endl;
return -1;
}
int popval = top->data;
node* temp = top;
top = top->next;
delete temp;
return popval;
}
bool isempty(){
return top == NULL;
}
node* getTop() const {
return top;
}
};
void printStack(Stack& s, const string& label) {
cout << label << ": ";
for (node* i = s.getTop(); i != nullptr; i = i->next)
cout << i->data << " ";
cout << endl;
}
void towerofhanoi(int d, Stack &s,Stack &des,Stack &a){
if(d==1){
des.push(s.pop());
printStack(s, "Source");
printStack(a, "Auxiliary");
printStack(des, "Destination");
cout << endl;
}
else{
towerofhanoi(d-1,s,a,des);
des.push(s.pop());
printStack(s, "Source");
printStack(a, "Auxiliary");
printStack(des, "Destination");
cout << endl;
towerofhanoi(d-1,a,des,s);
}
}
int main()
{
Stack source,destination,auxilary;
int n;
cout<<"enter number of disks"<<endl;
cin>>n;
for (int i = n; i>0; i--) {
source.push(i);
}
cout << "Initial configuration:" << endl;
printStack(source, "Source");
printStack(auxilary, "Auxiliary");
printStack(destination, "Destination");
cout << endl;
towerofhanoi(n,source,destination,auxilary);
return 0;
}