c – 推送和弹出操作的混合序列为什么这个序列不可能

发布时间：2020-12-16 07:52:32 所属栏目：百科来源：网络整理

导读：大家好,我正在学习决赛,我不能解决这个问题： Suppose that a client performs an intermixed sequence of stack push and pop operations. The push operations push the integers 0 through 9 in order on to the stack; the pop operations print out the

大家好,我正在学习决赛,我不能解决这个问题：

Suppose that a client performs an intermixed sequence of stack push and pop operations. The push operations push the integers 0 through 9 in order on to the stack; the pop operations print out the return value. Which of the following sequences could not occur?

(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) All of these sequences are possible

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

解决方法

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

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

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

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

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

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!