Für das nächste Kapitel "Breitensuche" brauchen wir eine neue Datenstruktur, die Warteschlange (engl.: Queue). In einer Warteschlange können beliebig viele Elemente nacheinander abgelegt werden. Sie besitzt eine Methode addLast um Elemente am hinteren Ende der Warteschlange anzufügen und eine Methode removeFirst um Elemente am vorderen Ende zu entnehmen.

In der Programmiersprache Java gibt es mehrere Klassen, die die Aufgaben einer Warteschlange erfüllen können, daher sind die Methoden der Warteschlange im Interface Queue definiert, das von mehreren Klassen implementiert wird, insbesondere von der Klasse LinkedList<T>, die wir im Folgenden verwenden. Dabei ist T die Klasse der Objekte, die in der LinkedList gespeichert werden können.

Am folgenden Beispiel, in dem String-Werte zu einer LinkedList hinzugefügt/aus dieser entnommen werden, sehen Sie, wie man diese Datenstruktur verwenden kann: