Element entfernen (dequeue)

Auch beim Entfernen eines Elementes am Anfang der Schlange sind mehrere Fälle zu unterscheiden:

• Die Schlange ereilt mindestens zwei Elemente
• Die Schlange enthält nur ein Element
• Der triviale Fall: Wenn die Schlange leer ist nichts zu tun

Wenn die beiden Attribute head und tail auf unterschiedliche Objekte verveisen (head != tail) kann man sicher sein, dass zwei oder mehr Elemente in der Schlange gespeichert sind. Um entsprechend dem FIFO-Prinzip das erste Element zu löschen geht man wie folgt vor:

Man setzt einfach das Attribut head auf den Knoten, auf den im bisherigen head als next verwiesen wurde. damit "hängt" das erste Element gewissermaßen in der Luft, es gibt keinen Verweis mehr auf den zugehörigen Knoten. Diese wird vom "garbage collector" der Java Laufzeitumgebung beseitigt.

In diesem Fall wird der letzte Knoten entfernt, die Schlange ist anschließend also leer. Man muss head und tail auf null setzen.

In der Regel gibt man das erste Element der Schlange aus, bevor man es entfernt. Das geschieht mit der Methode front. Die deqeue-Methode gibt also den Inhalt des Knotenobjekts zurück, welches sie anschießend entfernt. Den Inhalt erhält deqeue durch Aufruf von front. In front sollte überprüft werden, ob die Schlange leer ist.

Implementiere die Methoden front und deqeue entsprechen der obigen Erläuterungen.