面试题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上:点我前往

[来自为知笔记(Wiz)](http://www.wiz.cn/i/96171253 "来自为知笔记(Wiz)")