secuencia de entremezclado de las operaciones de inserción y extracción por qué es esta secuencia no possilbe

Question

Hola a todos Estoy estudiando para un final y yo puedo entender esta pregunta fuera:

Supongamos que un cliente realiza una secuencia de entremezclado de empuje pila y operaciones pop. Las operaciones de inserción empujan los enteros 0 a 9 en orden a la pila; las operaciones pop imprimen el valor de retorno. ¿Cuál de las siguientes secuencias no podría ocurrir?

(a) 4 3 2 1 0 9 8 7 6 5
(b) 2 1 4 3 6 5 8 7 9 0
(c) 0 4 6 5 3 8 1 7 2 9
(d) 4 6 8 7 5 3 2 9 1 0
(e) Todas estas secuencias son posibles

La respuesta es C pero im no seguro de cómo llegar a esa conclusión

Answer 1

Ok, así que el programa siempre empuja 0-9 en ese orden, por lo que mirar a cada línea, se trabaja a cabo qué orden los empujones y los estallidos ocurren

**The first line.** - Stack is 
Pushes 0, 1, 2, 3, 4 - [0, 1, 2, 3, 4] 
Pops 4, 3, 2, 1, 0 - [] 
Pushes 5, 6, 7, 8, 9 - [5, 6, 7, 8, 9] 
Pops 9, 8, 7, 6, 5 - [] 

**Second line** - Stack is 
Pushes 0, 1, 2 - [0, 1, 2] 
Pops 2, 1  - [0] 
Pushes 3, 4  - [0, 3, 4] 
Pops 4, 3  - [0] 
Pushes 5, 6  - [0, 5, 6] 
Pops 6, 5  - [0] 
Pushes 7, 8  - [0, 7, 8] 
Pops 8, 7  - [0] 
Pushes 9   - [0, 9] 
Pops 9, 0  - [] 

**Third line** - Stack is 
Pushes 0   - [0] 
Pops 0   - [] 
Pushes 1, 2, 3, 4 - [1, 2, 3, 4] 
Pops 4,   - [1, 2, 3] 
Pushes 5, 6  - [1, 2, 3, 5, 6] 
Pops 6, 5, 3  - [1, 2] 
Pushes 7, 8  - [1, 2, 7, 8] 
Pops 8   - [1, 2, 7] 
Pops ?    

el siguiente pop DEBE ser 7, porque fue empujado antes de 8, no puede ser 1.

Answer 2

Usted tienen 8 impreso antes de 1 así que cuando 1 apareció, los números hasta 8 ya han sido empujados. Pero si ese es el caso, 2 también ha sido empujado y debería aparecer antes de 1.

EDITAR: para ser más detallado - si tiene un valor x y luego un valor y en la secuencia y tiene x > yy x es antes de y en la secuencia, no se puede encontrar ningún valor en el intervalo [y, x] en la secuencia después de y.

Answer 3

Esto no es difícil de resolver. Simplemente comienza a escribir la secuencia hasta que encuentre el primer número reventado; luego tacharlo y continuar. Ahora podemos ver por qué la tercera secuencia no puede ocurrir:

0 // Pop 0 
- 
1 2 3 4 // Pop 4 
1 2 3 
1 2 3 5 6 // Pop 6 
1 2 3 5 // Pop 5 
1 2 3 // Pop 3 
1 2 
1 2 7 8 // Pop 8 
1 2 7 // And here it fails; you cannot possibly pop a 1 from the stack 

Answer 4

Para cualquier sub-secuencia decreciente en la secuencia de salida, no se puede tener [a1, ..., an] tal que, existen k , donde ak > a1 y ak < an y ak no han aparecido antes en la salida y ak no es parte de la subsecuencia [a1, ..., an].

Aquí [8, 1] es una de esas subsecuencias, donde 7 no ha llegado antes y todavía no forma parte de la subsecuencia.