31-栈的压入弹出序列

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

第一种 判断弹出序列能否全部遍历

假如可以遍历完弹出序列，说明弹出序列是有效的。

public boolean validateStackSequences(int[] pushed, int[] popped) {
        if (pushed == null || popped == null ) {
            return false;
        }
        if(pushed.length == 0 && popped.length == 0){
            return true;
        }

        Stack<Integer> stack = new Stack<>();
        int i = 0, j = 0;
        stack.push(pushed[i++]);
        while (i < pushed.length && j < popped.length) {
            if (stack.isEmpty()) {
                stack.push(pushed[i++]);
                continue;
            }
            if (stack.peek().equals(popped[j])) {
                j++;
                stack.pop();
            }else{
                stack.push(pushed[i++]);
            }
        }
				//假如没有遍历完，那么继续比较
        while (j < popped.length) {
            if(stack.peek().equals(popped[j])){
                j++;
                stack.pop();
            }else{
                break;
            }
        }
        return j == popped.length;
    }

这种方法比较复杂，虽然能ac，但并不优雅。

第二种 判断模拟栈是否为空

本题中数字无重复，可以用模拟栈模拟出栈的情况。

基本思路就是读取进栈序列，直接进栈，然后比较栈顶元素和当前的出栈序列元素，假如相等，就一直往外弹；假如不等就继续进栈。最后栈为空表示序列有效。

 public boolean validateStackSequences2(int[] pushed, int[] popped) {
        if (pushed == null || popped == null ) {
            return false;
        }
        if(pushed.length == 0 && popped.length == 0){
            return true;
        }
        Stack<Integer> stack = new Stack<>();
        int j = 0;
        for (int data : pushed) {
            stack.push(data);
            while (!stack.isEmpty() && stack.peek().equals(popped[j])) {
                stack.pop();
                j++;
            }
        }
        return stack.isEmpty();

    }