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

刚开始没弄清题意，简单来说，将某个序列压入栈，但是中间允许弹出。比如压入1234后，弹出4，再压入5.此时栈内是1235，则弹出序列为5321，而4之前弹出了，所以本次的弹出序列是45321。其次，条件是给了两个序列，第二个序列是用来判断的，而不是让你求出所有的可能性。
弄清题意后，就可以想到，得有一个辅助的数据结构来帮忙记录。由于已经使用了栈，所以首先考虑能否用辅助栈来解决。
思路1：使用辅助栈后。手上拿着两个序列，比较两个序列的首元素，1和4，不相等，则1压入辅助栈，比较2和首元素4，比较3和首元素4，不相等123都压入辅助栈，此时第一个序列拿到了4和第二个序列首元素4相等，所以不压入。遇到相等，则第二个序列索引后移一位，此时拿5，同时第一个序列索引也是要++的。此时两个序列的5又碰一起了，同理不压入。此时第一个序列遍历完毕，然后拿辅助栈的元素和第二个序列比，栈顶元素此时为3，第二个序列此时为3，相等，弹出3并且第二个序列索引++，同理2和1的过程同3，最后辅助栈弹空，则判断第二序列为true。只有辅助弹没弹空，就是false。

//自己的初级版
import java.util.Stack;
public class Solution {
    public boolean IsPopOrder(int [] pushA,int [] popA) {
      if(pushA == null || popA == null)
          return false;
      Stack<Integer> stack = new Stack<>();
      int index = 0;
      for(int i = 0; i < pushA.length; i++){//拿第一个序列的数去比较
          if(pushA[i] != popA[index]){//如果两个序列元素不相等，压入辅助栈
              stack.push(pushA[i]);
          }else //否则就说明相等，index++让第二序列的下一个数比较
             index++;      
          while(!stack.isEmpty() && stack.peek()==popA[index]){
        //只有栈不为空时，比较栈顶元素和第二序列的数，如果相等，栈弹出，索引++
          stack.pop();
          index++;
          }
      }   
      if(stack.isEmpty()){
          return true;
      }
      return false;      
    }
}

//精炼版
import java.util.Stack;
public class Solution {
    public boolean IsPopOrder(int [] pushA,int [] popA) {
      if(pushA == null || popA == null)
          return false;
      Stack<Integer> stack = new Stack<>();
      int index = 0;
      for(int i = 0; i < pushA.length; i++){
          stack.push(pushA[i]);
//第二个版本没有进行那么多判断的原因时，我不管你相不相等，先入栈再说
//相等的情况会在while中的比较时出现，此时再进行index++操作。
//比如4，在第二个版本（本例中）的4入了辅助栈，并且在while中的popA[index]仍旧是4
//而在上个版本中，4没有进入辅助栈，并且index在进入while判断前已经++，因此popA[index]是3
//这是因为5和4一样，都没有入辅助栈，所有index++执行两次，在while中已经指向了3
//第一个版本中不会弹4，5，第二个版本中会弹4，5，因为4，5在第二个版本中入栈了。
          while(!stack.isEmpty() && stack.peek()==popA[index]){
          stack.pop();
          index++;
          }
      } 
       return stack.isEmpty(); 
    }
}

思路2：使用队列或者数组存放。（其实牛客给出了头文件ArrayList，应该是一种暗示）
然后队列或者数组是逆序来放，毕竟思路一样，栈是先进后出，所以使用队列或者数组时，要从尾部取元素比较。

import java.util.ArrayList;

public class Solution {
    public boolean IsPopOrder(int [] pushA,int [] popA) {
        if(pushA.length==0||popA.length==0)
            return false;
        ArrayList<Integer> list  = new ArrayList<Integer>();
        int index = 0;
        for(int i = 0; i < pushA.length; i++){
            if(pushA[i] != popA[index])
                list.add(pushA[i]);
            else
                index++;
        }
        for(int i = list.size()-1; i >= 0; i--){
            if(list.get(i)!=popA[index])
                return false;
           index++;
        }
        return true;
    }
}