2003:C3:6711:DD00:1531:7A53:A5B9:F798: /* Programmierung */

2024-08-25T22:02:03Z

Programmierung

Neue Seite

Ein '''Deque''' ('''''D'''ouble-'''e'''nded '''que'''ue'', sprich: „Deck“) bezeichnet eine [[Datenstruktur]] der [[Informatik]].

Hierbei handelt es sich um eine [[Datenstruktur]] ähnlich der [[Warteschlange (Datenstruktur)|Warteschlange]] oder des [[Stapelspeicher]]s. Es kombiniert die Eigenschaften beider [[Datentyp|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 [[Programmbibliothek|Programmbibliotheken]] verschiedener [[Programmiersprache|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 [[Programmbibliothek|Programmbibliotheken]] können Deques auf unterschiedliche Weise implementieren, im Allgemeinen als eine Form eines dynamischen [[Feld (Datentyp)|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 [[Feld (Datentyp)|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 [[Speicheradresse|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 [[Speicherblock|Speicherblöcke]] verstreut werden, wobei der Container die erforderlichen Informationen intern speichert, um in konstanter [[Laufzeit (Informatik)|Laufzeit]] und mit einer einheitlichen sequentiellen Schnittstelle (über [[Iterator|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 [[Operation (Informatik)|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 [[Iterator (Entwurfsmuster)|Iteratoren]] und [[Referenz (Programmierung)|Referenzen]] auf als [[Liste (Datenstruktur)|Listen]].<ref>www.cplusplus.com: [https://www.cplusplus.com/reference/deque/deque/ deque]</ref>

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

== Programmierung ==
Das folgende Beispiel in der [[Programmiersprache]] [[C++]] mit Spielkarten zeigt die Verwendung der [[Klasse (Objektorientierung)|Klasse]] ''deque'' der [[C++-Standardbibliothek]] (siehe auch [[Template (C++)#Klassen-Templates|Template (C++) - Klassen-Templates]]). Bei der Ausführung des Programms wird die Methode ''main'' verwendet.<ref>Microsoft Docs: [https://docs.microsoft.com/en-us/cpp/standard-library/deque-class?view=msvc-160 deque Class]</ref><syntaxhighlight lang="cpp">
#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)
}
</syntaxhighlight>
Für die Ausgabe des Deque wird folgende [[Methode (Programmierung)|Methode]] verwendet:
<syntaxhighlight lang="cpp">
// 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;
}
</syntaxhighlight>
Für die Programmierung von [[Kartenspiel|Kartenspielen]] und [[Gesellschaftsspiel|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|Stapelspeicher - Beispiel mit Spielkarten]]).

== Siehe auch ==

* [[Warteschlange (Datenstruktur)]]
* [[Stapelspeicher]]
* [[Doppelt verkettete Liste]]
* [[Heap (Datenstruktur)]]
*[[Iterator]]

== Weblinks ==
www.geeksforgeeks.org: [https://www.geeksforgeeks.org/implementation-deque-using-doubly-linked-list/ Implementation of Deque using doubly linked list]

== Einzelnachweise ==
<references />

[[Kategorie:Datenstruktur]]

Deque - Versionsgeschichte

2003:C3:6711:DD00:1531:7A53:A5B9:F798: /* Programmierung */