之前参加过华北计算机研究所和优酷土豆的笔试，都考到出栈顺序，之前数据结构学的不到位，遇到这类题时，还着实把我愣了一会，现在总结下，省得以后再遇到这类问题，也希望能给遇到同样问题的兄弟们一个参考。
废话不多说，直接上个例题。
一个栈的入栈序列是a,b,c,d,e则栈的不可能的输出序列是：（）
A edcbd B decba C dceab D abcde
栈之根本——后进先出（Last In First Out , LIFO）初次接触到这个问题的人，或许会认为入栈abcde，所以出栈只能是edcba所以BCD都不对。
其实是这个问题描述有歧义，应该是分段入栈的顺序，也就是说，可能先入栈a，取出a，入栈b，取出b……，所以D也是可能的。
知道这个意思了以后，就要明确这个问题的矛盾根本所在：第一次出栈d，说明什么？说明a，b，c一定早已入栈（入栈顺序决定的）。那么在出栈d以后，a，b，c的出栈顺序一定是c，b，a，而不用理会中间穿插着出栈了d后面的字符（因为可以再入栈，再出栈嘛）。所以立即选中C，不用犹豫，理由简单：d出栈了，abc一定已经入栈，那么abc只能以cba的顺序出栈，C不符合，OK！
举一个更加直观的例子：
如栈顺序是：1 2 3 4 ，如何正确理解出栈？
（1）入栈顺序是1 2 3 4，就是指这四个数依次入栈：
数据4入栈之前，1 2 3肯定已经入栈了；
数据3入栈之前，1 2肯定已经入栈了，而4还没入栈；
数据2入栈之前，1肯定已经入栈了，而2 3 4还没入栈；
数据1最先入栈，2 3 4还没入栈。
（2）既然入栈顺序是1 2 3 4，3 4入栈的时候，1 2 肯定已经入栈了，怎么会在后面再入栈。
（3）先拿4 3 1 2这个出栈序列来说，4最先出来，说明此时1 2 3（底到顶顺序）还都在栈中；接下来只有3能出栈，3出来后，栈中为1 2（底到顶顺序）；再接下来只有2能出栈，所以如果出栈序列前两个是4 3的话，后两个只能是2 1。
再看个正确的出栈序列：2 4 3 1；2最先出来，说明它出来时，3 4还没入栈，而1已入栈且还在栈中；接着是4出来，说明此时3也在栈中（3要比4先入栈），此时栈中有1 3（底到顶顺序）；然后只能3出栈，最后是1出栈。
总之，挨个看出栈序列的数据，根据入栈顺序，分析它出来时，栈中应该还有谁，而有谁还没入栈，然后分析此时可不可能是它出栈。
下面针对具体问题，编程来进行分析。
输入一个压栈序列，判断第二个序列是否为其出栈序列。 例如：入栈序列：1 2 3 4 5 6，出栈序列，4,3,5,2,6,1
算法思想，1：根据出栈序列，入栈，直到其栈顶等于出栈元素，栈s：4,3,2,1
2：栈顶与出栈序列相同出栈，否则break
根据入栈序列入栈：（左为栈顶）
栈：1 2 3 4 1 2 3 1 2 5 1 2 1 6 1 |空
出栈元素： 4 3 5 2 6 1 ， 4 3 5 2 6 1 ，4 35 2 6 1，4 3 5 2 6 1 ，4 3 5 26 1 ，4 3 5 2 61 ，完
|
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
|
#include <iostream>
#include <stack>
using
namespace
std;
bool
IsStackPopOrder(
int
*pushorder,
int
*poporder,
int
len)
{
bool
isorder =
false
;
if
(pushorder!=NULL && poporder != NULL && len > 0)
{
stack<
int
> s;
int
*pnextpush = pushorder;
int
*pnextpop = poporder;
while
((pnextpop - poporder) < len)
{
while
(s.empty()||s.top()!=*pnextpop)
{
if
((pnextpush - pushorder)==len)
break
;
s.push(*pnextpush);
pnextpush++;
}
if
(s.top() == *pnextpop)
{
s.pop();
pnextpop++;
}
else
break
;
}
if
((pnextpop - poporder)==len && s.empty())
isorder =
true
;
}
return
isorder;
}
void
main()
{
int
array1[7] = {1,2,3,4,5,6,7};
int
array2[7] = {4,3,5,6,7,1,2};
if
(IsStackPopOrder(array1,array2,7))
cout<<
"是"
<<endl;
else
cout<<
"否"
<<endl;
system
(
"pause"
);
}
|
