[剑指offer][Java]栈的压入弹出序列

题目

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

程序核心思想

• 我的方法：没有用到stack，仅用数组实现。
  创建一个boolean数组，用来记录这个数是否已经被弹出（索引和push数组一致）。
  压入一个数，如果它跟弹出数组不一致，可以有两种做法：一，往左边（曾经压入栈的数）找，找到第一个在Boolean数组中记录为false的数（没有弹出的数），如果跟弹出数组不一致，那么再压入一个数；如果跟弹出数组一致，那么比较下一个在boolean数组中记录为false的数跟弹出数组的下一个数是否一致，重复以上动作。
  之前写了代码，但后来发现逻辑有问题，虽然测试用例都通过了，这个方法实现起来比起参考别人的方法要麻烦不少，所以就没有再尝试实现我自己的想法，可能以后有时间会再实现一下，现在想赶紧多刷几个题。
• 参考别人的方法：使用stack
  创建一个栈，压入一个元素，如果栈顶元素跟弹出数组一致，就把元素弹出，直到栈顶元素跟数组不一致，那时再压入一个元素，重复以上动作。直到弹出数组的数全部弹出，返回true；否则返回false。

Tips

• 注意length和length-1，这些边界问题
• 判断栈顶元素是否相等的时候，首先要先保证栈非空（空栈还谈什么栈顶不栈顶的...）

while(!stack.empty() && stack.peek() == popA[j] && j < popA.length)

代码

import java.util.ArrayList;
import java.util.Stack;

public class Solution {
    public boolean IsPopOrder(int [] pushA,int [] popA) {
        if(pushA.length != popA.length)    return false;
        if(pushA.length == 0)    return true;
        
        Stack<Integer> stack = new Stack<Integer>();
        
        int j = 0;
        for(int i = 0; i < pushA.length; i++){
            stack.push(pushA[i]);
            while(!stack.empty() && stack.peek() == popA[j] && j < popA.length){
                stack.pop();
                j++;
            }
            if(j == popA.length){
                return true;
            }
        }
        return false;
    }
}