mescolati sequenza di operazioni push e pop perché è questa sequenza non possilbe

Question

Ciao a tutti Sto studiando per una finale e non posso capire questa domanda fuori:

Supponiamo che un client esegue una sequenza mescolati dello stack spinta e operazioni pop. Le operazioni push spingono gli interi da 0 a 9 in ordine allo stack; le operazioni pop stampano il valore di ritorno. Quale delle seguenti sequenze non potrebbe verificarsi?

(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) Tutte queste sequenze sono possibili

La risposta è C ma im non sicuro come venire a tale conclusione

Answer 1

Ok, quindi il programma spinge sempre 0-9 in questo ordine, in modo da guardare ogni riga, lavoriamo quale ordinare le spinte e pop accadono

**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 ?    

la prossima pOP deve essere 7, perché è stato spinto prima 8, non può essere 1.

Answer 2

si hanno 8 stampato prima di 1 quindi quando 1 è stato inserito i numeri fino a 8 sono già stati premuti. Ma se questo è il caso, 2 è stato anche spinto e quindi dovrebbe essere spuntato prima 1.

MODIFICA: essere più prolisso - se si ha un valore x e quindi un valore y nella sequenza e si ha x > y e x è prima di y nella sequenza, nessun valore nell'intervallo [y, x] può essere soddisfatto nella sequenza dopo y.

Answer 3

Questo non è difficile da risolvere. Hai appena iniziato a scrivere la sequenza fino a trovare il primo numero spuntato; poi attraversalo e continua. Ora possiamo capire perché la terza sequenza non può avvenire:

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

Per qualsiasi discendente sotto-sequenza in sequenza in uscita, non si può avere [a1, ..., an] tale che, esistono k , dove ak > a1 e ak < an e ak non si trovano prima nell'output e ak non fa parte della sequenza secondaria [a1, ..., an].

Qui [8, 1] è una di queste sottocategorie, in cui 7 non è venuto prima e non fa ancora parte della sotto-sequenza.