Dies ist eine alte Version des Dokuments!
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
Fall a) Die Schlange enthält mindestens zwei Elemente
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.
Fall b) Die Schlange enthält nur ein Element
In diesem Fall wird der letzte Knoten entfernt, die Schlange ist anschließend also leer. Man muss head
und tail
auf null
setzen.
(A1) deqeue
Implementiere die Methode deqeue
entsprechen der obigen Erläuterungen mit einer passenden Fallunterscheidung und teste Sie manuell.