Biegral Blog

题目描述

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

思路分析

首先考虑这个问题肯定是需要一个辅助栈，方便后边讲思路，我们将压入序列称为pushV，弹出序列称为popV，按照pushV将数据压入栈，压入一个数据就比较栈顶数据是否是popV中的第一个数，如果是，就将该栈顶数据pop掉，然后继续压入，并进行比较。
为了进行比较，我们需要一个辅助的vector来存放从栈内pop掉的数据，最后将这个vector和popV进行比较，如果顺序相同，说明popV是该栈的一个弹出序列，否则就不是。

下面画图分析下思路：（以上边的例子说明）
pushV：1、2、3、4、5
popV：4、5、3、2、1

现在以popV的序列为4、3、5、1、2分析：

综上分析过程：说明当栈不为空且栈顶数据和当前popV序列中的数据不相等时循环结束。

代码实现：

https://github.com/lybb/Offer/blob/master/offer_22.cpp

bool IsPopOrder(vector<int> pushV,vector<int> popV)
{
    if (pushV.empty() || popV.empty())
        return false;

    stack<int> s;
    vector<int> compV;  //将s的出栈顺序保存在该vetcor中，最后和popV比较
    vector<int>::iterator it1 = pushV.begin();
    vector<int>::iterator it2 = popV.begin();
    while (it1 != pushV.end())
    {
        s.push(*it1);
        it1++;
        while(!s.empty() && s.top()==*it2)
        {
            compV.push_back(s.top());
            s.pop();
            it2++;
        }
    }
    if (!s.empty() && s.top()!=*it2)//如果栈s内有数据，但栈顶数据不是当前it2的数据，说明不是出栈顺序
        return false;

    it2 = popV.begin();
    vector<int>::iterator it = compV.begin();
    while (it2!=popV.end() && it!=compV.end())  //比较comp和popV，如果有任意一个不同则表明popV不是出栈顺序
    {
        if (*it2 != *it)
            return false;
        it2++;
        it++;
    }
    return true;
}