Stack utilizzando una coda

Question

Stavo sfogliando alcune domande di intervista e mi sono imbattuto in questo. Mi ha fatto strappare i capelli.

Qualcuno sa come implementare uno stack utilizzando la coda ?.

Answer 1

push: inserire l'elemento nel retro della coda.

pop: rimuovere un elemento dalla parte anteriore, inserirlo immediatamente nella parte posteriore, ripetere N-1 volte, dove N è la dimensione della coda, quindi rimuovere l'ultimo elemento e restituirlo.

Answer 2

Versione A:

push:

Enqueue in QUEUE1

pop:

mentre la dimensione del QUEUE1 è più grande di 1, tubo rimosse dalla coda elementi da QUEUE1 in coda2 dequeue e ritorno l'ultimo elemento di queue1, quindi cambia i nomi di queue1 e queue2

Versione B:

push:

Enqueue in coda2 enqueue tutte le voci di QUEUE1 in coda2, quindi passare i nomi di QUEUE1 e coda2

pop:

deqeue da QUEUE1

Answer 3

concetto di utilizzare una coda per implementare lo stack richiede O (2n) o (macchina indipendente) O (n) complessità dello spazio. Ma quando si lavora per una matrice di grandi dimensioni, il doppio della dimensione potrebbe non essere disponibile, anche la complessità temporale è O (n^2) o precisamente O (n * (n + 1)/2) nel caso si provi a usare solo una coda.