Perché utilizzare due stack per fare una coda?

Question

Vedo il vantaggio dell'utilizzo di due stack se si utilizza un'implementazione dell'array dato che gli stack vengono implementati più facilmente utilizzando gli array rispetto alle code. Ma se si usano elenchi concatenati, qual è il vantaggio? L'azione di far scoppiare lo stack sulla coda aumenta l'overhead per entrambe le implementazioni di elenchi collegati e array.

Answer 1

E 'un modo comune per implementare una coda in linguaggi di programmazione funzionale con puramente funzionale (immutabile, ma la condivisione di struttura) liste (ad esempio Clojure, Haskell, Erlang ...):

• usare un paio di liste per rappresentare una coda in cui elementi sono in ordine FIFO nella prima lista e in ordine LIFO nel secondo elenco
• Enqueue alla coda anteponendo al secondo elenco
• dequeue dalla coda prendendo il primo elemento del primo lista
• se il primo lista è vuota: invertire la seconda lista e sostituire la prima lista con esso, e sostituire il secondo elenco con un elenco vuoto

(tutte le operazioni restituiscono il nuovo oggetto coda in aggiunta ad eventuali valori restituiti)

Il punto è che l'aggiunta (rimozione) di un elemento a (da) il fronte di una lista puramente funzionale è O (1) e l'operazione inversa che è O (n) è ammortizzata su tutti i dequeues, quindi è vicino a O (1), fornendo così un'implementazione della coda ~ O (1) con strutture dati immutabili.

Answer 2

È una buona esperienza di apprendimento, ma non pratica.

Answer 3

È possibile effettuare una coda immutabile utilizzando due pile immutabili.

Ma, se si desidera solo una coda mutabile, l'uso di due stack è un ottimo modo per renderlo più lento e complicato rispetto all'utilizzo di un elenco collegato.

Answer 4

Questo approccio può essere utilizzato per creare una coda lock-free utilizzando due stack atomici a elenco singolo collegati, come fornito da Win32: Interlocked Singly Linked Lists. L'algoritmo potrebbe essere come descritto in liwp's answer, sebbene il passo di reimballaggio (punto 4) possa essere ottimizzato un po '.

Strutture e algoritmi di dati privi di blocchi è una zona di programmazione molto interessante (per alcuni di noi), ma devono essere utilizzati con molta attenzione. In una situazione generale, gli algoritmi basati su lock sono più efficienti.