[oha055]

Having some trouble understanding this question (from the book Algorithms, 4th edition):

"Suppose that a client performs an intermixed sequence of (stack) push and pop operations. The push operations put the integers 0 through 9 in order onto the stack; the pop operations print out the return values. Which of the following sequence(s) could NOT occur?"

a. 4 3 2 1 0 9 8 7 6 5
b. 4 6 8 7 5 3 2 9 0 1
c. 2 5 6 7 4 8 9 3 1 0
[...]

I'd really appreciate if someone who understands the question would give an explanation

This post has been edited by oha055: 17 November 2012 - 08:36 AM

[g00se]

Quote

[...]

Are we to understand there are more than 3 sequences?

[macosxnerd101]

Remember that Stacks store elements in a last-in-first-out order. So if I push 0, then 1, then 2, the 2 would be the first element to be popped from the Stack. This line is a big hint, by the way:

Quote

The push operations put the integers 0 through 9 in order onto the stack

[oha055]

g00se, on 17 November 2012 - 04:52 PM, said:

Quote

[...]

Are we to understand there are more than 3 sequences?

Yes, there are about 6-7 scenarios

[oha055]

macosxnerd101, on 17 November 2012 - 04:55 PM, said:

Remember that Stacks store elements in a last-in-first-out order. So if I push 0, then 1, then 2, the 2 would be the first element to be popped from the Stack. This line is a big hint, by the way:

Quote

The push operations put the integers 0 through 9 in order onto the stack

Yes, but doesn't this imply that the stack looks like this: (last)0 1 2 3 4 5 6 7 8 9(first)? then the only solution for a pop sequence would be pop 0, pop 1, etc.

This post has been edited by oha055: 17 November 2012 - 12:28 PM

[macosxnerd101]

If they push in order, then 9 would be the first element popped.