题解 | #栈的压入、弹出序列#

• 思路1
  对于出栈数组中的每个元素：考虑该元素出栈时，或者从栈顶弹出，或者在压入一些元素后，再从栈顶弹出。
  因此，遍历出栈数组中的每个元素，先判断栈顶是否是该元素，如果是，则弹出，遍历下一个出栈元素；如果不是，则将入栈数组压入栈中，直到遇见该元素，再遍历下一个（下一个元素的入栈元素应接着上次入栈结束的位置，因为压过的数不需要再压入了）。
  当所有入栈数组中元素都压完，仍然没有遇见该元素，说明出栈数组的顺序是错误的。
  [1,2,3,4,5],[4,3,5,1,2]
  当出栈元素遍历到1时，栈顶是2,1不会是栈顶弹出的结果，而入栈元素从5开始往后压入，也没有1，因此1是不会有机会在这个位置出栈的。

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

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

• 思路2
  以pushA数组为中心，模拟栈的压栈出栈。当没有遇见popA的当前第一个数时，则持续将pushA中数据压入栈中，遇见popA的当前第一个数时，则从栈中弹出数据。

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