【剑指offer】面试题22：栈的压入、弹出序列

题目：

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

代码：（注意其中的while循环和其后的if语句，容易出错）

class Solution {
public:
    bool IsPopOrder(vector<int> pushV,vector<int> popV) {
        if(pushV.size()<=0 || popV.size()<=0)  return false;
        
        stack<int> stk;
        int index1=0;
        for(int i=0;i<popV.size();++i)
        {
            if(stk.size()==0 || stk.top()!=popV[i])
            {
                while(index1<pushV.size() && pushV[index1]!=popV[i])//这里不能index1++，否则循环里元素出错
                {//相等的时候不入栈
                    stk.push(pushV[index1]);
                    index1++;
                }
                if(index1<pushV.size() && pushV[index1]==popV[i])//相等的时候还需要移动index1下标
                    index1++;
                else             //没有这个else也是对的
                    break;
                
            }
            else if(stk.top()==popV[i])
            {
                stk.pop();
            }
        }
        return stk.empty();
    }
};