算法-31.栈的压入、弹出序列

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

思路：定义一个辅助栈，依次将压入序列中的元素加入到辅助栈中，每加入一个，则判断该元素是否需要立刻出栈；如果最终辅助栈中的元素为null，说明弹出序列是该压栈序列的弹出序列

// 定义一个辅助栈
        Stack<Integer> stack = new Stack<>();
        int n = pushed.length;
        int index = 0;
        for (int i=0;i<n;i++) {
            // 先往辅助栈中添加元素
            stack.push(pushed[i]);
            // 然后循环判断，当前弹出序列中的第一个元素是不是满足条件
            // 比如：往辅助栈中添加了压入序列的第一个元素，然后循环判断辅助栈的第一个元素是否与弹出序列的第一个元素一致
            // 如果一致，则直接弹出，说明该元素是在压入栈中之后就被弹出了
            // 如果不一致，则继续往辅助序列中加入压入序列中的第二个元素
            // 然后判断此时栈顶元素与弹出序列的第一个是否一致
            // 其实就是每次都使用辅助栈的栈顶元素与当前弹出序列的位置上的元素做比较
            // 如果满足则弹出
            while (!stack.isEmpty() && (stack.peek() == popped[index])) {
                stack.pop();
                index++;
            }
        }
        // 如果此时辅助栈为null，说明弹出序列是满足条件的
        return stack.isEmpty();