MHB Verifying Sequence of Push/Pop Ops in a Stack

[evinda]

Hello! (Smirk)

Consider that a sequence of 10 push and 10 pop operations is executed at an initially empty stack.
The ten push operations place the numbers $0,1, \dots, 9 $, in an ascending order, in the stack.
It is possible, that between the push operations we can have some pop operations. Each pop() operation prints the value, that is returns.

Which of the following sequence of numbers cannot be printed? For the sequences, that are valid, present the sequence push() and pop() that has to be done, and for the others justify why they cannot be printed.

• $2 5 6 7 4 8 9 3 1 0$
• $4 6 8 7 5 3 2 9 0 1$

That's what I have tried:

• We push in the stack $0$, $1$, $2$, we pop $2$, we push $3$, $4$, $5$, we pop $5$, we push $6$, we pop $6$, we push $7$, we pop $7$, we pop $4$, we push $8$, we pop $8$, we push $9$, we pop $9$, we pop $1$, we pop $0$.
  
  So, the sequence $2 5 6 7 4 8 9 3 1 0$ can be printed.
  $$$$
• We push in the stack $0$, $1$, $2$, $3$, $4$, we pop $4$, we push $5$, $6$, we pop $6$, we push $7$, $8$, we pop $8$, we pop $7$, $5$, $3$, $2$, we push $9$, we pop $9$, but, then, we cannot pop $0$, because of the fact that $1$ was put after $0$ and the method that we use to push/pop elements is LIFO.
  
  So, the second sequence is not valid.

Am I right? (Thinking)

 

[Opalg]

Hello! (Smirk)

Consider that a sequence of 10 push and 10 pop operations is executed at an initially empty stack.
The ten push operations place the numbers $0,1, \dots, 9 $, in an ascending order, in the stack.
It is possible, that between the push operations we can have some pop operations. Each pop() operation prints the value, that is returns.

Which of the following sequence of numbers cannot be printed? For the sequences, that are valid, present the sequence push() and pop() that has to be done, and for the others justify why they cannot be printed.

• $2 5 6 7 4 8 9 3 1 0$
• $4 6 8 7 5 3 2 9 0 1$

That's what I have tried:

• We push in the stack $0$, $1$, $2$, we pop $2$, we push $3$, $4$, $5$, we pop $5$, we push $6$, we pop $6$, we push $7$, we pop $7$, we pop $4$, we push $8$, we pop $8$, we push $9$, we pop $9$, we pop $1$, we pop $0$.
  
  So, the sequence $2 5 6 7 4 8 9 3 1 0$ can be printed.
  $$$$
• We push in the stack $0$, $1$, $2$, $3$, $4$, we pop $4$, we push $5$, $6$, we pop $6$, we push $7$, $8$, we pop $8$, we pop $7$, $5$, $3$, $2$, we push $9$, we pop $9$, but, then, we cannot pop $0$, because of the fact that $1$ was put after $0$ and the method that we use to push/pop elements is LIFO.
  
  So, the second sequence is not valid.

Am I right? (Thinking)

Sounds good to me, except that in explaining the first sequence you omitted to say "pop 3" after "pop 9".

 

[evinda]

Sounds good to me, except that in explaining the first sequence you omitted to say "pop 3" after "pop 9".

Oh yes, I am sorry... (Blush) Thanks a lot! (Smile)