Warteschlange (Datenstruktur) - LinkFang.de





Warteschlange (Datenstruktur)


In der Informatik bezeichnet eine Warteschlange (englisch queue [kju]) eine häufig eingesetzte Datenstruktur. Sie dient zur Zwischenspeicherung von Objekten in einer Reihenfolge, bevor diese weiterverarbeitet werden.

Funktionsprinzip

Eine Warteschlange kann, im Gegensatz zum später beschriebenen Ringpuffer, eine beliebige Menge von Objekten aufnehmen und gibt diese in der Reihenfolge ihres Einfügens wieder zurück. Dazu stellen Warteschlangen die Operationen

  • enqueue zum Hinzufügen eines Objekts und
  • dequeue zum Zurückholen und Entfernen eines Objektes bereit.
  • während die Warteschlange (per Axiom) unendlich viele Objekte aufnimmt, kann beim Ringpuffer bei Erschöpfung ein Überlauf eintreten, für den eine Bearbeitung vereinbart werden muss, siehe auch unten.

Dabei wird nach dem First In – First Out-Prinzip, kurz FIFO (deutsch zuerst hinein – zuerst heraus) gearbeitet, das heißt, es wird von dequeue immer das Objekt aus der Warteschlange zurückgegeben, welches von den in der Warteschlange noch vorhandenen Objekten als erstes mit enqueue hineingelegt wurde.

Illustration

Man kann sich eine Warteschlange wie eine Warteschlange von Kunden an einer Kasse vorstellen. Der Letzte, der sich in die Schlange stellt, wird auch als letzter bedient. Umgekehrt wird derjenige, der sich als erstes angestellt hat, als erster bedient.

Mit enter wird ein neuer Wert (3) der Schlange hinzugefügt, und mit leave das am längsten gespeicherte Element (37) herausgenommen. Der einzige lesende Zugriff erfolgt mit front [math]\to[/math] und liefert das erste gespeicherte Element der Queue (hier im Beispiel 37, natürlich unter der Annahme, dass die Operation leave noch nicht ausgeführt wurde!).

Anwendung

Die zur Interprozesskommunikation verwendete Pipe ist eine der wichtigsten Anwendungen für Warteschlangen.

Durch Warteschlangen werden auch langsame externe Geräte, z. B. Drucker, von der Programmabarbeitung entkoppelt. Nach dem Einstellen eines Druckauftrages in die Warteschlange wird dem Programm der Auftrag als „gedruckt“ signalisiert, tatsächlich wird der Auftrag jedoch erst später bei Verfügbarkeit des Gerätes ausgeführt.

Warteschlangen werden außerdem häufig zur Datenübergabe zwischen asynchronen Prozessen in verteilten Systemen verwendet, wenn also Daten vor ihrer Weiterverarbeitung gepuffert werden müssen. Der Zugriff erfolgt dabei durch im Betriebssystem verankerte APIs. Die Größe der Warteschlange wird durch das Betriebssystem limitiert.

Graphische Benutzeroberflächen puffern Maus- und Tastaturereignisse in einer sogenannten „Message Queue“ nach dem FIFO-Prinzip, d. h. in der Reihenfolge ihres Auftretens. Anschließend leiten sie diese dann, abhängig von Position und Eingabefokus, an die korrekten Prozesse weiter.

Eine Warteschlange kann auch zum Parallelisieren verwendet werden. Dies kann man sich wie bei einem Postamt vorstellen, bei dem es mehrere Schalter für eine Warteschlange gibt. So können Aufgaben eingestellt werden, die später parallel abgearbeitet werden.

Implementierung als Ringpuffer

Warteschlangen sind häufig als Ringpuffer mit je einem Zeiger auf Anfang (In-Pointer) und Ende (Out-Pointer) implementiert. Die Besonderheit des Ringpuffers ist, dass er eine feste Größe besitzt. Dabei zeigt der In-Pointer auf das erste freie Element im Array, das den Ringpuffer repräsentiert, und der Out-Pointer auf das erste belegte Element in dem Array. Im Unterschied zum Array werden die ältesten Inhalte überschrieben, wenn der Puffer voll ist und weitere Elemente in den Ringpuffer abgelegt werden. Eine Implementierung des Ringpuffers sollte für den Fall, dass der Ringpuffer voll ist, entweder einen Pufferüberlauf signalisieren oder zusätzlichen Speicherplatz bereitstellen. In anderen Fällen kann das Überschreiben alter Elemente der Warteschlange und damit der Datenverlust gewollt sein.

Auch der Flugschreiber im Flugzeug ist in der Regel ein Ringpuffer, sodass bei einem Absturz in jedem Fall die letzten Minuten der aufgezeichneten Messwerte vorhanden sind.

Verwandtschaft mit Stapelspeichern (Stacks)

Warteschlangen kann man sich als Bücherstapel vorstellen, die von unten befüllt werden; dementsprechend gibt es Implementierungen, die gar keinen prinzipiellen Unterschied zwischen Stacks und Queues machen. In REXX steht das Leseende einer Queue fest; mit PUSH abgelegte Einträge werden nach dem LIFO-Prinzip gelesen (Last In – First Out), mit QUEUE abgelegte nach dem FIFO-Prinzip. Zur Interprozesskommunikation sind insbesondere Queues interessant.

Siehe auch


Kategorien: Datenstruktur

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Warteschlange (Datenstruktur) (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.