思路:
- 题目要我们判断两个序列是否符合入栈出栈的次序,我们就可以用一个栈来模拟。对于入栈序列,只要栈为空,序列肯定要依次入栈。那什么时候出来呢?自然是遇到一个元素等于当前的出栈序列的元素,那我们就放弃入栈,让它先出来。
//入栈:栈为空或者栈顶不等于出栈数组
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;
}
}