栈的压入、弹出序列

题目描述

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

//方法一
class Solution {
public:
    bool IsPopOrder(vector<int> pushV, vector<int> popV) {
        //遍历压入队列
        for (int i = 0; i < pushV.size();)
        {
            cout << "pushv=" << pushV[i] << "    ,pupv=" << popV[0] << endl;
            /*
            如果压入队列中的值等于弹出队列中第一个值，压入和弹出队列同时删除该值
            */
            if (pushV[i] == popV[0]) {
                pushV.erase(pushV.begin() + i);
                popV.erase(popV.begin());
                /*
                如果当前元素没在队列的第一个位置，弹出队列中上一个值与弹出队列第一个值比较
                */
                if (i > 0) {
                    i--;
                    continue;
                }
            }
            /*
            如果压入队列中当前值与弹出队列第一个值不相等，
            则使用压入队列中下一个值与弹出队列中第一个值进行比较
            */
            i++;
        }
        //如果遍历结束压入队列，队列中还存在数据，说明弹出序列不可能是压入序列
        if (pushV.size()>0) {
            return false;
        }
        else
        {
            return true;
        }
    }
};

//方法二
class Solution {
public:
    bool IsPopOrder(vector<int> pushV, vector<int> popV) {
        if (pushV.size() == 0) {
            return false;
        }
        vector<int>result;
        int j = 0;
        //遍历压入栈数据，放入辅助栈中
        for (int i = 0; i <pushV.size(); i++)
        {
            result.push_back(pushV[i]);
            /*如果辅助栈序列中某个值与出栈序列中首个值相同，
            删除辅助栈中当前数据，使用辅助栈中上一个数据与出栈序列中下一个数据比较。
            */
            while (j<popV.size()&&result.back()==popV[j])
            {
                result.pop_back();
                j++;
            }
        }
        //如果辅助栈序列数据为空，说明第二个序列为第一个序列的弹出顺序
        return result.empty();
    }
};