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

//参考了剑指offer原书的教学。
//这题的思路是构建一个辅助栈来模拟。围绕popV序列进行。popV序列中的那个数字，如果辅助栈栈顶就有，那就把辅助栈栈顶pop掉。如果没有，则去pushV序列中按照入栈顺序不断入栈（从上次截止的地方开始，在代码中体现为Pushindex不是每次循环都变为0的），直到找到popV想要出栈的数字为止。如果找到最后都没找到，说明这个数字要么不存在于PushV序列中，要么早就已经入栈了，被压在栈顶底下，出不来。
//通过这种模拟的方式即可判断。
#include <stack>
class Solution {
public:
    bool IsPopOrder(vector<int> pushV,vector<int> popV) {
        if(pushV.size()==0)
            return true;
        int Popindex=0;
        int Pushindex=0;
        bool foundInPushV=false;
        for(;Popindex<popV.size();Popindex++)
        {
            foundInPushV=false;
            if(!s.empty() && popV.at(Popindex)==s.top())//如果在辅助栈的栈顶，则弹出
            {
                s.pop();
            }else {//如果不在，就从pushV里入栈前面的数字，直到它进入到辅助栈中。如果pushV空了都没找到，判为false。
                while (Pushindex<pushV.size()) {
                    if(popV.at(Popindex)!=pushV.at(Pushindex))
                    {
                        s.push(pushV.at(Pushindex));
                        Pushindex++;
                    }else {
                        foundInPushV=true;//说明找到了。
                        Pushindex++;//进辅助栈然后再弹出辅助栈的步骤就免了
                        break;
                    }
                }
                if(foundInPushV==false)return false;
            }
        }
        return true;
    }
private:
    stack<int>s;//辅助栈
};