Push和pop操作的混合序列为什么这个序列不可能

Question

我正在学习决赛，我无法解决这个问题：

假设客户端执行堆栈推送和弹出操作的混合序列。推送操作按顺序将整数0到9推送到堆栈;弹出操作打印出返回值。以下哪个序列不会发生？

（a）4 3 2 1 0 9 8 7 6 5 （b）2 1 4 3 6 5 8 7 9 0 （c）0 4 6 5 3 8 1 7 2 9 （d）4 6 8 7 5 3 2 9 1 0 （e）所有这些序列都是可能的

答案是C，但我不确定如何得出这个结论

Answer 1

好的，所以程序总是以这个顺序按0-9，所以看看每一行，我们找出推动和弹出的顺序

**The first line.**   - Stack is
Pushes 0, 1, 2, 3, 4  - [0, 1, 2, 3, 4]
Pops   4, 3, 2, 1, 0  - []
Pushes 5, 6, 7, 8, 9  - [5, 6, 7, 8, 9]
Pops   9, 8, 7, 6, 5  - []

**Second line**  - Stack is  
Pushes 0, 1, 2   - [0, 1, 2]  
Pops   2, 1      - [0]  
Pushes 3, 4      - [0, 3, 4]  
Pops   4, 3      - [0]  
Pushes 5, 6      - [0, 5, 6]  
Pops   6, 5      - [0]  
Pushes 7, 8      - [0, 7, 8]  
Pops   8, 7      - [0]  
Pushes 9         - [0, 9]  
Pops   9, 0      - []  

**Third line**    - Stack is   
Pushes 0          - [0]  
Pops   0          - []  
Pushes 1, 2, 3, 4 - [1, 2, 3, 4]  
Pops   4,         - [1, 2, 3]  
Pushes 5, 6       - [1, 2, 3, 5, 6]  
Pops   6, 5, 3    - [1, 2]  
Pushes 7, 8       - [1, 2, 7, 8]  
Pops   8          - [1, 2, 7]   
Pops   ?            

下一个pop必须是7，因为它在8之前被推，它不能是1。

Answer 2

这不难解决。您只需开始编写序列，直到找到第一个弹出的数字;然后将其交叉并继续。现在我们可以看到为什么不能发生第三个序列：

0 // Pop 0
-
1 2 3 4 // Pop 4
1 2 3
1 2 3 5 6 // Pop 6
1 2 3 5 // Pop 5
1 2 3 // Pop 3
1 2
1 2 7 8 // Pop 8
1 2 7 // And here it fails; you cannot possibly pop a 1 from the stack

Answer 3

对于输出序列中任何递减的子序列，你不能有[a1, ..., an]这样，存在k，其中ak > a1和ak < an和ak在输出中没有出现，而ak不是子序列[a1, ..., an]的一部分。

这里[8,1]是一个这样的子序列，其中7不在之前，并且仍然不是子序列的一部分。

Answer 4

您在1之前打印了8，所以当1弹出数字时，直到8已被推。但如果是这种情况，2也被推，所以它应该在1之前弹出。

编辑：更详细 - 如果你有一个值x，然后在序列中有一个值y，你有x> y，x在序列中的y之前，在[y，x]区间内没有值可以满足y之后的序列。