Deque

Grundidee und wichtige Operationen

Ein Deque („Double-ended queue“, gesprochen „Deck“) ist eine Datenstruktur der Informatik. Es ähnelt sowohl einer Warteschlange als auch einem Stapelspeicher und kombiniert Eigenschaften beider Strukturen. Sein entscheidendes Merkmal ist, dass Elemente an beiden Enden gelesen, eingefügt und entfernt werden können.

Die Bezeichnungen der Operationen unterscheiden sich je nach Programmbibliothek:

• push und pop fügen ein Element am hinteren Ende ein beziehungsweise entnehmen es dort.
• put und get fügen ein Element am vorderen Ende ein beziehungsweise entnehmen es dort.
• first und last lesen das erste beziehungsweise letzte Element, ohne es zu entfernen.

Aufbau, Zugriff und Effizienz

Ein Deque ist ein Sequenzcontainer mit dynamischer Größe. Er kann sowohl vorne als auch hinten erweitert oder verkleinert werden. Der Speicher wird automatisch verwaltet: Der Container wächst und schrumpft nach Bedarf.

Technisch kann ein Deque als Array von Pointern auf einzelne, gleich große Speicherblöcke, sogenannte Chunks, realisiert werden. Da alle Chunks gleich groß sind, lässt sich für einen Index schnell berechnen, in welchem Chunk das gesuchte Element liegt. Dadurch ist wahlfreier Zugriff, etwa mit dem Operator [], in konstanter Zeit möglich, wie es der C++-Standard verlangt. Iteratoren mit wahlfreiem Zugriff erlauben ebenfalls den direkten Zugriff auf einzelne Elemente.

In einen Chunk passen mehrere Elemente. Deshalb ist beim Einfügen oder Entfernen an den Enden nicht für jedes einzelne Element eine neue Speicherallokation nötig: Für so viele Elemente, wie in einen Chunk passen, genügt genau eine Allokation. Dies kann schneller sein als bei einer verketteten Liste.

Wie ein dynamisches Array bietet ein Deque direkten Zugriff auf seine Elemente. Im Unterschied zu einem gewöhnlichen Array oder Vektor liegen seine Elemente jedoch nicht garantiert an zusammenhängenden Speicheradressen. Das Versetzen eines Zeigers von einem Element zu einem anderen führt deshalb zu undefiniertem Verhalten. Ein Vektor verwendet dagegen ein einzelnes zusammenhängendes Array, das beim Wachstum gelegentlich vollständig neu zugewiesen werden muss. Bei einem Deque können die Elemente über mehrere Speicherblöcke verteilt sein; die für den Zugriff nötigen Informationen verwaltet der Container intern.

Diese interne Struktur ist komplexer, kann aber besonders bei sehr langen Sequenzen ein effizienteres Wachstum ermöglichen, weil teure Neuzuweisungen vermieden werden. Für häufiges Einfügen und Löschen an anderen Stellen als dem Anfang oder Ende ist ein Deque weniger geeignet. In solchen Fällen ist es schlechter als eine Liste und bietet weniger konsistente Iteratoren und Referenzen.

Deques werden unter anderem zur Implementierung nichtdeterministischer endlicher Automaten und bei der Textsuche mit regulären Ausdrücken in Pattern-Matching-Algorithmen verwendet.

C++-Beispiel mit Spielkarten

In der C++-Standardbibliothek steht die Klasse deque zur Verfügung. Im Beispiel wird mit deque<string> ein Deque angelegt, dessen Elemente Zeichenketten sind. Zunächst werden mit push_back die drei Karten „Kreuz Bube“, „Herz Dame“ und „Karo König“ am Ende eingefügt. size() liefert danach die Länge 3. front() liest „Kreuz Bube“ am Anfang und back() liest „Karo König“ am Ende, ohne die Elemente zu entfernen.

Mit push_front("Kreuz 10") wird vorne eine weitere Karte ergänzt. Die Reihenfolge lautet nun („Kreuz 10“, „Kreuz Bube“, „Herz Dame“, „Karo König“). pop_back() entfernt anschließend „Karo König“ am hinteren Ende. Danach fügt push_back("Karo Ass") am Ende das „Karo Ass“ ein. Schließlich entfernt pop_front() die vorne liegende Karte „Kreuz 10“. Übrig bleiben („Kreuz Bube“, „Herz Dame“, „Karo Ass“).

Die zusätzliche Funktion toString erhält eine Referenz auf ein deque<string> und erzeugt daraus eine Textdarstellung der Form „(A, B, C, ...)“. empty() prüft zunächst, ob das Deque leer ist; in diesem Fall wird „()“ zurückgegeben. Andernfalls durchläuft eine Schleife die Elemente. at(i) greift dabei über den jeweiligen Index auf sie zu und fügt sie mit Kommas getrennt in den Ausgabetext ein.

Für Karten- und Gesellschaftsspiele, in denen Karten ausschließlich auf einen Stapel gelegt oder von ihm gezogen werden, sind statt eines Deque Stacks geeignet.