Warteschlange (Datenstruktur)

Begriff und Grundprinzip

Eine Warteschlange (englisch queue) ist eine häufig verwendete Datenstruktur in der Informatik. Sie dient als Puffer: Objekte werden vorübergehend gespeichert, bis sie weiterverarbeitet werden. Entscheidend ist, dass die Objekte grundsätzlich in derselben Reihenfolge entnommen werden, in der sie eingefügt wurden.

Wichtige Operationen sind:

• enqueue: fügt ein Objekt am Ende der Warteschlange hinzu.
• dequeue: gibt das vorderste Objekt zurück und entfernt es.

Dabei gilt das Prinzip First In – First Out (FIFO), also „zuerst hinein – zuerst heraus“. Dequeue liefert immer das noch vorhandene Objekt, das zuerst mit enqueue eingefügt wurde. Eine gewöhnliche Warteschlange kann theoretisch beliebig viele Objekte aufnehmen. Eine als Ringpuffer ausgeführte Warteschlange besitzt dagegen eine feste Größe und kann daher überlaufen.

Anschauliches Beispiel

Das FIFO-Prinzip lässt sich mit Kunden an einer Kasse vergleichen: Wer sich zuerst anstellt, wird zuerst bedient. Wer sich zuletzt einreiht, wird zuletzt bedient.

In der dargestellten Beispiel-Queue fügt enter den neuen Wert 3 hinzu. Leave entnimmt das am längsten gespeicherte Element 37. Die ausschließlich lesende Operation front liefert ebenfalls das zuerst gespeicherte Element, entfernt es aber nicht. Im Beispiel ist dies 37, sofern leave zuvor noch nicht ausgeführt wurde.

Typische Anwendungen

Eine wichtige Anwendung von Warteschlangen ist die Interprozesskommunikation, also der Datenaustausch zwischen laufenden Prozessen. Dazu gehört insbesondere die Pipe.

Warteschlangen entkoppeln außerdem langsame externe Geräte von der Ausführung eines Programms. Ein typisches Beispiel ist ein Drucker: Nachdem ein Druckauftrag in die Warteschlange eingestellt wurde, erhält das Programm die Meldung, der Auftrag sei „gedruckt“. Tatsächlich wird er erst ausgeführt, wenn das Gerät verfügbar ist.

In verteilten Systemen dienen Warteschlangen häufig zur Datenübergabe zwischen asynchronen Prozessen. Asynchron bedeutet hier, dass die beteiligten Prozesse nicht gleichzeitig oder mit gleicher Geschwindigkeit arbeiten müssen. Die Daten werden deshalb bis zur Weiterverarbeitung gepuffert. Der Zugriff erfolgt über im Betriebssystem verankerte APIs; die Größe der Warteschlange wird dabei durch das Betriebssystem begrenzt.

Grafische Benutzeroberflächen speichern Maus- und Tastaturereignisse in einer Message Queue. Sie bearbeiten die Ereignisse nach dem FIFO-Prinzip in der Reihenfolge ihres Auftretens und leiten sie abhängig von Position und Eingabefokus an die richtigen Prozesse weiter.

Auch in der parallelen Programmierung kommen Warteschlangen zum Einsatz. Mehrere Bearbeitungsstellen können Aufgaben aus einer gemeinsamen Warteschlange übernehmen und später parallel abarbeiten. Dies ähnelt einer Behörde mit mehreren Schaltern für dieselbe Warteschlange.

Ringpuffer und Verhältnis zum Stack

Warteschlangen werden häufig als Ringpuffer implementiert. Ein Ringpuffer besitzt eine feste Größe und wird durch ein Array sowie zwei Zeiger verwaltet:

• Der In-Pointer zeigt auf das erste freie Element und damit auf die Stelle, an der als Nächstes geschrieben wird.
• Der Out-Pointer zeigt auf das erste belegte und damit als Nächstes zu lesende Element.

Ist der Ringpuffer voll, können beim weiteren Einfügen die ältesten Inhalte überschrieben werden. Eine Implementierung sollte in diesem Fall entweder einen Pufferüberlauf melden oder zusätzlichen Speicher bereitstellen. In bestimmten Anwendungen ist das Überschreiben alter Elemente und der damit verbundene Datenverlust jedoch ausdrücklich erwünscht.

Eine Queue lässt sich auch als Bücherstapel vorstellen, der von unten befüllt wird. Deshalb behandeln manche Implementierungen Stacks und Queues nicht als grundsätzlich verschiedene Strukturen. Ein Stack arbeitet normalerweise nach Last In – First Out (LIFO): Das zuletzt eingefügte Element wird zuerst entnommen. In REXX ist das Leseende einer Queue fest. Mit PUSH eingefügte Einträge werden nach LIFO gelesen, mit QUEUE eingefügte dagegen nach FIFO. Für die Interprozesskommunikation sind insbesondere Queues wichtig.

Umsetzung in C++ und C#

Die Programmierbeispiele verwenden Spielkarten, um die Reihenfolge der Elemente zu zeigen. In C++ stellt die Standardbibliothek die Klasse queue bereit. Eine queue<string> wird nacheinander mit „Herz Dame“, „Karo König“ und „Kreuz Ass“ gefüllt. Die Methode size() liefert zunächst die Länge 3. Front() liest „Herz Dame“ am Anfang, ohne die Karte zu entfernen. Pop() entfernt anschließend dieses erste Element; danach beträgt die Länge 2 und front() liefert „Karo König“.

Eine mögliche eigene C++-Implementierung verwendet eine einfach verkettete Liste. Jedes Element enthält einen Wert und einen Zeiger next auf das folgende Element. Head zeigt auf das vorderste, tail auf das hinterste Element. Push fügt am Ende ein neues Element ein, pop entfernt das vorderste. Front gibt dessen Wert zurück, empty prüft, ob head gleich nullptr ist, und size liefert die gespeicherte Anzahl der Elemente. Konstruktor, Kopierfunktion, Zuweisungsoperator und Destruktor sorgen dafür, dass Elemente kopiert beziehungsweise freigegeben werden.

Das C#-Beispiel definiert eine generische Klasse Queue<T> auf Grundlage einer doppelt verketteten LinkedList<T>. Count() gibt die Zahl der Elemente zurück. Enqueue(T element) fügt mit AddLast ein Element am Ende ein. Dequeue() speichert den Wert des ersten Listenelements, entfernt dieses mit RemoveFirst und gibt den Wert zurück. Die Hauptmethode fügt dieselben drei Karten ein und entnimmt zuerst „Herz Dame“, danach „Karo König“.

Für Karten- und Gesellschaftsspiele, bei denen Karten während des Spiels oben auf einen Stapel gelegt oder von dort gezogen werden, eignen sich statt Warteschlangen Stacks.