c++ - 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不是子序列的一部分。akak[a1, ..., an]

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

Answer 4

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

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