栈的压入、弹出序列

题目：

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）

牛客网

解法思路

模仿入栈和出栈操作。如果序列相匹配，则模拟操作后栈为空。

1. 使用两个指针p1和p2分别指向下一个入栈的数据和下一个出栈的数据。
2. p1指向的数据入栈，p1后移
3. 比较当前栈顶数据与p2所指的数据是否相同。如果相同，弹出栈顶数据，p2后移。循环执行比较，当栈顶数据与p2所指数据不同时，跳到步骤2。
4. 当所有数据都入栈并执行出栈操作后，判断栈是否为空，如果此时栈为空，则入栈序列与出栈序列相匹配。否则不匹配。

class Solution {
public:
    bool IsPopOrder(vector<int> pushV,vector<int> popV) {
        int pushIndex = 0;
        int popIndex = 0;
        vector<int> v;
        while (pushIndex < pushV.size()) {
            v.push_back(pushV[pushIndex]);
            pushIndex++;
            while (!v.empty() && v[v.size()-1] == popV[popIndex]) {
                v.pop_back();
                popIndex++;
            }
        }
        return v.empty();
    }
};