Geek asks and answers

Mixed sequence of operations Push and Pop, why this sequence is impossible

I am preparing for the finale and cannot understand this question:

Suppose the client performs a mixed sequence of push and pop operations on the stack. Push operations push integers from 0 to 9 on the stack; Pop operations print a return value. Which of the following sequences cannot occur?

(a) 4 3 2 1 0 9 8 7 6 5
(b) 2 1 4 3 6 5 8 7 9 0
(s) 0 4 6 5 3 8 1 7 2 9
(d) 4 6 8 7 5 3 2 9 1 0
(d) All of these sequences are possible.

Answer C, but I'm not sure how to come to that conclusion

+6
source share
4 answers

, 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   ?

7, 8, 1.

+10

. , ; . , :

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
+4

[a1, ..., an] , k, ak > a1 ak < an ak ak [a1, ..., an].

[8, 1] - , 7 .

+1

8 1, , 1 , 8 . , 2 , 1.

EDIT: be more verbose - if you have an x ​​value and then a y value in the sequence and you have x> y and x before y in the sequence, no value in the interval [y, x] can execute in the sequence after y.

0
source

More articles:


All Articles