31-栈的压入、弹出序列

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

class Solution {
    public boolean validateStackSequences(int[] pushA, int[] popA) {
        Stack<Integer> a = new Stack<>();
        int index = 0;
        for (int i : pushA) {
            a.push(i);
            while (!a.empty() && (a.peek() == popA[index])) {
                a.pop();
                index++;
            }
        }
        return a.empty() && index == popA.length;
    }
}

直观点，还可以用双栈。切记 Integer 判断相等时要使用 equals(), 不能用 ==

class Solution {
    public boolean validateStackSequences(int[] pushA, int[] popA) {
        if (pushA.length != popA.length) return false;
        Stack<Integer> a = new Stack<>();
        Stack<Integer> b = new Stack<>();
        
        for (int i = popA.length - 1; i >= 0; i--) {
            b.push(popA[i]);
        }
        for (int i : pushA) {
            a.push(i);
            while (!a.empty() && (a.peek().equals(b.peek()))) {
                a.pop();
                b.pop();
            }
        }
        return a.empty() && b.empty();
    }
}