栈的序列问题

• 问题描述：输入两个序列，第一个序列，表示栈的压入顺序，判断第二个序列是否可能为该栈的弹出顺序。
• 假设:压入栈中的所有数字均不相等

关键：利用辅助栈

• 思路：让压入序列的元素按顺序进栈，进栈过程中，如果栈顶元素和弹出序列的头元素相等，则弹出栈顶元素。最后，通过判断栈是否为空，空，返回true，否则false。

  public boolean IsPopOrder(int[] pushA, int[] popA) {
  
        if (pushA == null || popA == null || popA.length != popA.length) {
            return false;
        }
        Stack<Integer> stack = new Stack<>(); // 建立一个辅助栈
        int j = 0; // 记录popA出栈序列的当前位置
        for (int i = 0; i < pushA.length; i++) { // 按进站顺序将pushA全部压入栈中，中途可能有出栈的
            stack.push(pushA[i]);
            if (stack.peek() == popA[j]) { // 如果栈顶元素==序列popA当前位置元素
                stack.pop(); // 弹出
                j++;
            }
        }
  
        // 此时，栈可能为空，也可能不为空，为空，则返回true;
        // 不空，则进一步判断（不为空时，一定是按顺序进栈，按顺序出栈的情况）,如：进栈1,2,3；出栈3,2,1
        while (!stack.isEmpty()) {
            if (stack.peek() == popA[j]) {
                stack.pop();
                j++;
            } else break;// 存在不相等，则为false，则阶break
        }
  
        // 最后判断栈是否为空
        if (stack.isEmpty()) {
            return true;
        }else {
            return false;
        }
    }