Element einfügen - enqueue

Beim Einfügen müssen zwei Fälle unterschieden werden:

Die Schlange ist leer

Die Schlange enthält mindestens ein Element, ist also nicht leer

Fall a) Die Schlange ist leer

Eine Schlange queue ist leer, wenn sowohl ihr Attribut head als auch das Attribut tail auf null zeigen, in diesem Fall gibt es keine Knoten:

(A1) Konstruktor und Methode "isEmpty"

Beginne die Implementation in der Klasse „LinkedQueue“ indem du die fehlenden Attribute und den Konstruktor einfügst/vervollständigst.

Implementiere dann die Methode isEmpty und teste sie mit einer leeren Schlange.

Um nun ein Element in die Schlange einzufügen geht man wie folgt vor:

Zunächst wird ein neuer Knoten erzeugt. Dieser besteht aus dem Inhaltsobjekt und dem Zeiger auf den nächsten Knoten, dieser wird bei der Instanziierung des Knotenobjekts auf null gesetzt.

Dann werden sowohl head als auch tail der Schlange auf diesen Knoten gesetzt - da es nur einen Knoten gibt ist head derselbe Knoten wie tail.

(A2) enqueue für den Fall a)

Füge in der enqeue-Methode folgende Funktionalität ein:

Prüfe, ob die Schlange leer ist - wenn ja:

Erzeuge einen neuen Knoten mit passenden Parametern

Setze head und tail der Schlange passend

Teste deine Methode und überprüfe die Funktionalität mit dem BlueJ-Inspektor.

Fall b) Die Schlange ist nicht leer

Um ein Element an eine nicht leere Schlange anzuhängen geht man folgendermaßen vor:

Zuerst wird wieder ein neuer Knoten erzeugt. Dieser besteht aus dem Inhaltsobjekt und dem Zeiger auf den nächsten Knoten, dieser wird bei der Instanziierung des Knotenobjekts auf null gesetzt.

Dann wird next des Knotens, auf den tail zeigt auf den neuen Knoten gesetzt.

Zum Schluss muss tail ebenfalls auf den neuen Knoten zeigen und entsprechend gesetzt werden.

Das folgende Bild veranschaulicht die Situation: schwarz gestrichelt vor dem anhängen des neuen Knotens, grün danach:

(A3) enqueue für den Fall b)

Füge in der enqeue-Methode im else-Zweig der Abfrage, ob die Schlange leer ist die folgende Funktionalität ein:

Erzeuge einen neuen Knoten mit passenden Parametern

Setze next des bislang letzten Knotens sowie tail der Schlange passend

Teste deine Methode und überprüfe die Funktionalität mit dem BlueJ-Inspektor. Du solltest nun beliebig Elemente an deine Schlange anhängen können.