Warteschlange (abstrakter Datentyp)

Darstellung von a FIFO (Zuerst in, zuerst aus) Warteschlange

Im Informatik, a Warteschlange ist ein Sammlung von Entitäten, die in einer Sequenz gehalten werden und durch Zugabe von Entitäten an einem Ende der Sequenz und der Entfernung von Entitäten aus dem anderen Ende der Sequenz modifiziert werden können. Durch Konvention wird das Ende der Sequenz, in der Elemente hinzugefügt werden Die Leute stehen an, um auf Waren oder Dienstleistungen zu warten.

Der Betrieb des Hinzufügens eines Elements zur Rückseite der Warteschlange ist bekannt als Enqueueund der Betrieb des Entfernens eines Elements von vorne ist als bekannt als Dequeue. Andere Operationen können ebenfalls erlaubt sein, häufig auch ein spähen oder Vorderseite Operation, der den Wert des nächsten Elements zurückgibt, das ohne ihn entgegenkommt.

Die Operationen einer Warteschlange machen es a FIFO-Datenstruktur (erstmal. In einer FIFO -Datenstruktur ist das erste Element, das der Warteschlange hinzugefügt wurde, das erste, der entfernt wird. Dies entspricht der Anforderung, dass alle Elemente, die zuvor hinzugefügt wurden, nach dem Entfernen des neuen Elements, sobald ein neues Element hinzugefügt wurde. Eine Warteschlange ist ein Beispiel für a Lineare Datenstrukturoder eine abstraktere Sammlung. Warteschlangen sind in Computerprogrammen üblich, in denen sie als Datenstrukturen in Verbindung mit Zugriffsroutinen implementiert werden Abstrakte Datenstruktur oder in objektorientierten Sprachen als Klassen. Gemeinsame Implementierungen sind Rundpuffer und verlinkte Listen.

Warteschlangen bieten Dienstleistungen in Informatik, Transport, und Unternehmensforschung wo verschiedene Entitäten wie Daten, Objekte, Personen oder Ereignisse gespeichert und später verarbeitet werden. In diesen Kontexten führt die Warteschlange die Funktion von a aus Puffer. Eine weitere Verwendung von Warteschlangen ist die Implementierung von Breite-First-Suche.

Warteschlangenimplementierung

Theoretisch ist ein Merkmal einer Warteschlange, dass es keine bestimmte Kapazität hat. Unabhängig davon, wie viele Elemente bereits enthalten sind, kann immer ein neues Element hinzugefügt werden. Es kann auch leer sein, an diesem Punkt wird das Entfernen eines Elements unmöglich sein, bis ein neues Element erneut hinzugefügt wurde.

Arrays mit fester Länge sind in Kapazität begrenzt, aber es ist nicht wahr, dass Elemente in Richtung des Kopfes der Warteschlange kopiert werden müssen. Der einfache Trick, das Array in einen geschlossenen Kreis zu verwandeln und den Kopf und den Schwanz endlos in diesem Kreis zu treiben, macht es unnötig, jemals im Array gespeicherte Gegenstände zu bewegen. Wenn n die Größe des Arrays hat, wird das Computerindizes -Modulo n Array in einen Kreis. Dies ist nach wie vor die konzeptionell einfachste Möglichkeit, eine Warteschlange in einer Sprache auf hoher Ebene zu konstruieren, aber es verlangsamt die Dinge zugegebenermaßen ein wenig, da die Array-Indizes mit Null verglichen werden müssen Überprüfen Sie, ob ein Array-Index außerhalb der Grenzen liegt, was einige Sprachen tun. Dies ist jedoch sicherlich die Methode der Wahl für eine schnelle und schmutzige Implementierung oder für jede hochrangige Sprache, die keine Zeigersyntax hat. Die Array -Größe muss im Voraus deklariert werden, aber einige Implementierungen verdoppeln einfach die deklarierte Array -Größe, wenn Überlauf auftritt. Die meisten modernen Sprachen mit Objekten oder Zeiger kann Bibliotheken für dynamische Listen implementieren oder ausgestattet sein. Eine solche Datenstrukturen Möglicherweise hat neben Speicherbeschränkungen keine feste Kapazitätsgrenze angegeben. Warteschlange Überlauf Ergebnisse des Versuchs, ein Element in eine vollständige Warteschlange und Warteschlange hinzuzufügen Unterfluss passiert, wenn Sie versuchen, ein Element aus einer leeren Warteschlange zu entfernen.

A begrenzte Warteschlange ist eine Warteschlange, die auf eine feste Anzahl von Elementen beschränkt ist.^[1]

Es gibt mehrere effiziente Implementierungen von FIFO -Warteschlangen. Eine effiziente Implementierung ist eine, die die Operationen-engagieren und wesentlich-durchführen kann O (1) Zeit.

• Verlinkte Liste
  • A doppelt verknüpfte Liste Hat O (1) Einfügung und Löschung an beiden Enden, daher ist es eine natürliche Wahl für Warteschlangen.
  • Eine regelmäßige einzig verknüpfte Liste hat nur ein effizientes Einfügen und Löschen an einem Ende. Eine kleine Modifikation - einen Zeiger auf die letzte Der Knoten zusätzlich zum ersten ermöglicht es ihm, eine effiziente Warteschlange zu implementieren.
• A Deque implementiert mit einem modifizierten dynamischen Array

Warteschlangen und Programmiersprachen

Warteschlangen können als separater Datentyp implementiert oder als Sonderfall von a angesehen werden Doppelte-Warteschlange (deque) und nicht separat implementiert. Zum Beispiel, Perl und Rubin Lassen Sie ein Array von beiden Enden schieben und knallen, damit man verwenden kann drücken und Wechsel Funktionen zu Enqueue und dequeue eine Liste (oder umgekehrt kann man verwenden unerschütterlich und Pop),^[2] Obwohl in einigen Fällen diese Vorgänge nicht effizient sind.

C ++ 's Standard -Vorlagenbibliothek Bietet ein ""Warteschlange"Vorlagenklasse, die nur auf Push/Pop -Operationen beschränkt ist. Seit J2SE5.0 enthält Javas Bibliothek a Warteschlange Schnittstelle, die Warteschlangenoperationen angibt; Implementierung von Klassen umfassen LinkedList und (seit J2SE 1.6) Arraydeque. PHP hat an Splqueue Klassen- und Drittbibliotheken wie BeaneStalk'd und Gearmter.

Beispiel

Eine einfache Warteschlange implementiert in JavaScript:

Klasse Warteschlange {  Konstrukteur() {  Dies.Artikel = [];  }  Enqueue(Element) {  Dies.Artikel.drücken(Element);  }  Dequeue() {  Rückkehr Dies.Artikel.Wechsel();  } } 

Rein funktionelle Implementierung

Warteschlangen können auch als implementiert werden rein funktionale Datenstruktur.^[3] Es gibt zwei Implementierungen. Der erste erreicht nur ${\ displayStyle o (1)}$ pro Operation im Durchschnitt. Das heißt, das amortisiert Zeit ist ${\ displayStyle o (1)}$, aber individuelle Operationen können dauern ${\ displayStyle o (n)}$ wo n ist die Anzahl der Elemente in der Warteschlange. Die zweite Implementierung heißt a Echtzeit-Warteschlange^[4] und es ermöglicht es der Warteschlange zu sein hartnäckig mit Operationen in O (1) schlechteste Zeit. Es ist eine komplexere Implementierung und erfordert faul Listen mit Memoisierung.

Amortisierte Warteschlange

Die Daten dieser Warteschlange werden in zwei gespeichert Einzellisten genannt ${\ displayStyle f}$ und ${\ displayStyle r}$. Die Liste ${\ displayStyle f}$ Hält den vorderen Teil der Warteschlange. Die Liste ${\ displayStyle r}$ Hält die verbleibenden Elemente (a.k.a., die Rückseite der Warteschlange) in umgekehrter Reihenfolge. Es ist einfach, in die Vorderseite der Warteschlange einzulegen, indem Sie einen Knoten am Kopf von hinzufügen ${\ displayStyle f}$. Und wenn ${\ displayStyle r}$ ist nicht leer, es ist leicht, vom Ende der Warteschlange zu entfernen, indem der Knoten am Kopf von entfernen ${\ displayStyle r}$. Wann ${\ displayStyle r}$ ist leer, die Liste ${\ displayStyle f}$ wird umgekehrt und zugeordnet ${\ displayStyle r}$ und dann der Kopf von ${\ displayStyle r}$ ist entfernt.

Der Einsatz ("Enqueue") nimmt immer nimmt ${\ displayStyle o (1)}$ Zeit. Die Entfernung ("dequeue") dauert ${\ displayStyle o (1)}$ wenn die Liste ${\ displayStyle r}$ ist nicht leer. Wann ${\ displayStyle r}$ ist leer, die Rückseite nimmt nimmt ${\ displayStyle o (n)}$ wo ${\ displayStyle n}$ ist die Anzahl der Elemente in ${\ displayStyle f}$. Aber wir können sagen, dass es ist ${\ displayStyle o (1)}$ amortisiert Zeit, weil jedes Element in ${\ displayStyle f}$ mussten eingefügt werden und wir können für jedes Element im Umkehr, wenn es eingefügt wurde, konstante Kosten zuweisen.

Echtzeit-Warteschlange

Die Echtzeit-Warteschlange erreicht ${\ displayStyle o (1)}$ Zeit für alle Operationen ohne Amortisation. Diese Diskussion wird technisch sein, erinnern Sie sich also an das ${\ displayStyle l}$ eine Liste, ${\ displayStyle | l |}$ bezeichnet seine Länge, das NULL repräsentiert eine leere Liste und ${\ displayStyle \ operatorname {cons} (h, t)}$ repräsentiert die Liste, deren Kopf ist h und wessen Schwanz ist t.

Die zur Implementierung unserer Warteschlangen verwendeten Datenstruktur besteht aus drei Einzellisten ${\ displayStyle (f, r, s)}$ wo f ist die Vorderseite der Warteschlange, r ist die Rückseite der Warteschlange in umgekehrter Reihenfolge. Die Invariante der Struktur ist das s ist die Rückseite von f ohne es ${\ displayStyle | r |}$ Erste Elemente, das heißt ${\ displayStyle | s | = | f |-| r |}$. Der Schwanz der Warteschlange ${\ displayStyle (\ operatorname {cons} (x, f), r, s)}$ ist dann fast ${\ displayStyle (f, r, s)}$ und ein Element einfügen x zu ${\ displayStyle (f, r, s)}$ ist fast ${\ displayStyle (f, \ operatorname {cons} (x, r), s)}$. Es wird fast gesagt, weil in beiden Ergebnissen, ${\ displayStyle | s | = | f |-| r | +1}$. Eine Hilfsfunktion ${\ displayStyle aux}$ muss dann aufgefordert werden, dass die Invariante zufrieden ist. Es müssen zwei Fälle berücksichtigt werden, je nachdem, ob ${\ displayStyle S}$ ist die leere Liste, in diesem Fall ${\ displayStyle | r | = | f | +1}$, oder nicht. Die formale Definition ist $oder$ und ${\ displaystyle \ operatorname {aux} (f, r, {\ text {nil}}) = (f ', {\ text {nil}}, f')}$ wo ${\ displayStyle f '}$ ist f gefolgt von r umgedreht.

Rufen Sie an ${\ displayStyle \ operatorname {reverse} (f, r)}$ die Funktion, die zurückgibt f gefolgt von r umgedreht. Nehmen wir das außerdem an, das ${\ displayStyle | r | = | f | +1}$Da es sich um den Fall handelt, wenn diese Funktion aufgerufen wird. Genauer gesagt, wir definieren eine faule Funktion ${\ displayStyle \ operatorname {rotate} (f, r, a)}$ das dauert als Eingabe drei Liste, so dass ${\ displayStyle | r | = | f | +1}$und die Verkettung von zurückgeben f, von r umgekehrt und von a. Dann $oder$. Die induktive Definition von Drehen ist $oder$ und $oder r, \ operatorname {cons} (y, a)))}$. Seine Laufzeit ist ${\ displayStyle o (r)}$Aber da eine faule Bewertung verwendet wird, wird die Berechnung verzögert, bis die Ergebnisse durch die Berechnung erzwungen werden.

Die Liste s In der Datenstruktur hat zwei Zwecke. Diese Liste dient als Zähler für ${\ displayStyle | f |-| r |}$, in der Tat, ${\ displayStyle | f | = | r |}$ dann und nur dann, wenn s ist die leere Liste. Mit diesem Zähler können wir sicherstellen, dass das Heck niemals länger als die vordere Liste ist. Außerdem verwendet s, was ein Schwanz von ist ferzwingt die Berechnung eines Teils der (faulen) Liste f in jedem Schwanz und Einfügung Betrieb. Daher wann ${\ displayStyle | f | = | r |}$, Die Liste f ist total gezwungen. Wenn es nicht der Fall war, die interne Darstellung von f Könnte ein Anhang von Anhängen von ... des Anhangs sein, und das Erzwingen wäre kein ständiger Zeitbetrieb mehr.

Siehe auch

• Rundpuffer
• Doppelte-Warteschlange (Deque)
• Prioritätswarteschlange
• Warteschlangentheorie
• Stack (abstrakter Datentyp) - Das "Gegenteil" einer Warteschlange: LIFO (zuletzt zuerst)

Verweise

Allgemeine Referenzen

• Dieser Artikel enthält Public Domain Materialvon demNIST dokumentieren: Schwarz, Paul E. "Begrenzte Warteschlange". Wörterbuch von Algorithmen und Datenstrukturen.

Weitere Lektüre

• Donald Knuth. Die Kunst der Computerprogrammierung, Band 1: Grundalgorithmen, Dritte Edition. Addison-Wesley, 1997. ISBN0-201-89683-4. Abschnitt 2.2.1: Stapel, Warteschlangen und Dequeueis, S. 238–243.
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, und Clifford Stein. Einführung in Algorithmen, Zweite Ausgabe. MIT Press und McGraw-Hill, 2001. ISBN0-262-03293-7. Abschnitt 10.1: Stapel und Warteschlangen, S. 200–204.
• William Ford, William Topp. Datenstrukturen mit C ++ und STL, Zweite Ausgabe. Prentice Hall, 2002. ISBN0-13-085850-1. Kapitel 8: Warteschlangen und vorrangige Warteschlangen, S. 386–390.
• Adam Drozdek. Datenstrukturen und Algorithmen in C ++, Dritte Edition. Thomson Course Technology, 2005. ISBN0-534-49182-0. Kapitel 4: Stapel und Warteschlangen, S. 137–169.

Externe Links

• STL Schnelle Referenz
• VBScript-Implementierung von Stack, Warteschlange, Deque und Rotschwarzbaum