描述

示例

思路

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

具体做法

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

代码

class Solution {
public:
bool IsPopOrder(vector<int> pushV,vector<int> popV) {
    int n = pushV.size();
    //辅助栈
    stack<int> s;
    //遍历入栈的下标
    int j = 0;
    //遍历出栈的数组
    for(int i = 0; i < n; i++){
        //入栈：栈为空或者栈顶不等于出栈数组
        while(j < n && (s.empty() || s.top() != popV[i])){
            s.push(pushV[j]);
            j++;
        }
        //栈顶等于出栈数组
        if(s.top() == popV[i])
            s.pop();
        //不匹配序列
        else
            return false;
    }
    return true;
}
};