题目：输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出序列。假设压入栈的所有数字均不相等。例如序列1、2、3、4、5是某栈的压栈序列，序列4、5、3、2、1是该压栈序列对应的一个弹出序列，但4、3、5、1、2就不可能是该压栈序列的弹出序列。
解题思路：找到判断一个序列是不是栈的弹出序列的规律：如果下一个弹出的数字刚好是栈顶数字，直接弹出。如果下一个弹出的数字不在栈顶，把压栈序列中还没有入栈的数字压入辅助栈，知道把下一个需要弹出的数字压入栈顶为止。如果所有的数字都压入了仍然没有找到下一个弹出的数字，那么该序列不可能是一个弹出序列。
C#实现方式：
|
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
|
public
static
bool
IsPopOrder(
int
[] pPush,
int
[] pPop,
int
nLength)
{
bool
bPossible =
false
;
if
(pPush !=
null
&& pPop !=
null
&& nLength > 0)
{
int
pNextPush = 0;
int
pNextPop = 0;
Stack<
int
> stackData =
new
Stack<
int
>();
while
(pNextPop < nLength){
while
(stackData.Count == 0 || stackData.Peek() != pPop[pNextPop])
{
if
(pNextPush == nLength)
break
;
stackData.Push(pPush[pNextPush]);
pNextPush++;
}
if
(stackData.Peek() != pPop[pNextPop])
break
;
stackData.Pop();
pNextPop++;
}
if
(stackData.Count == 0 && pNextPop == nLength)
bPossible =
true
;
}
return
bPossible;
}
|
Java实现方式：
|
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
|
public
static
boolean
IsPopOrder(
int
[] pPush,
int
[] pPop,
int
nLength)
{
boolean
bPossible =
false
;
if
(pPush !=
null
&& pPop !=
null
&& nLength >
0
)
{
int
pNextPush =
0
;
int
pNextPop =
0
;
Stack<Integer> stackData =
new
Stack<Integer>();
while
(pNextPop < nLength){
while
(stackData.size() ==
0
|| stackData.peek() != pPop[pNextPop])
{
if
(pNextPush == nLength)
break
;
stackData.push(pPush[pNextPush]);
pNextPush++;
}
if
(stackData.peek() != pPop[pNextPop])
break
;
stackData.pop();
pNextPop++;
}
if
(stackData.size() ==
0
&& pNextPop == nLength)
bPossible =
true
;
}
return
bPossible;
}
|
Python实现方式：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
class
StackMy(
object
):
@
staticmethod
def
isPopOrder(lst_push, lst_pop, length):
bPossible
=
False
if
lst_push !
=
None
and
lst_pop !
=
None
and
length:
pNextPush
=
0
stack_data
=
[]
for
pop_item
in
lst_pop:
while
len
(stack_data)
=
=
0
or
stack_data[
-
1
] !
=
pop_item:
if
pNextPush
=
=
length:
break
stack_data.append(lst_push[pNextPush])
pNextPush
+
=
1
if
stack_data[
-
1
] !
=
pop_item:
break
stack_data
=
stack_data[:
-
1
]
if
len
(stack_data)
=
=
0
:
bPossible
=
True
return
bPossible
|
本文转自 许大树 51CTO博客，原文链接：http://blog.51cto.com/abelxu/1974486，如需转载请自行联系原作者
