Wo würde ich normalerweise eine Deque in Produktionssoftware verwenden?

21

Ich bin mit der Verwendung von Stacks, Queues und Trees in Softwareanwendungen ziemlich vertraut, habe aber noch nie eine Deque (Double Ended Queue) verwendet. Wo würde ich ihnen normalerweise in freier Wildbahn begegnen? Wäre es an den gleichen Orten wie eine Warteschlange, aber mit zusätzlichen Gribbilien?

data-structures Weltingenieur
quelle
2
en.wikipedia.org/wiki/Double-ended_queue#Applications
Arseni Mourzenko
Anscheinend gibt es einige Verwirrung in diesem Thread. Im Internet ist "deque" eine doppelte Warteschlange (Wikipedia erwähnt die Implementierung von verknüpften Listen). In C ++ STL ist "std :: deque" jedoch eine Array-ähnliche Struktur, die als Array von Datenblöcken implementiert ist. Es bietet einen wahlfreien Zugriff, ähnlich wie std :: vector, aber seine Größenänderungsfähigkeit entspricht eher der von std :: list, da beim Hinzufügen von Daten Blöcke hinzugefügt und vorhandene Daten nicht neu zugeordnet und verschoben werden.
DXM
1
@DXM: Eine STL-Deque ist jedoch immer noch eine Warteschlange mit zwei Enden und bietet am Ende schnellere Operationen (abhängig von der Implementierung). Dass es auch Zugriff auf die Mitte bietet, macht die primäre Operation nicht weniger warteschlangenartig.
gbjbaanb
@gbjbaanb: Ich sage nur, wenn Sie sich die öffentlichen Schnittstellen von 3 Klassen ansehen: std :: vector, std :: list (oder std :: queue) und std :: deque, werden Sie diesen std :: vector sehen und std :: deque haben identische öffentliche Schnittstellen und identische Funktionen (std :: deque ist auf Kosten eines größeren Speicherbedarfs etwas flexibler). std :: list und std :: queue verhalten sich dagegen eher wie ihre CS-Gegenstücke, Linked-List bzw. Queue. CS deque! = Std :: deque
DXM
Ich finde diese Antwort praktischer von shiv.mymail - stackoverflow.com/questions/3880254/…
roottraveller

Antworten:

21

Eine Art und Weise, wie eine Deque verwendet wird, ist das "Altern" von Gegenständen. Es wird normalerweise als Rückgängig- oder Verlaufsfunktion verwendet. Eine neue Aktion wird in die Deque eingefügt. Die ältesten Stücke befinden sich vorne. Eine Begrenzung der Größe des Deques zwingt die Elemente an der Vorderseite, zu einem bestimmten Zeitpunkt entfernt zu werden, wenn neue Elemente eingefügt werden (Alterung der ältesten Elemente). Es bietet dann eine schnelle Möglichkeit, auf beide Enden der Struktur zuzugreifen, da Sie sofort die ältesten und neuesten Elemente kennen, um entweder die Vorderseite zu entfernen und die älteste Aktion in O (1) auszuführen oder in O (1) rückgängig zu machen.

jmq
quelle
Ich glaube nicht, dass hier Deques gebraucht werden. Ein einfacher (möglicherweise größenbeschränkter) Stapel reicht aus.
Konrad Rudolph
2
@Konrad Wie altert man Gegenstände in einem einfachen Stapel? (dh wie entfernst du Befehle, die "zu alt" sind?)
Andres F.
@AndresF. Ist das Alter unabhängig von der Stapelgröße? Wenn ja, dann habe ich noch nie von dieser Datenstruktur gehört. Andernfalls handelt es sich einfach um einen Stapel mit fester Größe, der in Form einer Deque implementiert werden kann , oder einfach durch das Postulieren einer einfacheren Datenstruktur, die als Stapel mit fester Größe bezeichnet wird .
Konrad Rudolph
Deques sind also immerhin nützlich;) Ich habe noch nie von einem Stapel mit fester Größe gehört (in dem Sinne, in dem Sie meinen, das älteste Element zu entfernen). Es macht Sinn, aber es ist nicht das, was normalerweise mit "Stapel" gemeint ist, und ob es tatsächlich einfacher ist, bleibt abzuwarten :)
Andres F.
Dies wurde in den Kommentaren der ursprünglichen Frage gepostet: en.wikipedia.org/wiki/Double-ended_queue Es ist nur eine Warteschlange mit zwei Enden. Ich habe es in der Praxis so verwendet, wie ich es oben beschrieben habe (weshalb ich es gepostet habe). In einem echten Stack sollten Sie nur Push, Pop, Top und Peek ausführen (wir könnten uns über andere streiten, aber das ist im Allgemeinen alles). Sie sollten nicht wissen, was sich am Boden des Stapels befindet oder wie Sie auf den Boden zugreifen können. In einem "Stapel mit fester Größe" würden Sie nur einen Stapelüberlauf erzeugen, anstatt alte Elemente beim Befüllen zu altern.
8.
1

Hervorragende Frage. Ich kann mich nicht erinnern, dass unser CS 102-Kurs eine einzelne Anwendung für die doppelte Warteschlange erwähnt hat.

Bis zum heutigen Tag ist die einzige mir bekannte Anwendung der im Wikipedia-Artikel erwähnte Arbeitsplaner .

Es funktioniert im Wesentlichen wie folgt:

In einem normalen Single-Threaded-Vorgehensmodell wird bei jedem Funktionsaufruf ein Aktivierungsdatensatz auf einem sogenannten Aufrufstapel abgelegt . Ein Aktivierungsdatensatz enthält die lokalen Variablen und Parameter dieses Aufrufs. Sobald der Aufruf der Methode abgeschlossen ist ("return"), wird der letzte Aktivierungsdatensatz vom Aufrufstapel abgerufen.

Dies ist besonders wichtig, da auf diese Weise die Rekursion implementiert wird: Die Struktur der Rekursion wird im aktuellen Status des Aufrufstapels dargestellt.

Beim Parallelisieren eines rekursiven Algorithmus können wir diese Eigenschaft ausnutzen, indem wir den Aufrufstapel durch eine Aufrufwarteschlange ersetzen. Jeder Thread in der Berechnung erhält eine eigene Aufrufwarteschlange und überträgt Aktivierungsdatensätze wie bei einer sequentiellen Ausführung.

Sobald ein Thread seine Arbeit beendet hat (= seine Anrufwarteschlange ist leer), stiehlt er Arbeit von einem anderen Thread, indem er einen Aktivierungsdatensatz aus der Anrufwarteschlange dieses Threads entfernt, indem er ihn vom "falschen" Ende entfernt.

Grundsätzlich fungiert die Anrufwarteschlange als zwei Anrufstapel, die jetzt zwei Threads bedienen.

Konrad Rudolph
quelle
Haben Sie eine Quelle dafür? Hört sich interessant an.
kyjelly90210
1
@ Richard1987 Der Wikipedia-Artikel zitiert das Originalpapier. Es gibt mehrere Implementierungen, zum Beispiel in der GNU c ++ stdlib -Implementierung für parallele Erweiterungen, die Arbeit stehlen (aber der Code ist schrecklich zu lesen), oder in einer parallelen Implementierung für generalisiertes Teilen und Erobern durch Sie (letztere verwendet jedoch einen sehr idiomatischen Programmierstil) speziell für die Bibliothek und daher schwer zu lesen)
Konrad Rudolph