Warteschlange
Warteschlangen in der Informatik
Um das Spiel zu implementieren, benötigen wir eine Möglichkeit die einzelnen Personen auf dem Baumstamm wie in einer Warteschlange zu organisieren. Warteschlangen begegnet man innerhalb und außerhalb der Informatik immer wieder. Eine Warteschlange bietet dabei immer die prinzipiell gleiche Funktionalität:
- Wenn man ein Element einer Warteschlange hinzufügt, dann wird dieses hinten an die Schlange angehängt.
- Wenn man ein Element von einer Warteschlange entfernt, dann wird dieses vorne von der Schlange entfernt.
Man spricht in der Informatik auch vom FIFO-Prinzip (first-in - first-out). Das Element das zuerst in der Warteschlange ist, wird auch zuerst wieder entfernt.
Eine Warteschlange lässt sich z.B. dadurch realisieren, dass die Warteschlange das erste Element kennt, und jedes Element wiederum seinen Nachfolger kennt:
Besonders beachtenswert ist hier, dass eine Person eine andere Person kennt. Man spricht hier von einer rekursiven Beziehung oder reflexiven Beziehung, was im Klassendiagramm besonders deutlich wird:
Klassendiagramm
Eine Warteschlange muss Elemente hinzufügen und entfernen können. Außerdem soll die erste Person zurück gegeben werden können ohne die Warteschlange zu verändern. Das Klassendiagramm hat damit folgende Gestalt:
Aufgabe 1 - Grundgerüst
Erzeuge ein neues BlueJ-Projekt und setze das Klassendiagramm um.
Lasse dabei die Implementierungen der Methoden hinzufuegen
und
entfernen
noch leer. Die Methode gibErstePerson
muss
nur die erste
Person zurückgeben und kann direkt implementiert werden.
(Falls Du Dich mit JUnit und testgetriebener Entwicklung beschäftigt hast,
kannst Du hier auch direkt Testfälle erzeugen)
Hinzufügen von Elementen
Es fehlen noch die Methoden zum Hinzufügen und Entfernen von Elementen. Eine mögliche Idee zum Hinzufügen lautet:
- Wenn die Warteschlange noch leer ist, wird die neue Person als erste Person gespeichert. Das Hinzufügen ist damit beendet.
- Wenn die Warteschlange schon eine Person enthält, dann suche die letzte Person der Warteschlange. Gehe dazu die Warteschlange von Anfang an durch, bis man bei der Person ist, die keinen Nachfolger mehr hat.
- Hänge an die letzte Person eine Person an.
Aufgabe 2 - Hinzufügen
Ordne die dargestellten Codezeilen und ergänze Deine Implementierung. (Hinweis: Hier nicht benötigte Teile der Klasse wurden weggelassen.)
Aufgabe 3 - Testen
Teste Deine Implementierung mit Hilfe des Objektinspektors wie im Screencast dargestellt (Falls Du Testfälle mit JUnit erzeugt hast, kannst Du diese nun einfach ablaufen lassen):
Entfernen des ersten Elements
Falls die Warteschlange kein Element enthält, ist beim Entfernen nichts zu tun. Ansonsten müssen alle Referenzen so "umgebogen" werden, dass das erste Element isoliert wird. Java kümmert sich um Objekte, auf die keine Referenzen mehr zeigen, indem der Garbage Collector diese automatisch aus dem Speicher entfernt.
Gehen wir wieder von folgender Situation aus:
Dann muss der Zustand nach dem Löschen des ersten Elements folgender sein:
Aufgabe 4 - Entfernen
Ergänze die Implementierung zur Methode entfernen
und teste die Methode
wie oben gezeigt mit Hilfe des Objektinspektors.
Tipp: Du benötigst zusätzlich eine lokale Variable.
Aufgabe 5 - Generische Warteschlange (optional)
Falls Du Dich im vorherigen Projekt mit generischen Klassen beschäftigt hast, kannst Du die Warteschlange wie im Fachkonzept zur Warteschlange beschrieben umschreiben. Die Warteschlange lässt sich dann ohne Änderungen in anderen Projekten wiederverwenden.
Aufgabe 6 - Gesamttest
Teste die Warteschlange ausführlich. Du kannst dazu z.B. ein Testprogramm in einer neuen Klasse schreiben oder einfach das Codepad in der folgenden Art benutzen (Falls Du JUnit-Testfälle erzeugt hast, musst Du natürlich nicht mehr per Hand testen):