CODEWITHSUNDEEP
javaalgorithmassemblydata-structuresstack
Jens B
Jens B

Reputation: 77

push and pop of integers to stack, what outcome is not possible

I am trying to take an online course of algorithms and i cant seem to get my head around how this works. (this is not homework, just a question from a free online course)

would anyone explain to me how the answers are found? the are given at the end of the exercise but i do not understand how it works. thanks in advance ! :)

Suppose that an intermixed sequence of (stack) push and pop operations are performed. The pushes push the integers 0 through 9 in order; the pops print out the return value. 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

(d) 4 3 2 1 0 5 6 7 8 9

(e) 1 2 3 4 5 6 9 8 7 0

(f) 0 4 6 5 3 8 1 7 2 9

(g) 1 4 7 9 8 6 5 3 0 2

(h) 2 1 4 3 6 5 8 7 9 0

Correct Answers: (b), (f), and (g).

Upvotes: 5

Views: 2415

Answers (1)

David Hoelzer
David Hoelzer

Reputation: 16351

IF the numbers are pushed in order, even with the pops occurring randomly, there are certain things that can never happen. Consider (b):

Push 0, 1, 2, 3, 4, pop 4, push 5, 6, pop 6, push 7, push 8, pop 8, pop 7, pop 5, pop 3, pop 2, push 9, pop 9.... You can't pop 0 because the one is in the way.

The same is true of the other incorrect answers.

Upvotes: 4

Related Questions