牛客网 —— 栈的压入、弹出序列 c++《解题分析和完整解题步骤》

首先，我们先看一下题目的要求：

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

现在我们先分析一下：
第一步：我们首先明白栈的特点是：后进先出，我们应该怎么样做才好？
第二： 我们不能只拿push和pop对比，如果push走完了，pop还没有走完，那系统会判断错误，但是这部一定是错误啊；所以我将先画一幅图，我们来了解一下，

主要的意思是：我们拿入栈的值，与出栈的值作比较，如果，栈里面的值，与出栈的值不一样，那么继续往栈里面入职，然后继续比较，比如，图中的到4的时候，我们看到和出栈的值一样，那么我们继续拿栈里面的3与出栈里面的比较，一样，就出栈，直到栈里面为空，但是入栈不为空，那么继续向里面继续入栈，在比较，直到入栈结束，且栈里面与出栈的值相等，那么就表明符合我们的要求。

下面我们就看一下代码;

class Solution {
public:
    bool IsPopOrder(vector<int> pushV,vector<int> popV) {
        stack<int> st;
        size_t pushIndex = 0 , popIndex = 0;
        while(pushIndex < pushV.size())
        {
            st.push(pushV[pushIndex++]);
            while(!st.empty() &&                       //判断栈里面不为空，
                 st.top() == popV[popIndex])     //且栈的值与出栈的的值相等
            {
                    st.pop();     //那么就由栈里面pop出来；
                    popIndex++;   //栈里面的向前走一个，继续判断；
            }
        }
        return st.empty();     //返回为空，则说明栈和出栈相等，符合要求，结束；
    }
};