《剑指offer第二版》面试题31：栈的压入、弹出序列（java

题目描述

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

解题思路:

1. 定义一个辅助栈S，假设栈的压入顺序为A,弹出序列为B
2. 将A的第一个数字压入辅助栈S中。
3. 比较S栈顶元素和B的当前数字是否一样：
   1. 如果不一样，则将A中的数字压入占中。
   2. 如果一样，则S弹出栈顶元素，继续比较S栈顶元素和B的下一个数字。

代码

boolean isStackOutSquence(int[] stackSeq, int[] outSeq){
    if (stackSeq == null || outSeq == null) {
        return false;
    }
    if (stackSeq.length != outSeq.length) {
        return false;
    }

    if (stackSeq.length == 0) {
        return true;
    }

    Stack<Integer> stack = new Stack<>();

    int stackSeqIndex = 0;
    int outSeqIndex = 0;
    while (stackSeqIndex == 0 || !stack.isEmpty()) {
        if (stackSeqIndex != 0 && stack.peek() == outSeq[outSeqIndex]) {
            // stack 栈顶元素和B中的当前值一样，则弹出栈顶元素
            stack.pop();
            outSeqIndex++;
        } else {
            // stack 栈顶元素和B中的当前值不一样，则继续压入A中的数字
            if (stackSeqIndex >= stackSeq.length) {
                break;
            }
            stack.push(stackSeq[stackSeqIndex]);
            stackSeqIndex++;

        }
        if (outSeqIndex >= outSeq.length) {
            break;
        }
    }
    return stack.isEmpty();
}