Warteschlangen (engl. queues) sind Datenstrukturen die auf dem FIFO Prinzip basieren:

Die Objekte die zuerst eingefügt werden, werden auch als erstes wieder ausgelesen. Warteschlangen erhalten die Reihenfolge der Ankunft indem Sie immer nur Objekte am Kopf entnehmen und immer nur Objekte am Ende der Warteschlange einfügen. Typische Operationen auf einer Warteschlange sind:

Wichtig: Warteschlangen bieten keinen wahlfreien Zugriff auf alle ihre Elemente

Warteschlangen sind im realen Leben häufig anzutreffen wenn es sich um Prozesse handelt die alle Beteiligten demokratisch, transparent (fair?) behandeln soll:

• Fließband
• Rolltreppe
• Warten bei vielen Dienstleistern wird als FIFO organisiert

In der Informatik sind Warteschlangen immer dann anzutreffen wenn die Erhaltung einer Ankunftsreihenfolge eine Rolle spielt:

• Datenbanksperren
• Eingehende Webserveranforderungen
• Transaktionales Arbeiten (Sitzplatzreservierung)

Implementierung

Warteschlange sind Spezialfälle von Listen. Im Unterschied zu einer Liste erlauben sie nur das Einfügen von Objekten am Ende und das Entfernen am Kopf der Warteschlange:

Ringpuffer

Warteschlangen die auf einfach oder zweifach verketteten Knoten beruhen sind sehr flexibel. Sie sind jedoch auch ineffizient da bei jedem Aufruf neue Knotenobjekte mit dem aufwendigen new() Operator erzeugt werden müssen.

Dies kann durch die Verwendung von ausreichend großen Ringpuffern vermieden werden, da hier die Knotenobjekte nur einmalig angelegt werden müssen. Diese Ringpuffer werden durch ein Feld R mit einer festen Größe n implementiert. Beim Erreichen des Endes des Feldes wird dieses durch ein Fortsetzen am Beginn des Feldes zum Ring "zusammengebogen".

Hierzu benötigt man:

• einen Zeiger auf das Ende der Warteschlange (im Beispiel R[j])
• einen Zeiger auf den Kopf der Warteschlange (Im Beispiel R[i])

Beim Einfügen und Entfernen von Elementen werden beim Verrücken der Zeiger der Restwert nach der Division durch die Größe des Felds verwendet um nicht einen Feldüberlauf zu Erzeugen. Beim Einfügen eines neuen Elements in den Ringpuffer wird das neue Ende in Java wie folgt berechnet:

ende = (ende-1)%n;

Der Kopf wird nach dem Entfernen eines Elements wie folgt berechnet:

kopf = (kopf-1)%n;

Wichtig: Ringpuffer haben eine feste Größe. Es muss explizit eine Ausnahmebehandlung implementiert werden, wenn die Warteschlange über die Größe n des Feldes wächst.