【剑指offer】栈的压入和弹出序列

class Solution {
public:
    bool IsPopOrder(vector<int> pushV,vector<int> popV) {
        //两种写法模拟整个过程
        //1.直接利用栈模拟
        stack<int> s;
        //从pop序列分析
        for(int i = 0, j = 0; i < popV.size(); i++){
            //对每一个弹出的元素，都把它之前的元素入栈的过程模拟一遍
            while(s.empty() || s.top() != popV[i]){
                //当栈里为空或者栈顶不是弹出的那个元素的时候 模拟压栈
                s.push(pushV[j++]);
                if(j > pushV.size())
                    return false;//入栈的地址非法判断
            }
            //当while循环结束，此时栈顶的元素和弹出序列的元素相同，模拟弹出
            s.pop();
        }
        //当弹出序列遍历完了之后,此时模拟的过程也应该结束，栈里不能有多余的元素
        return s.empty()? true : false;

        /*2.利用vector数组模拟栈
        vector<int> stack;
        //从push序列分析
        for(int i = 0, j = 0; i < pushV.size(); i++){
            //模拟按入栈顺序开始入栈，和弹出顺序作比较
            stack.push_back(pushV[i]);
            //入栈每一个元素之后，判断此时的出栈序列元素是否和它一致，一致则弹出，否则继续模拟入栈
            while(j < popV.size() && popV[j] == stack.back()){
                //入栈的过程中和弹出序列相同时开始模拟按照弹出序列弹出
                stack.pop_back();
                j++;
            }
        }
            //当入栈元素全部入栈结束之后，必须也都弹出了，数组中不能存有元素
            return stack.empty();
                    */
    }
};