面试题22：栈的压入、弹出序列

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

分析

栈是一种“后进先出”(LIFO)的数据结构，所以元素的出进顺序都是有相对关系的。对应于题目中的例子，当入栈序列为1,2,3,4,5时，经过如下操作便可得到4,5,3,2,1的出栈序列：push(1),push(2),push(3),push(4),pop(4),push(5),pop(5),pop(3),pop(2),pop(1)。而对于4,3,5,1,2的出栈序列，尝试过程如下：push(1),push(2),push(3），push(4),pop(4),pop(3),push(5),pop(5)，此时栈顶元素应该为2，而当前出栈序列中对应的元素为1，所以不可能是该栈的一个出栈序列。

经过以上分析，总结思想如下：

设置两个指针pIn和pOut，分别指向入栈和出栈序列的第一个元素。若pIn!=pOut，则将pIn指向的元素入栈，pIn++，知道两个元素相等时，将pIn指向的元素入栈并出栈，pOut++，继续重复以上过程即可。

代码如下：

1.  `bool IsPopOrder(const vector& pPush,const vector& pPop)`
2.  `{`
3.  `    int i,j;`
4.  `    int length=pPush.size();`
5.  `    if(length==0)`
6.  `        return true;`
7.  `    stack s;`
8.  `    s.push(pPush[0]);`
9.  `    i=1,j=0;`
10.  `    while(i<=length && j<length)`
11.  `    {`
12.  `        if(s.top()!=pPop[j] && i==length)`
13.  `            return false;`
14.  `        if(s.top()!=pPop[j])`
15.  `        {`
16.  `            s.push(pPush[i++]);`
17.  `        }`
18.  `        else if(s.top()==pPop[j])`
19.  `        {`
20.  `            s.pop();`
21.  `            j++;`
22.  `        }`
23.  `    }`
24.  `    if(s.empty())`
25.  `    {`
26.  `        return true;`
27.  `    }`
28.  `    else`
29.  `    {`
30.  `        return false;`
31.  `    }`
32.  `}`

以上

如果你有任何想法或是可以改进的地方，欢迎和我交流！

完整代码及测试用例在github上：点我前往