【LeetCode】---剑指Offer 31.栈的弹出压入序列

一、题目描述：

二、算法原理：

核心思想：
入栈的栈顶元素跟出栈序列进行匹配，入一个匹配一个。注意：结束的标志就是入栈序列走完了。

三、代码实现：

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

        //pushV：入栈序列  popV: 出栈序列
        
        // 1.定义2个移动下标来遍历2个序列 
        int pushi=0,popi=0;
        // 2.创建一个栈来实现匹配
        stack<int> st;

        //(1)整个程序结束的标志：入栈序列走完了！
        while(pushi<pushV.size())
        {
            //(2)先入栈
            st.push(pushV[pushi++]);
            //(3)判断匹配：
            // ①成功：因为可能有持续输出所以用while循环：
            while(!st.empty()&&st.top()==popV[popi])
            {
                popi++;
                st.pop();
            }
            // ②匹配失败：回到(2)继续

        }
        //！！！最终的判定结果：如果入栈序列 进入(st)走完了 并且 为空，必然两者匹配！！！
        // 否则不匹配！
        return st.empty();
    }
};