剑指offer30 栈的压入、弹出序列

思路：

• 题目要我们判断两个序列是否符合入栈出栈的次序，我们就可以用一个栈来模拟。对于入栈序列，只要栈为空，序列肯定要依次入栈。那什么时候出来呢？自然是遇到一个元素等于当前的出栈序列的元素，那我们就放弃入栈，让它先出来。

//入栈：栈为空或者栈顶不等于出栈数组
while(j < n && (s.isEmpty() || s.peek() != popA[i])){
    s.push(pushA[j]);
    j++;
}

• 如果能按照这个次序将两个序列都访问完，那说明是可以匹配入栈出栈次序的。

具体做法

• step 1：准备一个辅助栈，两个下标分别访问两个序列。
• step 2：辅助栈为空或者栈顶不等于出栈数组当前元素，就持续将入栈数组加入栈中。
• step 3：栈顶等于出栈数组当前元素就出栈。
• step 4：当入栈数组访问完，出栈数组无法依次弹出，就是不匹配的，否则两个序列都访问完就是匹配的。

代码

import java.util.*;

public class Solution {
    public boolean IsPopOrder(int [] pushA,int [] popA) {
        Stack<Integer> stack=new Stack<>();
        int j=0;
        int n=pushA.length;
      	//遍历出栈元素
        for(int i=0;i<n;i++){
          //只要 值不等于出栈元素就入栈 
          //遍历入栈
            while(j<n&&(stack.isEmpty()||stack.peek()!=popA[i])){
                stack.push(pushA[j]);
                j++;
            }
          //栈顶等于出栈元素就出栈
            if(stack.peek()==popA[i]){
                stack.pop();
            }
          //不相等直接返回false
            else{
                return false;
            }
            
        }
        return true;
      
    }
}