栈的压入、弹出序列

题目：

​ 输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如，序列 {1, 2, 3, 4, 5} 是某栈的压栈序列，序列 {4, 5, 3, 2, 1} 是该压栈序列对应的一个弹出序列，但 {4, 3, 5, 1, 2} 就不可能是该压栈序列的弹出序列。

分析：

​ 压栈序列为 {1, 2, 3, 4, 5} ，弹出序列为 {4, 5, 3, 2, 1} 对应的压栈的出栈过程

​ 一个压栈序列为 {1, 2, 3, 4, 5}的栈 没有一个弹出序列为 {4, 3, 5, 1, 2}

通过分析以上序列，可以得出：

• 如果下一个弹出的数字刚好是栈顶数字，那么直接弹出。
• 如果下一个弹出的数字不在栈顶，我们把压栈序列中还没有入栈的数字压入辅助栈，直到把下一个需要弹出的数字压入栈顶为止。
• 如果所有的数字都压入栈了仍然没有找到下一个弹出的数字，那么该序列不可能是一个弹出序列。

代码：

public class StackPushPopOrder {

    /**
     * 是否为弹出序列
     *
     * @param pushOrder 压栈序列
     * @param popOrder  出栈序列
     * @param length    栈的长度
     * @return boolean
     */
    public static boolean isPopOrder(int[] pushOrder, int[] popOrder, int length) {

        boolean possible = false;

        if (null != pushOrder && null != popOrder && length > 0) {

            int pushNext = 0; //下一个要push元素的index
            int popNext = 0; //下一个要pop元素的index
            int push = 0; //pushOrder首个元素的index
            int pop = 0; //popOrder首个元素的index

            Stack<Integer> dataStack = new Stack<>();
            // 循环结束条件，所有元素都已pop
            while (popNext - pop < length) {
                // 辅助栈栈顶元素不是弹出序列中要弹出元素
                // 向辅助栈中压入元素
                while (dataStack.size() == 0 || dataStack.peek() != popOrder[popNext]) {
                    // 如果所有数字都已压入辅助栈，退出循环
                    if (pushNext - push == length) {
                        break;
                    }
                    // 向辅助栈中压入压栈序列元素
                    dataStack.push(pushOrder[pushNext]);
                    pushNext++;
                }

                // 没有匹配到对应元素
                if (dataStack.peek() != popOrder[popNext]) {
                    break;
                }

                dataStack.pop();
                popNext++;
            }

            if (dataStack.size() == 0 && popNext - pop == length) {
                possible = true;
            }
        }

        return possible;
    }
}

测试：

@Test
public void test() {

    int[] pushOrder = {1, 2, 3, 4, 5};
    int[] popOrder = {4, 5, 3, 2, 1};
    int length = 5;
    boolean isPopOrder = StackPushPopOrder.isPopOrder(pushOrder, popOrder, length);
    System.out.println(isPopOrder);
}