# Hanoi Tower with Stack

Solve the Hanoi Tower problem without recursion

## Solution

1) 假设有1个盘子

2) 假设有2个盘子

• 将盘子1从left移动到middle
• 将盘子2从left移动到right
• 将盘子1从middle移动到right

## Complexity

1) 1个盘子的时候需要21 – 1步

2) 根据1)，我们知道移动n-1 个盘子需要`2^(n - 1) - 1`步。而移动n个盘子需要做：把n-1个盘子移动到middle，然后把第n个盘子移动到left“。即`2 * (2^(n - 1) - 1) + 1 = 2^n – 1`

3) 由数学归纳法可知，对于任意n，完成Hanoi Tower需要2n – 1步。

## Code

``````enum Tower { Zero, Left, Mid, Right };

class HanoiObj {
public Tower src, tmp, dest;
public int num, index;
public HanoiObj(Tower s, Tower t, Tower d, int n) : src(s), tmp(t), dest(d), num(n) {
if (n == 1) {
index = 1;
}
}
public HanoiObj(Tower s, Tower d, int i) : src(s), dest(d), index(i) {
num = 1; tmp = Zero;
}
}

void move(Tower src, Tower dest, int index) {
System.out.println("Move Disk #" + index + " from Tower " + src + " to Tower " + dest);
}

void TOH(int N) {
Stack<HanoiObj> Hstack;
Tower s, t, d;
int n;
Hstack.push(new HanoiObj(Left, Mid, Right, N));
while (!Hstack.empty()) {
HanoiObj tmpObj = Hstack.top();
Hstack.pop();
s = tmpObj.src;
t = tmpObj.tmp;
d = tmpObj.dest;
n = tmpObj.num;
if (n < 1) {
continue;
}
if (n == 1) {
move(s, d, tmpObj.index);
} else {
// because Stack is LIFO, the push sequence is symmetric to the way we expect it to pop
Hstack.push(new HanoiObj(t, s, d, n - 1));
Hstack.push(new HanoiObj(s, d, n)); // basically, equivalent to calling move function
Hstack.push(new HanoiObj(s, d, t, n - 1));
}
}
}
``````