一个栈的输入序列为1 2 3 4 5，则下列序列中不可能是栈

[单选题]

一个栈的输入序列为1 2 3 4 5，则下列序列中不可能是栈的输出序列的是

```
1 5 4 3 2
```
```
2 3 1 4 5
```
```
2 3 4 1 5
```
```
5 4 1 3 2
```

查看正确选项

J_kiwi

对于出栈这类题目，为了尽快选出答案，我们可以先看第一个出栈的元素是后进栈的选项，这些选项的特点是在在第一个进栈元素之前进栈的元素必须是逆序的。

发表于 2015-12-03 08:06:34 回复(0)

渊虹

A:PUSH POP PUSH PUSH PUSH PUSH POP POP POP POP

B:PUSH PUSH POP POSH POP POP PUSH POP PUSH POP

C:PUSH PUSH POP PUSH POP PUSH POP POP PUSH POP

D:5最先出栈说明入栈顺序是12345，出栈只能是54321.

发表于 2015-09-16 16:41:33 回复(0)

cpppppp

先给出结论：

对于任意栈：1, 2, 3, 4,..., n-1, n，

经过任意顺序的进栈和出栈，也就是栈混洗，

都不能出现（...,c,...,a,....,b,....）的顺序，其中(a < b < c) ，...代表夹在中间的其他元素。

也就是不能出现（...大...小...中...）的顺序。

证明过程如下：

当输出存在顺序 c a b 时，

因为a < b < c，所以当c出栈的时候，一定有a，b已c在之前压入栈中，且没有出栈，存在栈中。

又因为 a < b，所以一定是a先进栈，b后进栈。那么b先出栈，a后出栈。

所以不可能出现 c a b 的顺序。

补充：

可能出现：

...小...中...大...

...小...大...中...

...中...小...大...

...中...大...小...

...大...中...小...

不可能出现：

...大...小...中...

上面只证明了不可能出现的情况，可能出现的情况证明过程略。

发表于 2019-01-16 16:57:32 回复(0)

__sgf__

这种顺序进栈，中途可出栈，求出栈序列的题目是有规律的，假设元素进栈顺序为从小到大进栈，得到的每个可能的出栈序列须满足：对于其中任一个元素k，要么，其后边的出栈元素都大于k；要么，其后边的出栈元素中小于k的那些元素按递减顺序排列。题目给的元素少可以测试选项，但元素多的话还是要掌握规律。

发表于 2022-01-08 17:49:17 回复(1)

FLYFREELY

选项A：1入，1出，2入，3入，4入，5入，5出，4出，3出，2出；出栈序列为1，5，4，3，2。
选项B：1入，2入，2出，3人，3出，1出，4入，4出，5入，5出；出栈序列为2，3，1，4，5。
选项C：1入，2入，2出，3入，3出，4入，4出，1出，5入，5出；出栈序列为2，3，4，1，5。
选项D：1入，2入，3入，4入，5入，5出，4出；此时栈内还剩3，2，1，一定是3先出，出栈序列不可能是1，3，2。

所以正确答案为D。

其实这题可以先看最后入栈的选项5，其出栈顺序必为逆序，D选择很快就选出来了。

发表于 2022-07-28 08:43:20 回复(0)