题目
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列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;
}
}
