Doppelseitige Warteschlange - Double-ended queue

In der Informatik ist eine Double-Ended-Queue (abgekürzt mit deque , ausgesprochen deck , wie "cheque") ein abstrakter Datentyp , der eine Warteschlange verallgemeinert , für die Elemente entweder vorne (Kopf) oder hinten hinzugefügt oder entfernt werden können (Schwanz). Es wird oft auch genannt Kopf-Schwanz - verknüpfte Liste , wenn auch richtig , dies zu einer bestimmten bezieht sich Datenstruktur Implementierung eines Deque (siehe unten).

Regeln der Namensgebung

Deque wird manchmal geschrieben dequeue , aber diese Verwendung wird im Allgemeinen in der Fachliteratur oder im technischen Schreiben abgelehnt , da dequeue auch ein Verb ist, das "aus einer Warteschlange entfernen" bedeutet. Nichtsdestotrotz buchstabieren mehrere Bibliotheken und einige Autoren wie Aho , Hopcroft und Ullman in ihrem Lehrbuch Data Structures and Algorithms Dequeue . Auch John Mitchell , Autor von Concepts in Programming Languages, verwendet diese Terminologie.

Unterscheidungen und Untertypen

Dies unterscheidet sich vom abstrakten Datentyp Queue oder First in First Out List ( FIFO ), bei dem Elemente nur an einem Ende hinzugefügt und am anderen entfernt werden können. Diese allgemeine Datenklasse hat einige mögliche Untertypen:

• Ein Deque mit Eingabebeschränkung ist ein Deque, bei dem das Löschen von beiden Enden, das Einfügen jedoch nur an einem Ende erfolgen kann.
• Ein Deque mit Ausgabebeschränkung ist ein Deque, bei dem das Einfügen an beiden Enden, das Löschen jedoch nur an einem Ende erfolgen kann.

Sowohl die grundlegenden als auch die gebräuchlichsten Listentypen in der Datenverarbeitung, Warteschlangen und Stacks, können als Spezialisierungen von Deques betrachtet und mit Deques implementiert werden.

Betrieb

Die grundlegenden Operationen für eine Deque sind Enqueue und Dequeue an beiden Enden. Ebenfalls allgemein implementiert sind Peek- Operationen, die den Wert an diesem Ende zurückgeben, ohne ihn aus der Warteschlange zu entfernen.

Namen variieren zwischen den Sprachen; Zu den wichtigsten Implementierungen gehören:

Implementierungen

Es gibt mindestens zwei gängige Wege, ein Deque effizient zu implementieren: mit einem modifizierten dynamischen Array oder mit einer doppelt verketteten Liste .

Der dynamische Array-Ansatz verwendet eine Variante eines dynamischen Arrays , die von beiden Enden aus wachsen kann, manchmal als Array deques bezeichnet . Diese Array-Deques haben alle Eigenschaften eines dynamischen Arrays, wie wahlfreien Zugriff mit konstanter Zeit , gute Referenzlokalität und ineffizientes Einfügen/Entfernen in der Mitte, wobei stattdessen an beiden Enden amortisiertes Einfügen/Entfernen mit konstanter Zeit hinzugefügt wird von nur einem Ende. Drei gängige Implementierungen sind:

• Deque-Inhalte in einem Ringpuffer speichern und die Größe nur ändern, wenn der Puffer voll ist. Dadurch wird die Häufigkeit der Größenanpassungen verringert.
• Zuordnen von Deque-Inhalten aus der Mitte des zugrunde liegenden Arrays und Ändern der Größe des zugrunde liegenden Arrays, wenn eines der Enden erreicht ist. Dieser Ansatz kann häufigere Größenänderungen erfordern und mehr Platz verschwenden, insbesondere wenn Elemente nur an einem Ende eingefügt werden.
• Speichern von Inhalten in mehreren kleineren Arrays, Zuweisen zusätzlicher Arrays am Anfang oder Ende nach Bedarf. Die Indizierung wird implementiert, indem ein dynamisches Array beibehalten wird, das Zeiger auf jedes der kleineren Arrays enthält.

Rein funktionale Umsetzung

Double-ended Queues können auch als rein funktionale Datenstruktur realisiert werden . Es gibt zwei Versionen der Implementierung. Die erste, ' Echtzeit-Deque' genannt , wird unten vorgestellt. Es ermöglicht, dass die Warteschlange mit Operationen in der Worst-Case-Zeit von O (1) beständig ist, erfordert jedoch Lazy- Listen mit Memoization . Der zweite, ohne faule Listen oder Auswendiglernen, wird am Ende der Abschnitte präsentiert. Seine amortisierte Zeit beträgt O (1), wenn die Persistenz nicht verwendet wird; aber die Komplexität einer Operation zum schlechtesten Zeitpunkt ist O ( n ), wobei n die Anzahl der Elemente in der doppelseitigen Warteschlange ist.

Erinnern wir uns daran , dass für eine Liste l, |l|deren Länge bezeichnet, die NILeine leere Liste dar und CONS(h, t)stellt die Liste dessen Kopf hund dessen Schwanz ist t. Die Funktionen drop(i, l)und take(i, l)geben die Liste lohne ihre ersten iElemente bzw. die ersten iElemente von lzurück. Oder, wenn |l| < i, geben sie die leere Liste lbzw. zurück.

Echtzeit-Deques durch Lazy Rebuilding und Scheduling

Eine doppelendige Warteschlange wird als Sechsfach dargestellt, (len_front, front, tail_front, len_rear, rear, tail_rear)wobei fronteine verkettete Liste ist, die den Anfang der Warteschlange der Länge enthält len_front. In ähnlicher Weise rearist eine verkettete Liste, die die Rückseite des Endes der Warteschlange darstellt, der Länge len_rear. Darüber hinaus ist sichergestellt, dass |front| ≤ 2|rear|+1und |rear| ≤ 2|front|+1– intuitiv bedeutet dies, dass sowohl die Front als auch die Rückseite zwischen einem Drittel minus einem und zwei Drittel plus einem der Elemente enthalten. Schließlich, tail_frontund tail_rearsind Endungen von frontund von rear, ermöglichen sie die Planung des Moments, in dem einige faule Operationen erzwungen werden. Beachten Sie, dass, wenn eine doppelendige Warteschlange nElemente in der vorderen Liste und nElemente in der hinteren Liste enthält, die Ungleichungsinvariante nach iEinfügungen und dLöschungen erfüllt bleibt, wenn (i+d) ≤ n/2. Das heißt, n/2zwischen jedem Rebalancing können höchstens Operationen stattfinden.

Lassen Sie uns zunächst eine Implementierung der verschiedenen Operationen geben, die sich auf die Vorderseite des Deque-Kontras, Kopf und Schwanz auswirken. Diese Implementierung respektiert nicht unbedingt die Invariante. In einem zweiten Mal erklären wir, wie man eine Deque, die die Invariante nicht erfüllt, in eine Deque umwandelt, die sie erfüllt. Sie verwenden jedoch die Invariante, dass wenn die Vorderseite leer ist, die Rückseite höchstens ein Element hat. Die Operationen, die das Ende der Liste betreffen, werden in ähnlicher Weise durch Symmetrie definiert.

empty = (0, NIL, NIL, 0, NIL, NIL)
fun insert'(x, (len_front, front, tail_front, len_rear, rear, tail_rear)) =
  (len_front+1, CONS(x, front), drop(2, tail_front), len_rear, rear, drop(2, tail_rear))
fun head((_, CONS(h, _), _, _, _, _)) = h
fun head((_, NIL, _, _, CONS(h, NIL), _)) = h
fun tail'((len_front, CONS(head_front, front), tail_front, len_rear, rear, tail_rear)) =
  (len_front - 1, front, drop(2, tail_front), len_rear, rear, drop(2, tail_rear))
fun tail'((_, NIL, _, _, CONS(h, NIL), _)) = empty

Es bleibt zu erklären , wie ein Verfahren zu definieren balance, die die deque Neuverteilung wenn insert'oder taildie Invariante brechen. Das Verfahren insertund tailkann durch zunächst definiert werden , die Anwendung insert'und tail'dann die Anwendung balance.

fun balance(q as (len_front, front, tail_front, len_rear, rear, tail_rear)) =
  let floor_half_len = (len_front + len_rear) / 2 in
  let ceil_half_len = len_front + len_rear - floor_half_len in
  if len_front > 2*len_rear+1 then
    let val front' = take(ceil_half_len, front)
        val rear' = rotateDrop(rear, floor_half_len, front)
    in (ceil_half_len, front', front', floor_half_len, rear', rear')
  else if len_front > 2*len_rear+1 then
    let val rear' = take(floor_half_len, rear)
        val front' = rotateDrop(front, ceil_half_len, rear)
    in (ceil_half_len, front', front', floor_half_len, rear', rear')
  else q

wobei rotateDrop(front, i, rear))die Verkettung von frontund von zurückgeben drop(i, rear). Das ist front' = rotateDrop(front, ceil_half_len, rear)in front'den Inhalt von enthalten frontund der Inhalt reardavon ist nicht bereits in rear'. Da das Ablegen von nElementen Zeit in Anspruch nimmt , verwenden wir Faulheit, um sicherzustellen, dass Elemente zu zweit abgeworfen werden, wobei bei jedem Vorgang zwei Abwürfe durchgeführt werden. ${\displaystyle O(n)}$tail'insert'

fun rotateDrop(front, i, rear) =
  if i < 2 then rotateRev(front, drop(i, rear), $NIL)
  else let $CONS(x, front') = front in
    $CONS (x, rotateDrop(front', j-2, drop(2, rear)))

wobei rotateRev(front, middle, rear)eine Funktion ist, die die Vorderseite zurückgibt, gefolgt von der Mitte umgekehrt, gefolgt von der Rückseite. Diese Funktion wird auch definiert Trägheit verwendet , um sicherzustellen , dass es Schritt für Schritt berechneter sein kann, mit einem Schritt während jeden ausgeführten insert'und tail'und eine konstante Zeit. Diese Funktion verwendet die Invariante |rear|-2|front|2 oder 3.

fun rotateRev(NIL, rear, a)=
  reverse(rear++a)
fun rotateRev(CONS(x, front), rear, a)=
  CONS(x, rotateRev(front, drop(2, rear), reverse (take(2, rear))++a))

Wo ++ist die Funktion, die zwei Listen verkettet.

Umsetzung ohne Faulheit

Beachten Sie, dass dies ohne den faulen Teil der Implementierung eine nicht persistente Implementierung der Warteschlange in O (1) amortisierter Zeit wäre . In diesem Fall könnten die Listen tail_frontund tail_rearaus der Darstellung der doppelseitigen Warteschlange entfernt werden.

Sprachunterstützung

Die Container von Ada stellen die generischen Pakete Ada.Containers.Vectorsund Ada.Containers.Doubly_Linked_Listsfür die Implementierungen dynamischer Arrays bzw. verknüpfter Listen bereit .

Die Standardvorlagenbibliothek von C++ stellt die Klassenvorlagen std::dequeund std::listfür die Implementierungen mehrerer Arrays bzw. verknüpfter Listen bereit .

Ab Java 6 stellt Javas Collections Framework eine neue DequeSchnittstelle bereit, die die Funktionalität des Einfügens und Entfernens an beiden Enden bereitstellt. Es wird durch Klassen wie ArrayDeque(ebenfalls neu in Java 6) und LinkedListimplementiert, die die dynamischen Array- bzw. Linked-List-Implementierungen bereitstellen. Im ArrayDequeGegensatz zu seinem Namen unterstützt das jedoch keinen Direktzugriff.

Javascript des Array - Prototyp & Perl ‚s Arrays native Unterstützung für sowohl das Entfernen ( Verschiebung und Pop ) und das Hinzufügen ( unshift und Push ) Elemente an beiden Enden.

Python 2.4 führte das collectionsModul mit Unterstützung für Deque-Objekte ein . Sie wird unter Verwendung einer doppelt verketteten Liste von Subarrays fester Länge implementiert.

Ab PHP 5.3 enthält die SPL-Erweiterung von PHP die Klasse 'SplDoublyLinkedList', mit der Deque-Datenstrukturen implementiert werden können. Um eine Deque-Struktur zu erstellen, mussten bisher stattdessen die Array-Funktionen array_shift/unshift/pop/push verwendet werden.

Das Data.Sequence- Modul von GHC implementiert eine effiziente, funktionale Deque-Struktur in Haskell . Die Implementierung verwendet 2–3 Fingerbäume, die mit Größen annotiert sind. Es gibt andere (schnelle) Möglichkeiten, rein funktionale (also auch persistente ) Double-Queues zu implementieren (meist mit stark fauler Auswertung ). Kaplan und Tarjan waren die ersten, die optimale konfluent persistente kettebare Deques implementierten. Ihre Implementierung war streng rein funktional in dem Sinne, dass sie keine faule Auswertung verwendet. Okasaki vereinfachte die Datenstruktur, indem es eine Lazy-Evaluation mit einer Bootstrapped-Datenstruktur verwendet und die Leistungsgrenzen vom Worst-Case auf amortisiert herabgestuft hat. Kaplan, Okasaki und Tarjan produzierten eine einfachere, nicht-bootstrapped, amortisierte Version, die entweder durch faule Evaluierung oder effizienter durch Mutation in einer breiteren, aber immer noch eingeschränkten Weise implementiert werden kann. Mihaesau und Tarjan schufen eine einfachere (aber immer noch hochkomplexe) streng rein funktionale Implementierung von verkettebaren Deques und auch eine viel einfachere Implementierung von streng rein funktionalen nicht verkettebaren Deques, die beide optimale Worst-Case-Grenzen haben.

Rust std::collectionsenthält VecDeque, das eine doppelseitige Warteschlange mit einem erweiterbaren Ringpuffer implementiert.

Komplexität

• In einer doppelt verknüpften Listenimplementierung und unter der Annahme, dass kein Zuweisungs-/Zuweisungs-Overhead angenommen wird, beträgt die Zeitkomplexität aller Deque-Operationen O(1) . Außerdem beträgt die Zeitkomplexität des Einfügens oder Löschens in der Mitte bei einem gegebenen Iterator O(1); die Zeitkomplexität des wahlfreien Zugriffs nach Index beträgt jedoch O(n).
• In einem wachsenden Array beträgt die amortisierte Zeitkomplexität aller Deque-Operationen O(1) . Außerdem beträgt die Zeitkomplexität des wahlfreien Zugriffs nach Index O(1); aber die Zeitkomplexität des Einfügens oder Löschens in der Mitte ist O(n) .

Anwendungen

Ein Beispiel, bei dem ein Deque verwendet werden kann, ist der Work-Stealing-Algorithmus . Dieser Algorithmus implementiert die Aufgabenplanung für mehrere Prozessoren. Für jeden Prozessor wird ein separates Deque mit auszuführenden Threads verwaltet. Um den nächsten Thread auszuführen, holt der Prozessor das erste Element aus dem Deque (unter Verwendung der Deque-Operation "Entferne erstes Element"). Wenn sich der aktuelle Thread teilt, wird er wieder an den Anfang des Deques gestellt ("Element vorne einfügen") und ein neuer Thread wird ausgeführt. Wenn einer der Prozessoren die Ausführung seiner eigenen Threads beendet (dh sein Deque ist leer), kann er einen Thread von einem anderen Prozessor "stehlen": Er holt sich das letzte Element aus dem Deque eines anderen Prozessors ("remove last element") und führt es. Der Work-Stealing-Algorithmus wird von Intels Threading Building Blocks (TBB)-Bibliothek für die parallele Programmierung verwendet.

Siehe auch

• Rohr
• Warteschlange
• Prioritätswarteschlange

Verweise

Externe Links

• Typsichere Open-Source-Deque-Implementierung im Comprehensive C Archive Network
• SGI STL-Dokumentation: deque<T, Alloc>
• Code-Projekt: Eine eingehende Studie des STL-Deque-Containers
• Deque-Implementierung in C
• VBScript-Implementierung von Stack, Queue, Deque und Red-Black Tree
• Mehrere Implementierungen von nicht verknüpfbaren Deques in Haskell