栈的压入、弹出序列

同样是栈相关的一道题，来自《剑指Offer》

栈的压入、弹出序列

https://www.acwing.com/problem/content/description/40/

题目如下：
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。

假设压入栈的所有数字均不相等。

例如序列 1,2,3,4,5 是某栈的压入顺序，序列 4,5,3,2,1 是该压栈序列对应的一个弹出序列，但 4,3,5,1,2 就不可能是该压栈序列的弹出序列。

注意：若两个序列长度不等则视为并不是一个栈的压入、弹出序列。若两个序列都为空，则视为是一个栈的压入、弹出序列。

样例
输入：[1,2,3,4,5]
[4,5,3,2,1]

输出：true

思路：

想了一会似乎没有什么很奇特的算法，遂直接开栈模拟，模拟的规则也很简单，先用两个指针指向两个序列的开头，每次入栈一个元素，如果加入的元素跟指向出栈序列的指针当前所指的元素相同，就开始出栈，直到栈顶元素和指向出栈序列的指针指向的元素不同或者栈空为止。
由于每次只入栈一个元素，而出栈是可以出多个的，因此加入压栈序列的所有元素之后，我们只需要看一下指向出栈序列的指针是否已经遍历了整个出栈序列，如果已经遍历了出栈序列，那么就是合法的出栈序列。

AC 代码

class Solution {
public:
    bool isPopOrder(vector<int> pushV,vector<int> popV) {
        if(pushV.empty()) return popV.empty();
        if(pushV.size() != popV.size()) return false;
        stack<int> stk;
        int i = 0,j = 0;
        while(i<pushV.size()){
                int tt = pushV[i];
                stk.push(tt);
                i++;
            while(j<popV.size() && stk.size() &&stk.top() == popV[j]){
                stk.pop();
                j++;
            }
        }
        return j == popV.size();
    }
};

栈的压入、弹出序列

原文：https://www.cnblogs.com/Softwarer1412/p/14719438.html