Aufbau und Funktionsweise
Von außen sieht man der Schlange nur vier Methoden an. Innen besteht sie aus Knoten, die aneinanderhängen: Jeder Knoten hält einen Inhalt und kennt seinen Nachfolger. Die Schlange selbst merkt sich nur zwei Knoten – den vorderen (head) und den hinteren (tail).
Auf dieser Seite schaust du hinein. Als Beispiel dient ein Messenger, der eingehende Nachrichten der Reihe nach anzeigt.
| Teil | Was er sich merkt |
|---|---|
Queue |
head – den vordersten Knoten, tail – den hintersten Knoten |
QueueNode |
content – das gespeicherte Objekt, nextNode – den Knoten dahinter |
Der hinterste Knoten hat keinen Nachfolger: Sein nextNode ist null. Eine leere Schlange erkennt man daran, dass head auf null zeigt.
Im Messenger-Beispiel stehen Nachrichten in der Schlange. Das Klassendiagramm zeigt alle drei beteiligten Klassen, die Pfeile tragen die Namen der Verweise aus den Objektdiagrammen.
classDiagram
direction LR
class Queue {
+isEmpty() boolean
+enqueue(pContent: Message)
+dequeue()
+front() Message
}
class QueueNode {
+QueueNode(pContent: Message)
+getNext() QueueNode
+setNext(pNext: QueueNode)
+getContent() Message
}
class Message {
+getUsername() String
+getText() String
+getDate() String
}
Queue --> QueueNode : head
Queue --> QueueNode : tail
QueueNode --> QueueNode : nextNode
QueueNode --> Message : content
Nachrichten einreihen
Die Methode enqueue soll eine neue Nachricht ans Ende der Warteschlange anhängen.
- Setze die Schritte im Objektdiagramm um.
- Entwirf zur Methode enqueue der Klasse Queue einen Algorithmus in Pseudocode.
- Bereite dich darauf vor, deinen Algorithmus anhand des Objektdiagramms zu präsentieren.
Formulierungshilfe: Pseudocode
- Erzeuge ...
- Setze das Attribut / die Variable ... auf die Referenz ...
Nachrichten lesen und entfernen
Die Methode front soll die erste Nachricht in der Warteschlange zurückgeben. Die Methode dequeue soll die erste Nachricht aus der Warteschlange entfernen.
- Setze die Schritte im Objektdiagramm um.
- Entwirf zu den Methoden dequeue und front einen Algorithmus in Pseudocode.
- Bereite dich darauf vor, deinen Algorithmus anhand des Objektdiagramms zu präsentieren.
Weiterdenken: Was geschieht mit dem Knoten, der gerade entfernt wurde? Niemand verweist mehr auf ihn. Wer räumt ihn weg?
Grenzfälle: die leere Schlange
Bisher stand die Schlange schon voll da. Ein Algorithmus ist aber erst fertig, wenn er auch an den Rändern stimmt: beim ersten Einreihen in eine leere Schlange und beim Entfernen des letzten Knotens.
- Setze beide Schritte im Objektdiagramm um.
- Prüfe deine Algorithmen von oben an diesen beiden Fällen. Wo würden sie scheitern?
- Ergänze deine Algorithmen so, dass sie auch hier stimmen.
Weiterdenken: Warum braucht die Schlange überhaupt einen Verweis auf das Ende? Beschreibe, wie enqueue ohne tail funktionieren müsste und was das bei einer Schlange mit 10 000 Nachrichten bedeutet.