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

import java.util.*;

public class Solution {
    public boolean IsPopOrder(int [] pushA,int [] popA) {
        Deque<Integer> s1 = new ArrayDeque<>();
        // 往 s1 入栈，中间可能存在部分先出栈，再继续入栈的情况
        int j = 0;
        for(int x : pushA){
            s1.push(x);
            // 1. 中途开始出栈;
            // 2. 最后，将pushA压完后，还会进while里尝试能不能将 s1 继续出栈
            while(!s1.isEmpty() && s1.peek().equals(popA[j])) {
                s1.poll();
                j++;
            }
        }
        // 执行到这里有两种情况：
        // 1. s1 已经在上面的while里变成空栈了;
        // 2. 输入的出入栈序列不匹配，s1 还没清空就退出while了
        return s1.isEmpty();
    }
}