Warum zwei Stapel verwenden, um eine Warteschlange zu erstellen?

Question

Ich kann den Vorteil der Verwendung von zwei Stapeln sehen, wenn eine Array-Implementierung verwendet wird, da Stacks einfacher mit Arrays als Warteschlangen implementiert werden. Aber wenn Linked-Listen verwendet werden, was ist der Vorteil? Das Aufrufen des Stapels in die Warteschlange erhöht den Aufwand für Implementierungen mit verknüpften Listen und Arrays.

Answer 1

Es ist ein verbreiteter Weg, um eine Warteschlange in funktionalen Programmiersprachen mit rein funktionalen (unveränderlich, sondern teile Struktur) Listen (zB Clojure, Haskell, Erlang ...) zu implementieren:

• verwenden, um ein Paar von Listen um eine Warteschlange darzustellen, in der Elemente in FIFO-Reihenfolge in der ersten Liste und in LIFO-Reihenfolge in der zweiten Liste
• Warteschlange in Warteschlange durch Voranstellen an die zweite Liste
• Warteschlange aus der Warteschlange durch das erste Element des ersten Warteschlange Liste
• wenn die erste Liste ist leer: die zweite umzukehren und die erste Liste mit sich, ersetzen und die zweite Liste mit einer leeren Liste

(alle Operationen des neuen Warteschlangenobjekt zusätzlich zu allen möglichen Rückgabewerte zurück)

ersetzen

Der Punkt ist, dass das Hinzufügen (Entfernen) eines Elements zu (von) der Vorderseite einer rein funktionalen Liste O (1) ist und die umgekehrte Operation, die O (n) ist, wird über alle Dequeues amortisiert, so dass es nahe O (1), wodurch Sie eine ~ O (1) Warteschlangenimplementierung mit unveränderlichen Datenstrukturen erhalten.

Answer 2

Es ist eine gute Lernerfahrung, aber keine praktische.

Answer 3

Sie können eine unveränderbare Warteschlange mit zwei unveränderlichen Stapeln erstellen.

Wenn Sie jedoch nur eine veränderbare Warteschlange möchten, ist die Verwendung von zwei Stapeln eine gute Methode, um sie langsamer und komplizierter zu machen, als nur eine verknüpfte Liste zu verwenden.

Answer 4

Dieser Ansatz kann verwendet werden, um eine lock-free-Warteschlange unter Verwendung von zwei atomaren Single-Linked-List-basierten Stapeln zu erstellen, wie sie von Win32 bereitgestellt werden: Interlocked Singly Linked Lists. Der Algorithmus könnte wie in liwp's answer beschrieben sein, obwohl der Umpackschritt (Punkt 4) ein wenig optimiert werden kann.

Lock-free Datenstrukturen und Algorithmen ist eine sehr spannende (zu einigen von uns) Bereich der Programmierung, aber sie müssen sehr sorgfältig verwendet werden. In einer allgemeinen Situation sind lockbasierte Algorithmen effizienter.