用栈来解决汉诺塔问题.md

#用栈来解决汉诺塔问题 ##题目： ###将经典的汉诺塔问题修改了一下规则，限制不能从最左侧直接移动到最右侧，也不能从最右侧直接移动到最左侧，而是必须经过中间。求当塔有N层时，打印最优移动过程和最优移动总步数。

        private Action action = Action.No;
    private enum Action {
        No, LtoM, MtoL, MtoR, RtoM
    }

    public int move(int num) {
        int step = 0;

        Stack<Integer> leftStack = new Stack<>();
        Stack<Integer> midStack = new Stack<>();
        Stack<Integer> rightStack = new Stack<>();
        for (int i = num; i > 0; i--) {
            leftStack.push(i);
        }
        while (rightStack.size() < num) {
            step += fromStackTotoStack(Action.MtoL, Action.LtoM, leftStack, midStack, "left", "mid");
            step += fromStackTotoStack(Action.LtoM, Action.MtoL, midStack, leftStack, "mid", "left");
            step += fromStackTotoStack(Action.RtoM, Action.MtoR, midStack, rightStack, "mid", "right");
            step += fromStackTotoStack(Action.MtoR, Action.RtoM, rightStack, midStack, "right", "mid");
        }
        return step;
    }

    public int fromStackTotoStack(Action preNoAction, Action nowAction, Stack<Integer> fromStack,
                                  Stack<Integer> toStack, String from, String to) {
        if (action != preNoAction && !fromStack.isEmpty()) {
            if (toStack.isEmpty() || fromStack.peek() < toStack.peek()) {
                toStack.push(fromStack.pop());
                action = nowAction;
                System.out.println("Move " + toStack.peek() + " from " + from + " to " + to);
                return 1;
            }
        }
        return 0;
    }