Vorüberlegungen
Die Struktur einer Warteschlange
Stellen wir uns eine Warteschlange an einer Supermarktkasse vor. Hat man Glück, so ist die Schlange leer und man kann sich als Erster dort anstellen:
Für gewöhnlich bleibt man dort aber nicht lange allein, sondern ein weiterer Wartender erscheint. Dieser stellt sich hinter uns, so dass man klar erkennen kann, dass er in der Warteschlange unser Nachfolger ist. Zum einen weiß dadurch der Kassierer, dass wir zuerst an der Reihe sind und wir selber registrieren, dass der neue Wartende nach uns an der Reihe sein wird. D.h. sollte jemand den Kassierer fragen, wer nun an der Reihe ist, wird er sicher auf uns deuten und wenn uns jemand fragen sollte, wer nach uns dran kommt, könnten wir einfach mit dem Finger auf unseren Nachfolger deuten:
Sollte es an der Kasse nicht allzu schnell voran gehen, so werden noch weitere Wartende in der Schlange erscheinen:
Immer noch ist es so, dass jeder Wartende in der Schlange genau weiß, wer nach ihm an der Reihe sein wird. Nur der Letzte in der Schlange weiß dies natürlich nicht. Würde man ihn nach seinem Nachfolger fragen, so müsste er ins Leere zeigen.
Eine Möglichkeit, die Struktur in dieser Warteschlange zu beschreiben, ist folgende: Ein Wartender ist der Erste und jeder Wartende kennt seinen Nachfolger, sofern er einen hat.
Einfügen neuer Elemente
Wie man sich in einer Warteschlange einzureihen hat, wird jeder wissen. Manchmal allerdings muss man vielleicht einen Moment suchen, um das Ende der Schlange zu finden. Zum Beispiel, wenn in einer Bäckerei aus Platzgründen die Leute nicht in einer Reihe stehen.
In dem Fall kann man sich durchfragen, bis man das Ende der Schlange, d.h. den bisher letzten Wartenden, gefunden hat. Und falls man nicht so recht weiß, wen man als erstes fragen soll, wo das Ende ist, dann fragt man einfach zuerst die Person, die gerade an der Kasse steht, wer denn ihr Nachfolger ist und arbeitet sich so einmal ganz durch die Schlange durch.
Dieses Vorgehen ist nicht das geschickteste. Der aufmerksame Leser kann ja schon einmal im Hinterkopf überlegen, warum es nicht so elegant ist und wie man es besser machen könnte 🙂
Entfernen des ersten Elementes
Wenn wir beim Bild der Supermarktkasse bleiben, dann wird dort ein Wartender (im Idealfall) die Schlange deswegen verlassen, weil er bezahlt hat. Das bedeutet insbesondere, dass nur der erste Wartende die Schlange verlässt und nicht irgendjemand, der mittendrin steht. Danach rutschen alle ein Stück auf und der bisher zweite Wartende – also der bisherige Nachfolger vom Ersten – ist nun der neue Erste in der Schlange.
Mit diesen grundlegenden Eigenschaften wollen wir uns für den Moment zufrieden geben. Nun machen wir uns Gedanken darüber, wie man eine solche Warteschlange mittels Java umsetzen könnte.
Umsetzung in Java
Darstellung mittels eines Entwurfsdiagramms
Zunächst beginnen wir damit, eine Warteschlange in einem geeigneten Diagramm darzustellen. Dieses ist im Wesentlichen eine schematische Darstellung der Situation an der Kasse:
Wie man anhand des Diagramms schon erahnen kann, passiert hier etwas für uns Neues: Wir betrachten Objekte einer Klasse Wartender die als Attribut wiederum Objekte dieser Klasse besitzen. Die Pfeile zwischen den Wartenden zeigen an, dass das Attribut nachfolger tatsächlich auf den Nachfolger in der Schlange zeigt. Ganz links gibt es noch einen Pfeil vom Kassierer auf den Ersten in der Schlange. Auf diese Weise wollen wir den Beginn der Schlange markieren.
Hervorzuheben ist noch der letzte Pfeil. Dieser zeigt auf ein Objekt mit Namen null. Das bedeutet, er zeigt ins Leere. In vielen Programmiersprachen, und so auch in Java, ist null nämlich die Bezeichnung für ein leeres oder nicht vorhandenes Objekt.
Damit wir die Wartenden unterscheiden können, um so bei späteren Testläufen feststellen zu können, ob wir alles richtig gemacht haben, fügen wir der Klasse Wartender noch ein Attribut name vom Typ String hinzu und kommen zu einem ersten Entwurf.
Entwurf der Klasse Wartender
Wie im Diagramm schon ersichtlich, besitzt die Klasse Wartender die beiden Attribute nachfolger und name. Wir beginnen mit der Implementierung also wie folgt:
public class Wartender {
// Attribute
private String name;
private Wartender nachfolger;
// Konstruktor
public Wartender (String pName){
name = pName;
nachfolger = null;
}
// get-Methoden
public String getName(){
return name;
}
public Wartender getNachfolger(){
return nachfolger;
}
}
Solange wir einem Wartenden keinen Nachfolger zuweisen können, ist das Attribut nachfolger noch recht unnütz. Also fügen wir eine entsprechende Methode hinzu:
public void setNachfolger(Wartender pNachfolger){
nachfolger = pNachfolger;
}
Sehen wir uns einen kleinen Testauf an:
public class WarteschlangenTest {
public static void main(String[] args) {
Wartender erster = new Wartender("Anton");
erster.setNachfolger(new Wartender("Berta"));
}
}
In diesem Beispiel gibt es zwei Objekte der Klasse Wartender. Ungewohnt ist aber, dass das zweite Objekt, also Berta nur als Nachfolger von Anton wiederzufinden ist. Es gibt keine Variable, unter der es abgelegt wurde.
Möchten wir also die beiden Namen Berta einmal anzeigen lassen, geht das nur so:
public class WarteschlangenTest {
public static void main(String[] args) {
Wartender erster = new Wartender("Anton");
erster.setNachfolger(new Wartender("Berta"));
System.out.println(erster.getName());
System.out.println(erster.getNachfolger().getName());
}
}
Das Klassendiagramm der Klasse Wartender sieht auch etwas ungewöhnlich aus:
Hier liegt eine Assoziation der Klasse Wartender mit sich selbst vor, da der Nachfolger eines Wartenden eben wieder ein Wartender ist.
Die Klasse Wartender ist nun fertiggestellt. Jetzt widmen wir uns der Gesamtstruktur, d.h. wir entwerfen nun eine Klasse Warteschlange.
Erster Entwurf
Es mag überraschen, dass unsere Warteschlange nur ein einziges Attribut besitzt:
public class Warteschlange {
// Attribut
private Wartender kassierer;
// Konstruktor
public Warteschlange (){
kassierer = new Wartender("Kassierer");
}
}
Der Kassierer wird hier auch als Objekt der Klasse Wartender modelliert. Das ist ein kleiner Trick: Man nutzt hier aus, dass der Kassierer auf den Ersten in der Schlange zeigt, sobald er erscheint. Er verhält sich also im Grunde genau wie die anderen Wartenden. Daher verändern wir unser Diagramm wie folgt:
Es ist alternativ auch möglich, den Kassierer in der Umsetzung der Warteschlange wegzulassen. Meiner Erfahrung nach ist eine erste Umsetzung mit Kassierer aber recht gut nachvollziehbar, so dass ich bei dieser bleiben möchte.
Nun kommen wir zu einem der entscheidenden Punkte in der Implementierung. Wir müssen es ermöglichen, den Letzten in der Schlange zu finden, damit man hinter diesen einen neuen Wartenden einreihen kann.
Um das Prinzip zu verbildlichen, stellen wir uns wieder vor, dass wir uns durch die ganze Schlange durchfragen müssen, um den letzten Wartenden zu finden. Während wir dies tun, zeigen wir immer mit einem Finger (das ist der Laufzeiger) auf denjenigen, den wir gerade gefragt haben, ob er der Letzte in der Schlange ist.Wie oben schon erwähnt, geht es geschickter. Aber es hat seinen Grund, warum ich den Laufzeiger ins Spiel bringe 😉
Wir beginnen damit, den Kassierer zu fragen, wer als Nächster an der Reihe ist. Im Diagramm würde man unsere erste Frage so darstellen:
Unsere Frage muss ganz konkret lauten: Ist Dein Nachfolger null? Ist die Antwort ja, dann steht noch niemand in der Schlange. Ist sie nein, dann müssen wir uns an den Nachfolger wenden:
Wieder fragen wir: Ist Dein Nachfolger null? und reagieren entsprechend. Auf diese Weise wandern wir von einem Wartenden zum Nächsten.
Ist der Nachfolger tatsächlich null, so beenden wir das Fragen und stellen fest, dass wir auf den Letzten zeigen.
Eine mögliche Implementierung sieht so aus:
private Wartender getLetzter(){
// Der Lauzeiger wird erschaffen.
// Er zeigt zuerst auf den Kassierer.
Wartender laufzeiger = kassierer;
// Nun wird gefragt.
while(laufzeiger.getNachfolger()!=null){
laufzeiger = laufzeiger.getNachfolger();
}
// Ist der Letzte gefunden, wird er
// bekannt gegeben.
return laufzeiger;
}
Beachte, dass diese Methode privat ist, da man von außen nur Zugriff auf den Ersten haben soll.
Mithilfe dieser Methode ist es nun recht leicht, einen neuen Wartenden anzustellen! Wir schnappen uns einfach den Letzten und teilen ihm mit, dass er nun auch einen Nachfolger erhält:
public void stelleAn(Wartender pNeuer) {
getLetzter().setNachfolger(pNeuer);
}
Da in einer Warteschlange ja immer der Erste bedient wird, sollten wir auch eine Methode ergänzen mit der man erfährt wer denn der Erste ist:
public Wartender getErster() {
return kassierer.getNachfolger();
}
Es könnte auch praktisch sein, prüfen zu können, ob die Schlange leer ist:
public boolean istLeer() {
return (kassierer.getNachfolger() == null);
}
Schließlich kommen wir noch zum Entfernen des ersten in der Schlange. Hier schauen wir uns direkt zwei Wege an, dies umzusetzen.
Der erste besteht darin, dass wir dem Kassierer mitteilen, dass ab nun der Nachfolger des bisherigen Ersten der neue Erste sein soll. Den Nachfolger des Ersten finden wir mit kassierer.getNachfolger().getNachfolger().
Aber Vorsicht! Wenn die Schlange leer ist, ist kassierer.getNachfolger() ja null. In diesem Fall würde kassierer.getNachfolger().getNachfolger() zu einer Nullpointer Exception führen, da wir von einem Objekt, das es gar nicht gibt, verlangen, den Nachfolger anzugeben. Das können wir aber leicht mit einer if-Abfrage umgehen:
public void entferneErsten() {
if (istLeer() == false) {
kassierer.setNachfolger(kassierer.getNachfolger().getNachfolger());
}
}
Ein anderer Weg besteht darin, den bisher Ersten in der Schlange zum neuen Kassierer zu machen. Der bisherige Kassierer verschwindet dann einfach:
public void entferneErsten() {
if (istLeer() == false) {
kassierer = kassierer.getNachfolger();
}
}
Hier sollte man schon merken: Oftmals gibt es verschiedene Wege, eine Datenstruktur zu Implementieren!
Sehen wir uns zur Übersicht einmal die komplette Klasse an:
public class Warteschlange {
private Wartender kassierer;
public Warteschlange() {
kassierer = new Wartender("Kassierer");
}
// Nicht elegante Variante dieser Methode!
private Wartender getLetzter() {
Wartender laufzeiger = kassierer;
while (laufzeiger.getNachfolger() != null) {
laufzeiger = laufzeiger.getNachfolger();
}
return laufzeiger;
}
public Wartender getErster() {
return kassierer.getNachfolger();
}
public void stelleAn(Wartender pNeuer) {
getLetzter().setNachfolger(pNeuer);
}
public void entferneErsten() {
if (istLeer() == false) {
kassierer = kassierer.getNachfolger();
}
}
public boolean istLeer() {
return (kassierer.getNachfolger() == null);
}
}
Hier haben wir ein Beispiel dafür, wie sie im Einsatz aussieht:
public class WarteschlangenTest {
public static void main(String[] args) {
Warteschlange meineSchlange = new Warteschlange();
meineSchlange.stelleAn(new Wartender ("Anton"));
meineSchlange.stelleAn(new Wartender ("Berta"));
meineSchlange.stelleAn(new Wartender ("Caesar"));
while(meineSchlange.istLeer()==false){
System.out.println(meineSchlange.getErster().getName());
meineSchlange.entferneErsten();
}
}
}
Als Ausgabe erhalten wir hier tatsächlich die drei Namen der Wartenden.
Überarbeitung der Methode getLetzter()
Bereits oben wurde schon erwähnt, dass die Methode getLetzter() recht ungeschickt implementiert wurde. Aber was genau ist daran so ungeschickt?
Das Problem ist, dass sie sehr ineffizient ist. Je länger die Schlange ist, desto länger benötigt die Methode, um vom Kassierer aus bis zum Letzten zu laufen. So etwas kann ein Programm unnötig bremsen.
Eine bessere Idee ist es, nicht nur den Kassierer zu markieren, sondern auch immer den Letzten:
Wir können uns vorstellen, dass der Letzte immer ein Schild in der Hand hat, woran ein Neuer ihn erkennen kann.
Möchten wir so einen neuen Wartenden anstellen, gehen wir wie folgt vor:
- Wir finden sofort den Letzten und teilen ihm mit, dass er den neuen als Nachfolger hat.
- Wir verschieben den Pfeil letzter auf den nun neuen Letzten.
In Java können wir dies so erreichen:
public class Warteschlange {
private Wartender kassierer;
private Wartender letzter;
public Warteschlange() {
kassierer = new Wartender("Kassierer");
}
public Wartender getLetzter() {
return letzter;
}
public Wartender getErster() {
return kassierer.getNachfolger();
}
public void stelleAn(Wartender pNeuer) {
if (istLeer()) {
kassierer.setNachfolger(pNeuer);
letzter = kassierer.getNachfolger();
} else {
getLetzter().setNachfolger(pNeuer);
letzter = letzter.getNachfolger();
}
}
public void entferneErsten() {
if (istLeer() == false) {
kassierer = kassierer.getNachfolger();
}
}
public boolean istLeer() {
return (kassierer.getNachfolger() == null);
}
}
Es ist eine Fallunterscheidung nötig, da der Fall, dass sich jemand an eine leere Schlange stellt, gesondert behandelt werden muss.
Ausblick
So wie wir nun die Methode getLetzter() verbessert haben, könnte man sich noch vornehmen, die Implementierung noch weiter zu optimieren, indem man sich den Kassierer und tatsächlich nur die „echten“ Wartenden speichert. Dies möchte ich aber gerne als Übung so im Raum stehen lassen.
Anstatt also diese Änderung im Folgenden zu betrachten, werden wir eine allgemeine Klasse Queue entwerfen, mit der man Objekte einer beliebigen Klasse in einer Schlange aneinander reihen kann.