algs4 1.3.3 计算不可能产生的 出栈顺序 -- 用编码的方式 计算

FindGhost.java

package life.yanfeng.study.algorithm;

import edu.princeton.cs.algs4.StdOut;

import java.util.Arrays;

enum StackActionEnum {
    pop, push
}

class StackAction<Item> {
    StackActionEnum action;
    Item item;

    StackAction(Item item, StackActionEnum action) {
        this.item = item;
        this.action = action;
    }
}

// for 1.3.3
public class FindGhost {
    public static <Item> Queue<StackAction<Item>> ghost(Item[] pushItems, Item[] popItems) {
        // 也先按既定的 push 顺序, 放到 队列里.
        Queue<Item> pushQueue = new Queue<>();
        for (int i = 0; i < pushItems.length; i++) {
            pushQueue.enqueue(pushItems[i]);
        }

        // 先按 pop 顺序, 放到 队列里.
        Queue<Item> popQueue = new Queue<>();
        for (int i = 0; i < popItems.length; i++) {
            popQueue.enqueue(popItems[i]);
        }

        // 准备好要 入 的 栈.
        Stack<Item> stack = new Stack<>();

        // 准备记录 栈操作的 队列.
        Queue<StackAction<Item>> actionQueue = new Queue<>();

        for (; !popQueue.isEmpty(); ) {
            Item popItem = popQueue.dequeue();

            if (!stack.isEmpty() && stack.top().equals(popItem)) {
                actionQueue.enqueue(new StackAction(stack.top(), StackActionEnum.pop));
                stack.pop();
                continue;
            }

            for (; !pushQueue.isEmpty(); ) {
                Item pushItem = pushQueue.dequeue();
                if (pushItem.equals(popItem)) { // get it!
                    actionQueue.enqueue(new StackAction(pushItem, StackActionEnum.push));
                    actionQueue.enqueue(new StackAction(pushItem, StackActionEnum.pop));
                    break;
                } else {
                    actionQueue.enqueue(new StackAction(pushItem, StackActionEnum.push));
                    stack.push(pushItem);
                }
            }
        }

        if (popQueue.isEmpty() && pushQueue.isEmpty() && stack.isEmpty()) {
            return actionQueue;
        } else {
            return null;
        }
    }

    public static <Item> String showGhost(Queue<StackAction<Item>> ghost) {
        String result = "";
        int pushActionCounter = 0;

        for (; !ghost.isEmpty(); ) {
            StackAction<Item> actionItem = ghost.dequeue();
            String suffix = "";
            if (actionItem.action == StackActionEnum.push) {
                pushActionCounter += 1;
                suffix = "👇";
            } else {
                pushActionCounter -= 1;
                suffix = "👆";
            }

            String prefix = new String(new char[pushActionCounter]).replace("\0", "*");
            result += "\n" + prefix + actionItem.item.toString() + suffix;
        }

        return result;
    }

    public static void main(String[] args) {
        Integer[] pushItems = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
        Integer[][] allPopItems = {
                {4, 3, 2, 1, 0, 9, 8, 7, 6, 5},
                {4, 6, 8, 7, 5, 3, 2, 9, 0, 1},
                {2, 5, 6, 7, 4, 8, 9, 3, 1, 0},
                {4, 3, 2, 1, 0, 5, 6, 7, 8, 9},
                {1, 2, 3, 4, 5, 6, 9, 8, 7, 0},
                {0, 4, 6, 5, 3, 8, 1, 7, 2, 9},
                {1, 4, 7, 9, 8, 6, 5, 3, 0, 2},
                {2, 1, 4, 3, 6, 5, 8, 7, 9, 0}
        };

        for (int i = 0; i < allPopItems.length; i++) {
            Integer[] popItems = allPopItems[i];
            Queue<StackAction<Integer>> ghost = ghost(pushItems, popItems);
            if (null == ghost) {
                StdOut.println(Arrays.toString(popItems) + " 不符合预期");
            } else {
                StdOut.println(Arrays.toString(popItems) + "符合预期.对应的完整出入栈顺序是:\n" + showGhost(ghost));
            }
        }
    }
}

[4, 3, 2, 1, 0, 9, 8, 7, 6, 5]符合预期.对应的完整出入栈顺序是:

*0👇
**1👇
***2👇
****3👇
*****4👇
****4👆
***3👆
**2👆
*1👆
0👆
*5👇
**6👇
***7👇
****8👇
*****9👇
****9👆
***8👆
**7👆
*6👆
5👆
[4, 6, 8, 7, 5, 3, 2, 9, 0, 1] 不符合预期
[2, 5, 6, 7, 4, 8, 9, 3, 1, 0]符合预期.对应的完整出入栈顺序是:

*0👇
**1👇
***2👇
**2👆
***3👇
****4👇
*****5👇
****5👆
*****6👇
****6👆
*****7👇
****7👆
***4👆
****8👇
***8👆
****9👇
***9👆
**3👆
*1👆
0👆
[4, 3, 2, 1, 0, 5, 6, 7, 8, 9]符合预期.对应的完整出入栈顺序是:

*0👇
**1👇
***2👇
****3👇
*****4👇
****4👆
***3👆
**2👆
*1👆
0👆
*5👇
5👆
*6👇
6👆
*7👇
7👆
*8👇
8👆
*9👇
9👆
[1, 2, 3, 4, 5, 6, 9, 8, 7, 0]符合预期.对应的完整出入栈顺序是:

*0👇
**1👇
*1👆
**2👇
*2👆
**3👇
*3👆
**4👇
*4👆
**5👇
*5👆
**6👇
*6👆
**7👇
***8👇
****9👇
***9👆
**8👆
*7👆
0👆
[0, 4, 6, 5, 3, 8, 1, 7, 2, 9] 不符合预期
[1, 4, 7, 9, 8, 6, 5, 3, 0, 2] 不符合预期
[2, 1, 4, 3, 6, 5, 8, 7, 9, 0]符合预期.对应的完整出入栈顺序是:

*0👇
**1👇
***2👇
**2👆
*1👆
**3👇
***4👇
**4👆
*3👆
**5👇
***6👇
**6👆
*5👆
**7👇
***8👇
**8👆
*7👆
**9👇
*9👆
0👆

Process finished with exit code 0