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!
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.