javadata-structureslifo

sequences on a LIFO stack

I'm studying for a midterm and I need help with this question:

Suppose that an intermixed sequence of push and pop operations are performed on a LIFO stack. The pushes push the numbers 0 through 9 in order; the pops print out the return value. Which of the following output sequence(s) could occur? Select all that are possible.

1 2 5 4 3 6 0 9 8 7

6 5 4 3 2 1 0 7 8 9

4 6 8 7 5 3 2 9 0 1

0 1 5 6 4 3 7 9 2 8

0 2 4 1 6 7 5 9 8 3

I believe the answer is:

6 5 4 3 2 1 0 7 8 9

Am I correct? Thank you in advance!

Solution

  • First one is Possible and sequence is: 

    push(0);
push(1);
pop();
push(2);
pop();
push(3);
push(4);
push(5);
pop();
pop();
pop();
push(6);
pop();
pop();
push(7);
push(8);
push(9);
pop();
pop();
pop();

    Second one is also possible with sequence:

    push(0);
push(1);
push(2);
push(3);
push(4);
push(5);
push(6);
pop();
pop();
pop();
pop();
pop();
pop();
pop();
push(7);
pop();
push(8);
pop();
push(9);
pop();

    Third one is not possible because after printing 9 stack will contain 0 1 and pop() will give you 1 not 0.

    Also fourth is also not possible because after printing 9 stack will have 2 8 and you can not pop() 2 before 8.

    Fifth is also not possible because after printing 4 stack will contain 1 3 and 3 will be popped first.