//https://www.nowcoder.com/practice/d77d11405cc7470d82554cb392585106?tpId=13&&tqId=11174&rp=1&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking
//JZ31 栈的压入、弹出序列
class Solution {
public:
    bool IsPopOrder(vector<int> pushV,vector<int> popV) {
        stack<int> st; //用来入pushV的栈
        size_t popi = 0; //弹出顺序vector的下标
        for (auto e : pushV) { //遍历pushV
            st.push(e); //入栈
            
            //每次入栈后,栈顶和弹出顺序比较,如果能匹配就进入while
            //不能匹配说明这个数据可能还没入栈,继续入栈
            while (!st.empty() && st.top()==popV[popi]) { 
                ++popi; //匹配成功,下标后移一位
                st.pop(); //匹配成功把st栈顶元素出栈
            }
        }
        //当pushV已经遍历完,但是st中还有数据,说明弹出顺序popV非法
        
        return st.empty(); //如果最后都能匹配上那么st即为空返回1,否则返回0
    }
};