JZ31 栈的压入、弹出序列

题目来源：栈的压入、弹出序列_牛客题霸_牛客网

题目：如下

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

答案：如下

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pushV int整型vector 
     * @param popV int整型vector 
     * @return bool布尔型
     */
    bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {
        // write code here
        stack<int> st;
        int pushi=0,popi=0;
        while(pushi<pushV.size())
        {
            st.push(pushV[pushi]);
            ++pushi;

            while(!st.empty()&&st.top()==popV[popi])
            {
                st.pop();
                ++popi;
            }
        }

        return st.empty();
    }
};

解析：如下

（1）建立栈和变量

题目是判断第二个序列是否可能为该栈的弹出顺序，那么这里我们可以建立一个栈来模拟栈的压入和弹出

由于pushV和popV是vector可以用operator[]来进行访问，那么我们可以创建变量pushi和popi用于访问pushV和popV

stack<int> st;
int pushi=0,popi=0;

（2）模拟

假设pushV中有5个数据，那么当pushi=4的时候已经访问完pushV中的数据，那么我们就可以以此为while循环判断条件，即pushi<pushV.size()

将pushV中的数据逐个压入st栈中，由于出栈的顺序未定，判断是否符合popV序列，那么可能入完第一个判断不符合，再入第二个判断符合，，当st不为空时，并且当st的栈顶数据等于popV的数据时就把st的栈顶数据pop掉，有可能弹出完，下一个数据仍可能在弹出数据中，这时我们继续进行判断

如图所示

while(pushi<pushV.size())
{
        st.push(pushV[pushi]);
        ++pushi;

        while(!st.empty()&&st.top()==popV[popi])
        {
            st.pop();
            ++popi;
        }
}

（3）判断

当数据都弹出后，st为空，说明pushV中的数据对应有符合popV中的出栈顺序，反之则没有

return st.empty();

到这里我们讲解完毕

如果对您有帮助的话点一个免费的赞和收藏叭！

由于作者水平不足，如有任何错误，请读者在评论区交流！