„He Sie da, hinten anstellen!“ Schlangen sind im Leben leider allgegenwärtig. Damit sind nicht Kriechtiere gemeint, sondern Warteschlangen, in denen das oftmals allzu langsame Vorwärtskommen dann auch einem Kriechen entspricht. Wo immer viele Aufgaben von nur wenigen oder gar nur einem Bearbeiter zu verrichten sind, bilden sich Schlangen.

Da Programme einen Teil der realen Welt modellieren, ist es nicht verwunderlich, dass die Schlange eine der elementaren Datenstrukturen ist, die in sehr vielen Problemstellungen auftaucht.

Eine Schlange (engl. queue) ist eine Datenstruktur, in der Elemente in einer linearen Abfolge gespeichert sind, und bei der das Einfügen eines neuen Elementes immer nur auf einer bestimmten Seite, das Löschen immer nur auf der jeweils anderen Seite der Folge erlaubt ist. Abbildung 2.21 zeigt eine Schlange.

Schlangen sind also Stapeln sehr ähnlich, nur dass hier das Einfügen von Elementen auf der anderen Seite als das Löschen geschieht. Um noch einmal das Beispiel mit den Tellern im Geschirrschrank aus Abschnitt 2.4 zu bemühen: Eine gute Hausfrau stellt Teller immer hinten an. Sie verwendet also eine Schlange, keinen Stapel.

„Wer zuerst kommt, mahlt zuerst!“ Weil Elemente immer auf einer bestimmten Seite eingefügt und auf der anderen herausgenommen werden, ist das erste Element, das in die Struktur eingebracht wurde, auch immer das erste, das wieder herausgeholt wird. Man sagt daher, dass Schlangen nach dem FIFO-Prinzip („first in first out“) arbeiten.

Das Element, das als nächstes gelöscht werden wird, wird als Kopf (engl. head) der Schlange bezeichnet, das Element am anderen Ende als Schwanz (engl. tail). Um mit den Bezeichnungen bei Stapeln konsistent zu bleiben, wird in LEDA der Kopf ebenfalls als Top bezeichnet, und das Herausnehmen ebenfalls als Pop. Um den Unterschied zu Stapeln klarzumachen, wird das Einfügen als Append bezeichnet, nicht als Push.

LEDA bietet als Implementierung für Schlangen die Klassen queue und b_queue an. Bei ersterer handelt es sich um Schlangen, die beliebig viele Elemente speichern können. Zweitere ist dann besonders nützlich, wenn wir im Voraus wissen, dass nur eine bestimmte, begrenzte Anzahl von Elementen jemals in die Schlange aufgenommen werden („bounded queue“).

An dieser Stelle stellt sich dieselbe Frage wie bei der Einführung von Stapeln: Warum sollen wir Schlangen benutzen, wenn wir doch mit dem Typ list alles machen können? Die in Abschnitt “Wozu überhaupt einen Stapel benutzen?” gegebenen Antworten gelten hier ebenfalls.

Schauen wir uns also Warteschlangen in einer typischen Situation an.