进栈出栈顺序问题

描述

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

解析

对于每一个弹出的元素，在他之前的元素肯定在栈中，例如弹出序列4,5,3,2,2，这个序列4第一个弹出，那么1,2,3，4依次入栈，弹出4，然后5入栈，弹出5，最后弹出3,2,1，对于4,3,5,1,2这个序列，1,2,3,4入栈，4弹出，3弹出，然后5入栈，弹出5，此时栈中top位置的元素是2，不是1，因此此序列错误。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
bool IsPopOrder(vector<int> pushV,vector<int> popV) 
{
    int size = popV.size();
    if(size == 0)
        return false;
    stack<int> tmp;
    int a = 0, b = 0;
    while(b < size)
    {
    	if(!tmp.empty() && tmp.top() == popV[b])
        {
        	tmp.pop();
            ++b;
        }
        else if(a < size)
        {
        	tmp.push(pushV[a++]);
        }
        else
        {
        	return false;    
        }
    }
    return true;
}