Deque

Ein Deque (Double-ended queue, sprich: „Deck“) bezeichnet eine Datenstruktur der Informatik.

Hierbei handelt es sich um eine Datenstruktur ähnlich der Warteschlange oder des Stapelspeichers. Es kombiniert die Eigenschaften beider Datentypen. Der Unterschied besteht darin, dass die Daten an beiden Enden gelesen, eingefügt oder entfernt werden können.

Eigenschaften

Die Operationen eines Deque, die in den Programmbibliotheken verschiedener Programmiersprachen nicht einheitlich benannt sind:

• push und pop für das Einfügen oder Entnehmen eines Elements am hinteren Ende der Deque.
• put und get für das Einfügen oder Entnehmen am vorderen Ende der Deque.
• first und last für das Lesen des ersten oder letzten Elementes, ohne es zu entfernen.

Technisch wird ein Deque als ein Array von Pointern auf einzelne Chunks mit jeweils gleicher Größe realisiert. Damit ist gesichert, dass der wahlfreie Zugriff mit konstanter Zeit erfolgen kann, was der C++-Standard verlangt. Durch die jeweils gleiche Größe der Chunks lässt sich deren Position für den indizierten Zugriff (Operator []) schnell berechnen. Dies wäre mit einer verketteten Liste nicht möglich. Dadurch, dass jeweils mehrere Elemente in einen Chunk passen ist das Einfügen und Entfernen an den Enden schneller als bei einer Liste da für so viele Elemente die in einen Chunk passen genau eine Speicherallokation erforderlich ist.

Deques sind Sequenzcontainer mit dynamischen Größen, die an beiden Enden (entweder vorne oder hinten) erweitert oder verkleinert werden können. Bestimmte Programmbibliotheken können Deques auf unterschiedliche Weise implementieren, im Allgemeinen als eine Form eines dynamischen Arrays. In jedem Fall ermöglichen sie jedoch den direkten Zugriff auf die einzelnen Elemente über Iteratoren mit wahlfreiem Zugriff, wobei der Speicher automatisch verwaltet wird, indem der Container nach Bedarf erweitert und verkleinert wird.

Daher bieten sie eine ähnliche Funktionalität wie Arrays, jedoch mit effizienter Einfügung und Löschung von Elementen auch am Anfang der Sequenz und nicht nur am Ende. Im Gegensatz zu Arrays wird jedoch nicht garantiert, dass Deques alle ihre Elemente an zusammenhängenden Speicheradressen speichern: Der Zugriff auf Elemente in einer Deque durch Versetzen eines Zeigers auf ein anderes Element führt zu undefiniertem Verhalten. Sowohl dynamischen Arrays als auch Deques bieten eine sehr ähnliche Schnittstelle und können für ähnliche Zwecke verwendet werden, aber intern funktionieren beide auf ganz unterschiedliche Weise: Während Vektoren ein einzelnes Array verwenden, das gelegentlich für das Wachstum neu zugewiesen werden muss, können die Elemente eines Deque auf verschiedene Speicherblöcke verstreut werden, wobei der Container die erforderlichen Informationen intern speichert, um in konstanter Laufzeit und mit einer einheitlichen sequentiellen Schnittstelle (über Iteratoren) direkten Zugriff auf eines seiner Elemente zu ermöglichen.

Daher sind Deques intern etwas komplexer, aber dies ermöglicht es ihnen, unter bestimmten Umständen effizienter zu wachsen, insbesondere bei sehr langen Sequenzen, bei denen Neuzuweisungen teurer werden. Bei Operationen, bei denen Elemente häufig an anderen Positionen als am Anfang oder am Ende eingefügt oder entfernt werden, sind Deques schlechter und weisen weniger konsistente Iteratoren und Referenzen auf als Listen.

In der Praxis verwendet man die Deque unter anderem zur Implementierung von nichtdeterministischen endlichen Automaten und zur Textsuche mittels regulärer Ausdrücke (Pattern-Matching-Algorithmus).

Programmierung

Das folgende Beispiel in der Programmiersprache C++ mit Spielkarten zeigt die Verwendung der Klasse deque der C++-Standardbibliothek (siehe auch Template (C++) - Klassen-Templates). Bei der Ausführung des Programms wird die Methode main verwendet.

#include <deque> // Bindet den Datentyp deque in das Programm ein
#include <iostream>

using namespace std;

int main()
{
    deque<string> myDeque; // Deklariert ein Deque mit dem Elementtyp string

    // Fügt dem Deque 3 Elemente vom Typ string am Ende hinzu
    myDeque.push_back("Kreuz Bube");
    myDeque.push_back("Herz Dame");
    myDeque.push_back("Karo König");

    cout << "Die Länge des Deque ist "
         << myDeque.size() << endl;    // Ausgabe Anzahl der Elemente
    string card = myDeque.front();     // Weist das Element am Anfang ("Kreuz Bube") der Variablen card zu
    cout << "Die Karte am Anfang der Deque ist: "
         << card << endl;              // Ausgabe
    card = myDeque.back();             // Weist das Element am Ende ("Karo König") der Variablen card zu
    cout << "Die Karte am Ende der Deque ist: "
         << card << endl;              // Ausgabe der Karte
    cout << toString(myDeque) << endl; // Ausgabe: (Kreuz Bube, Herz Dame, Karo König)

    myDeque.push_front("Kreuz 10");    // Fügt 1 Element am Anfang des Deque ein

    cout << "Die Länge des Deque ist "
         << myDeque.size() << endl;    // Ausgabe Anzahl der Elemente 
    cout << toString(myDeque) << endl; // Ausgabe: (Kreuz 10, Kreuz Bube, Herz Dame, Karo König)

    myDeque.pop_back();                // Entfernt das Element am Ende
    cout << toString(myDeque) << endl; // Ausgabe: (Kreuz 10, Kreuz Bube, Herz Dame)

    myDeque.push_back("Karo Ass");     // Fügt dem Deque 1 Element am Ende hinzu
    cout << toString(myDeque) << endl; // Ausgabe auf der Konsole: (Kreuz 10, Kreuz Bube, Herz Dame, Karo Ass)

    myDeque.pop_front();               // Entfernt das Element am Anfang
    cout << toString(myDeque) << endl; // Ausgabe: (Kreuz Bube, Herz Dame, Karo Ass)
}

Für die Ausgabe des Deque wird folgende Methode verwendet:

// Diese Methode gibt das Deque in der Form (A, B, C, ...) als Text zurück.
string toString(deque<string> & aDeque)
{
    if (aDeque.empty())
        return "()";
    string text = "(";
    for (size_t i = 0; i < aDeque.size() - 1; i++)
        text += aDeque.at(i) + ", ";
    text += aDeque.at(aDeque.size() - 1) + ")";
    return text;
}

Für die Programmierung von Kartenspielen und Gesellschaftsspielen mit Stapeln, bei denen während des Spiels Karten auf einen Stapel gelegt oder von einem Stapel gezogen wird, sind stattdessen Stacks geeignet (siehe Stapelspeicher - Beispiel mit Spielkarten).

Siehe auch

• Warteschlange (Datenstruktur)
• Stapelspeicher
• Doppelt verkettete Liste
• Heap (Datenstruktur)
• Iterator

Weblinks

www.geeksforgeeks.org: Implementation of Deque using doubly linked list