例题-栈的压入，弹出序列

题目描述

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等

原理

根据栈的压入顺序判断栈的弹出顺序，其中核心的一点是抓住弹出时是从栈顶元素开始的，换句话说弹出序列中的每一个值都是某个状态下栈中的栈顶元素。

那么我们就使用一个栈来模拟压入弹出的操作，在这个过程中来反推弹出序列的正确性

具体的做法是：

我们按照压入顺序逐个将元素压入栈中，而每压入一个元素之后，都要判断当前栈顶元素是否与当前出栈序列 的第一个元素相同，如果相同，则执行出栈操作，并且将往后移一位；如果不相同，就继续压入之后的元素。我们不断重复以上操作直到所有元素都压入栈后，再判断是否所有元素都顺序出栈了，如果都顺利出栈了，说明弹出序列是有效的，否则无效。

代码实现

class Stack 
{
public:
    bool IsPopOrder(vector<int> pushV, vector<int> popV)
    {
        stack<int>sta;
        int i = 0;
        int j = 0;
        while (i < pushV.size()) 
        {
            if (pushV[i] != popV[j]) 
            {
                sta.push(pushV[i]);
                ++i;
            }
            else 
            {
                ++i;
                ++j;
                while (!sta.empty() && sta.top() == popV[j]) 
                {
                    sta.pop();
                    j++;
                }
            }
        }
        return sta.empty();
    }
};

输入为

[1,2,3,4,5],[4,5,3,2,1]

输出为

true