/*汉诺塔非递归实现--利用栈

  * 1.创建一个栈，栈中每个元素包含的信息：盘子编号，3个塔座的变量

  * 2.先进栈，在利用循环判断是否栈空，

  * 3.非空情况下，出栈，检查是否只有一个盘子--直接移动，否则就模拟前面递归的情况--非1的情况

  * 4.直到栈空就结束循环，就完成全部的移动。

  * */

 class Stack11{

     Towers[] tt = new Towers[20];

     int top = -1;

     public boolean isEmpty(){

         return top == -1;

     }

     public void push(Towers t){

         tt[++top] = t;

     }

     public Towers pop(){

         return tt[top--];

     }

 }

 class Towers{

     int diskN;

     char from;

     char inter;

     char to;

     public Towers(int diskN, char from, char inter, char to) {

         this.diskN = diskN;

         this.from = from;

         this.inter = inter;

         this.to = to;

     }

 }

 public class HannoTower_Stack {

     public static void main(String[] args) {

         Towers t1 = new Towers(3,'A','B','C');

         doTowers(t1);

     }

     private static void doTowers(Towers t1) {

         Stack11 stack = new Stack11();

         stack.push(t1);

         while(!stack.isEmpty()){

             Towers temp = stack.pop();

             //处理是一个盘子的情况--所有打印语句都从这里打印

             if(temp.diskN == 1){

                 System.out.println("Top disk " + "from " + temp.from + " to " + temp.to);

             }

             //注意处理移动的顺序本来是A-C-B,A-B-C,B-A-C.所以进栈的顺序相反

             else{

                 stack.push(new Towers(temp.diskN-1,temp.inter,temp.from,temp.to));

                 stack.push(new Towers(1,temp.from,temp.inter,temp.to));

                 stack.push(new Towers(temp.diskN-1,temp.from,temp.to,temp.inter));

             }

         }

     }

 }