汉诺塔问题（进阶）--- 用栈来模拟整个过程（非递归）

进阶版汉诺塔问题有一下两个原则：
<1> 小压大
<2> 相邻不可逆

由此，可得两个结论：
<1> 游戏的第一个动作一定是L->M,这是显而易见得。
<2>在走出最小步数过程中的任何时刻，4个动作只有一个是不违反上述两个原则的

综上所述，只要没走一步都根据这两个原则来考察，然后按顺序走下来即可。

附上代码

package pers.mao.stackAndQueue.demo_06;

import java.util.Stack;

/**
 * @author Mao Qingbo
 * @date 2020-10-23
 * 用栈来模拟整个过程
 */
public class TowersOfHanoi2 {
    /**
     * 5个动作：1）没动作 2）L->M 3)M->L 4)M->R 5)R->M
     */
    public enum Action{
        No,LToM,MToL,MToR,RToM
    }

    /**
     *
     * @param num 塔的层数
     * @param left 左塔
     * @param mid 中塔
     * @param right 右塔
     * @return 返回步数
     */
    public int hanoiProblem2(int num,String left,String mid,String right){
        Stack<Integer> lS = new Stack<Integer>();
        Stack<Integer> mS = new Stack<Integer>();
        Stack<Integer> rS = new Stack<Integer>();
        lS.push(Integer.MAX_VALUE);
        mS.push(Integer.MAX_VALUE);
        rS.push(Integer.MAX_VALUE);
        for(int i = num; i > 0; i--){
            lS.push(i);
        }
        Action[]  record ={Action.No};
        int step = 0;
        while(rS.size()!=num+1){
            step += fStackTotStack(record,Action.MToL,Action.LToM,lS,mS,left,mid);
            step += fStackTotStack(record,Action.LToM,Action.MToL,mS,lS,mid,left);
            step += fStackTotStack(record,Action.RToM,Action.MToR,mS,rS,mid,right);
            step += fStackTotStack(record,Action.MToR,Action.RToM,rS,mS,right,mid);
        }
        return step;
    }

    /**
     *
     * @param record 记录动作
     * @param preAct 前一个动作
     * @param nowAct 当前动作
     * @param fStack 出发栈
     * @param tStack 目标栈
     * @param from 出发塔
     * @param to 目标塔
     * @return 返回步数
     */
    public int fStackTotStack(Action[] record, Action preAct, Action nowAct,Stack<Integer> fStack, Stack<Integer> tStack, String from, String to) {
        if(record[0] != preAct && fStack.peek() < tStack.peek()){
            tStack.push(fStack.pop());
            System.out.println("Move "+tStack.peek()+" from "+from+" to "+to);
            record[0] = nowAct;
            return 1;
        }
        return 0;
    }
}