Intermixed sequence of Push and pop operations why is this sequence not possible

Question

I'm studying for a final and I can't figure this question out:

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

The answer is C but im not sure how to come to that conclusion

Solution 1

Ok, So the program always pushes 0-9 in that order, so looking at each line, we work out which order the pushes and pops happen

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

The next pop MUST be 7, because it was pushed before 8, it cannot be 1.

Solution 2

This is not difficult to solve. You just start writing the sequence until you find the first popped number; then cross it out and continue. Now we can see why the third sequence cannot occur:

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

Solution 3

For any decreasing sub-sequence in the output sequence, you can not have [a1, ..., an] such that, there exist k, where ak > a1 and ak < an and ak has not come before in the output and ak is not part of the sub-sequence [a1, ..., an].

Here [8, 1] is one such sub-sequence, where 7 has not come before and still not part of the sub-sequence.