In der Informatik ist eine Warteschlange eine besondere Art des abstrakten Datentyps oder der Sammlung, in der die Entitäten in der Sammlung in Ordnung gehalten werden und das Rektor (oder nur), sind Operationen auf der Sammlung die Hinzufügung von Entitäten am Ende Endposition und Eliminierung von Entitäten von der Vorderendposition. Das macht die Warteschlange eine Datenstruktur von First In First Out (FIFO). In einer FIFO Datenstruktur wird das erste zur Warteschlange hinzugefügte Element das erste zu entfernende sein. Das ist zur Voraussetzung gleichwertig, dass sobald ein Element hinzugefügt wird, müssen alle Elemente, die vorher hinzugefügt wurden, entfernt werden, bevor das neue Element angerufen werden kann. Eine Warteschlange ist ein Beispiel einer geradlinigen Datenstruktur.

Warteschlangen stellen Dienstleistungen in der Informatik, dem Transport und der Operationsforschung zur Verfügung, wo verschiedene Entitäten wie Daten, Gegenstände, Personen oder Ereignisse versorgt und gehalten werden, später bearbeitet zu werden. In diesen Zusammenhängen führt die Warteschlange die Funktion eines Puffers durch.

Warteschlangen sind in Computerprogrammen üblich, wo sie als Datenstrukturen durchgeführt werden, die mit Zugriffsroutinen als eine abstrakte Datenstruktur oder auf objektorientierten Sprachen als Klassen verbunden sind. Allgemeine Durchführungen sind kreisförmige Puffer und verbundene Listen.

Das Vertreten einer Warteschlange

In jedem der Fälle, des Kunden oder Gegenstands an der Front der Linie war der erste, um hereinzugehen, während am Ende der Linie das letzte ist, um hereingegangen zu sein. Jedes Mal beendet ein Kunde, für ihre Sachen zu zahlen (oder eine Person steigt aus der Rolltreppe aus, oder der Maschinenteil wird vom Montageband, usw. entfernt), dass Gegenstand die Warteschlange von der Vorderseite verlässt. Das vertritt die Warteschlange "entfernen" Funktion. Jedes Mal, wenn ein anderer Gegenstand oder Kunde in die Linie eingehen, um zu warten, schließen sie sich dem Ende der Linie an und vertreten die "einreihen" Funktion. Die Warteschlange-"Größe"-Funktion würde die Länge der Linie zurückgeben, und die "leere" Funktion würde wahr nur zurückkehren, wenn es nichts in der Linie gäbe.

Warteschlange-Durchführung

Theoretisch ist eine Eigenschaft einer Warteschlange, dass sie keine spezifische Kapazität hat. Unabhängig von wie viel Elemente bereits enthalten werden, kann ein neues Element immer hinzugefügt werden. Es kann auch leer sein, an dem Punkt, der ein Element entfernt, unmöglich sein wird, bis ein neues Element wieder hinzugefügt worden ist.

Feste Länge-Reihe wird in der Kapazität beschränkt und ineffizient, weil Sachen zum Kopf der Warteschlange kopiert werden müssen. Jedoch begrifflich sind sie einfach und arbeiten mit frühen Sprachen wie FORTRAN und GRUNDLEGEND, der Zeigestöcke oder Gegenstände nicht hatte. Am meisten neuere Sprachen mit Gegenständen oder Zeigestöcken können durchführen oder mit Bibliotheken für dynamische Listen kommen. Solche Datenstrukturen können nicht angegeben haben hat Höchstlimit außer Speichereinschränkungen gestellt. Warteschlange-Überschwemmungsergebnisse vom Versuchen, ein Element auf einen vollen Warteschlange- und Warteschlange-Unterlauf hinzuzufügen, geschehen, wenn sie versuchen, ein Element von einer leeren Warteschlange zu entfernen.

Eine begrenzte Warteschlange ist eine auf eine festgelegte Zahl von Sachen beschränkte Warteschlange.

Es gibt mehrere effiziente Durchführungen von FIFO Warteschlangen. Eine effiziente Durchführung ist diejenige, die die Operationen — Aufbau und Abbau — in O (1) Zeit durchführen kann.

• Verbundene Liste
• Eine doppelt verbundene Liste hat O (1) Einfügung und Auswischen an beiden Enden, auch ist eine natürliche Wahl nach Warteschlangen.
• Eine regelmäßige einzeln verbundene Liste hat nur effiziente Einfügung und Auswischen an einem Ende. Jedoch, eine kleine Modifizierung — das Halten eines Zeigestocks zum letzten Knoten zusätzlich zum ersten — wird ihm ermöglichen, eine effiziente Warteschlange durchzuführen.
• Ein deque hat das Verwenden einer modifizierten dynamischen Reihe durchgeführt

Warteschlangen und Programmiersprachen

Einige Sprachen, wie Perl und Ruby, haben bereits Operationen, wegen eine Reihe von beiden Enden zu stoßen und knallen zu lassen, so kann man Stoß verwenden und Funktionen auswechseln, einzureihen und eine Liste zu entfernen (oder, rückwärts kann man Unverschiebung und Knall verwenden), obwohl in einigen Fällen diese Operationen nicht effizient sind.

C ++ 's Standardschablone-Bibliothek stellt "" templated Klasse zur Verfügung, die eingeschränkt wird, um nur Operationen zu stoßen/knallen zu lassen. Seit J2SE5.0 enthält Javas Bibliothek eine Schnittstelle, die Warteschlange-Operationen angibt; durchführende Klassen schließen ein und (seit J2SE 1.6). PHP hat eine Klasse von SplQueue. Die Drittwerkzeuge wie beanstalk'd und Gearman

Siehe auch

• Deque
• Vorzugswarteschlange
• Theorie von Queueing
• Stapel - das "Gegenteil" einer Warteschlange: LIFO (Letzt im Ersten)
• Kreisförmiger Puffer

Allgemeiner

• Donald Knuth. Die Kunst der Computerprogrammierung, Bands 1: Grundsätzliche Algorithmen, die Dritte Ausgabe. Addison-Wesley, 1997. Internationale Standardbuchnummer 0-201-89683-4. Abschnitt 2.2.1: Stapel, Warteschlangen und Deques, Seiten 238-243.
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest und Clifford Stein. Einführung in Algorithmen, die Zweite Ausgabe. MIT Presse und McGraw-Hügel, 2001. Internationale Standardbuchnummer 0-262-03293-7. Abschnitt 10.1: Stapel und Warteschlangen, Seiten 200-204.
• William Ford, William Topp. Datenstrukturen mit C ++ und STL, die Zweite Ausgabe. Prentice Hall, 2002. Internationale Standardbuchnummer 0-13-085850-1. Kapitel 8: Warteschlangen und Vorzugswarteschlangen, Seiten 386-390.
• Adam Drozdek. Datenstrukturen und Algorithmen in C ++, die Dritte Ausgabe. Kurs-Technologie von Thomson, 2005. Internationale Standardbuchnummer 0-534-49182-0. Kapitel 4: Stapel und Warteschlangen, Seiten 137-169.

Links

• STL schnelle Verweisung
• VBScript Durchführung des Stapels, der Warteschlange, deque, und des Rot-schwarzen Baums