Das Kefk Network Wiki befindet sich im Testbetrieb.
Warteschlange (Datenstruktur)
Aus Kefk.
In der Informatik bezeichnet eine Warteschlange (engl. Queue [kju]) eine häufig eingesetzte spezielle Datenstruktur.
Inhaltsverzeichnis |
Funktionsprinzip
Eine Warteschlange kann 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 Objekt und
- dequeue zum Zurückholen und Entfernen eines Objektes
bereit.
Dabei wird nach dem First In – First Out-Prinzip (deutsch zuerst hinein – zuerst hinaus, kurz FIFO) 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.
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 Queue wird durch das Betriebssystem limitiert.
Graphische Benutzeroberflächen puffern Maus- und Tastaturereignisse in einer sog. „Message Queue“ und teilen sie dann, abhängig von Position und Eingabefocus, den korrekten Prozessen zu.
Implementierung als Ringpuffer
Warteschlangen sind häufig als Ringpuffer mit je einem Zeiger auf Anfang und Ende implementiert. Die Besonderheit des Ringpuffers ist, dass er eine feste Größe besitzt. Dabei werden, wenn der Puffer voll ist, die ältesten Inhalte wieder überschrieben. Wenn zwischenzeitlich nicht genügend Objekte entnommen wurden, kann dies dazu führen, dass sich der Inhalt des Ringpuffers immer nur über einen begrenzten Zeitraum hinweg auslesen lässt. Eine korrekt implementierte Warteschlange sollte daher in diesem Fall entweder einen Pufferüberlauf signalisieren oder zusätzlichen Speicherplatz bereitstellen, es sei denn, dass der Datenverlust akzeptiert werden kann.
Auch die Black-Box im Flugzeug ist in der Regel ein Ringpuffer, sodass bei einem Absturz auch nur die letzten Minuten der aufgezeichneten Messwerte vorhanden sind.
Verwandtschaft mit Stapelspeichern (Stacks)
Warteschlangen lassen sich vorstellen als Bücherstapel, 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 freilich insbesondere Queues interessant.
Siehe auch
 | Dieses Dokument entstammt in seiner ersten oder einer späteren Version der deutschsprachigen Wikipedia. Es ist dort zu finden unter dem Stichwort Warteschlange_%28Datenstruktur%29, die Liste der bisherigen Autoren befindet sich in der Versionsliste; die Originalfassung kann dort auch bearbeitet werden. Alle Texte der Wikipedia und ihre Derivate stehen unter der GNU-Lizenz für freie Dokumentation. |
