inf-schule | Platz da! » Warteschlange

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:

Objektdiagramm zur Warteschlange von Personen

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:

Warteschlange als rekursive Datenstruktur

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 (kein UML sondern Java-spezifisch):

Klassendiagramm zur Warteschlange

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)

class Warteschlange {
Person erste;
void hinzufuegen(Person p){
}
void entfernen(){
}
Person gibErstePerson(){
return erste;
}
}
class Person {
String name;
Person naechste;
Person(String n) {
name = n;
}
}

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.)

class Warteschlange {
Person erste;
void hinzufuegen(Person p){
if (erste == null) {
erste = p;
}
else {
Person letzte = erste;
while(letzte.naechste != null)
letzte = letzte.naechste;
letzte.naechste = p;
}
}
}

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:

Objektdiagramm zur Warteschlange von Personen

Dann muss der Zustand nach dem Löschen des ersten Elements folgender sein:

Objektdiagramm nach dem Löschen

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.

void entfernen(){
if (erste != null) {
Person alteErste = erste;
erste = erste.naechste;
alteErste.naechste = null;
}
}

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):

Testen der Warteschlange im Codepad