Motivation
In unserer Einführung zu Warteschlangen haben wir Objekte einer Klasse Wartender aneinandergereiht. Um dies zu ermöglichen, brauchte die Klasse Wartender ein Attribut nachfolger.
Was aber könnten wir tun, wenn wir andere Objekte in einer Schlange aufreihen wollen – beispielsweise Autos, die vor einer Schranke warten. Müssen wir dann einer vielleicht schon vorhandenen Klasse Auto ebenfalls ein Attribut nachfolger hinzufügen? Das wäre doch etwas umständlich.
Außerdem konnte unsere Warteschlange nur Wartende aufnehmen, keine anderen Objekte. Müssen wir diese Warteschlange also etwa jedes Mal anpassen?
Natürlich ist beides nicht nötig. Stattdessen werden wir eine Klasse Queue entwickeln, in der man – ähnlich wie bei Arrays – Objekte einer beliebigen aber vorher festgelegten Klasse ablegen kann.
Objekte in Knoten ablegen
Möchten wir Objekte einer vollkommen beliebigen Klasse (z.B. Auto) in einer Schlange aneinanderreihen, müssen wir es ermöglichen, einem Objekt ein nachfolgendes Objekt zuzuordnen. Allerdings müssen wir davon ausgehen, dass die Klasse kein Attribut besitzt, das für diesen Zweck vorgesehen ist.
Dieses Problem lösen wir, indem wir die Objekte, die wir aufreihen wollen, in sogenannte Knoten ablegen. Diese Knoten besitzen ein Attribut naechster, mit dem der Nachfolger festgelegt werden kann.
Unser erster Schritt besteht also nun darin, die Klasse Knoten zu entwerfen.
Wie wir in der Abbildung sehen, muss ein Knoten zwei Attribute besitzen:
- Ein Attribut der Klasse Knoten, mit dem der Nachfolger festgelegt werden kann.
- Ein Attribut, das auf den eigentlichen Inhalt verweist, also auf das Objekt, das wir eigentlich in der Schlange anstellen wollen.
Von welcher Klasse muss das zweite Attribut sein?
Da wir im Allgemeinen nicht wissen, von welcher Klasse der Inhalt sein wird, geben wir an, dass er von der Klasse Object ist. Dies ist die allgemeinste Klasse in Java, d.h., jede Klasse ist eine Spezialisierung der Oberklasse Object!
Schauen wir uns eine mögliche Implementierung einer Klasse Knoten an:
public class Knoten {
private Object inhalt;
private Knoten naechster;
public Knoten(Object pInhalt) {
inhalt = pInhalt;
naechster = null;
}
public Knoten getNaechster() {
return naechster;
}
public Object getInhalt() {
return inhalt;
}
public void setNaechster(Knoten pNaechster) {
naechster = pNaechster;
}
}
Um ein „Gefühl“ für diese Klasse zu bekommen, sehen wir uns eine Anwendung an. Dazu brauchen wir aber noch eine Klasse, um Objekt zu erzeugen.
Nehmen wir dazu diese:
public class Auto {
private String farbe;
private int leistung;
public Auto(String pFarbe, int pLeistung) {
farbe = pFarbe;
leistung = pLeistung;
}
public String getFarbe() {
return farbe;
}
public int getLeistung() {
return leistung;
}
public void schreibeInfos() {
System.out.println("Farbe: " + farbe);
System.out.println("Leistung: " + leistung);
}
}
Nun legen wir zwei Autos in Knoten ab und hängen einen an den anderen:
public class KnotenTest {
public static void main(String[] args) {
Knoten meinErsterKnoten = new Knoten(new Auto("Rot", 60));
meinErsterKnoten.setNaechster(new Knoten(new Auto("Blau", 100)));
}
}
Das rote Auto wurde sofort als Inhaltsobjekt des ersten Knotens angegeben.
Das blaue Auto wurde sofort als Inhaltsobjekt des zweiten Knotens angegeben. Dieser wiederum wurde sofort als Nachfolger vom ersten Knoten festgelegt.
Nun möchten wir vielleicht die Methode schreibeInfos() des ersten Autos aufrufen, um zu testen, ob alles geklappt hat. Hier taucht aber eine kleine Schwierigkeit auf:
public class KnotenTest {
public static void main(String[] args) {
Knoten meinErsterKnoten = new Knoten(new Auto("Rot", 60));
meinErsterKnoten.setNaechster(new Knoten(new Auto("Blau", 100)));
meinErsterKnoten.getInhalt().schreibeInfos(); // Fehler!
}
}
Warum können wir die Methode so nicht aufrufen?
Das Problem ist, dass die Methode getInhalt() der Klasse Knoten ein Objekt der Klasse Object liefert. Die Klasse Object besitzt nämlich keine Methode namens schreibeInfos().
In diesem konkreten Fall wissen wir aber, dass in dem Knoten ein Objekt der Klasse Auto liegt. Daher können wir Java die Garantie geben, dass die Methode schreibeInfos() einen Artikel liefert. Man sagt, dass wir das Objekt explizit casten also explizit in ein Objekt der Klasse Auto umwandeln:
public class KnotenTest {
public static void main(String[] args) {
Knoten meinErsterKnoten = new Knoten(new Auto("Rot", 60));
meinErsterKnoten.setNaechster(new Knoten(new Auto("Blau", 100)));
((Auto) meinErsterKnoten.getInhalt()).schreibeInfos();
}
}
Achtung! Hätten wir einen Fehler gemacht haben und es befände sich doch ein Objekt einer anderen Klasse in dem Knoten, so würde dies zu einem Laufzeitfehler führen.
An das blaue Auto kommen wir nur auf den Weg über den ersten zum zweiten Knoten heran, zum Beispiel so:
public class KnotenTest {
public static void main(String[] args) {
Knoten meinErsterKnoten = new Knoten(new Auto("Rot", 60));
meinErsterKnoten.setNaechster(new Knoten(new Auto("Blau", 100)));
((Auto) meinErsterKnoten.getInhalt()).schreibeInfos();
Auto zweitesAuto = (Auto) meinErsterKnoten.getNaechster().getInhalt();
zweitesAuto.schreibeInfos();
}
}
Nachdem wir nun einen ersten Eindruck der Klasse Knoten bekommen haben, verwenden wir sie, um eine Klasse Queue zu erstellen.
Implementierung einer Queue
Bei Queues gibt es einige Standardmethoden und Bezeichnungen, an die wir uns auch halten werden:
| Queue() | Es wird eine leere Queue erstellt. |
| void enqueue(Object pInhalt) | Hängt einen neuen Knoten mit dem Inhalt pInhalt an die Queue, sofern pInhalt nicht null ist. Andernfalls passier gar nichts. |
| void dequeue() | Entfernt den ersten Knoten, sofern es einen gibt. Ist die Queue leer, so geschieht nichts. |
| Object front() | Liefert das Inhaltsobjekt des ersten Knotens, sofern die Queue nicht leer ist. Andernfalls wird null geliefert. |
| boolean isEmpty() | Dies liefert den Wert true, wenn die Queue leer ist. Andernfalls wird der Wert false zurückgegeben. |
Bei der Implementierung gehen wir anders vor als im Einstieg. Dort gab es noch das „Dummy-“Objekt kassierer, das immer in der Schlange vorhanden war. Dieses Mal verzichten wir auf ein solches Objekt. Eine leere Queue besitzt also gar keinen Knoten. Enthält eine Queue genau ein Objekt, dann ist ihr sogenannter Kopf (in der Literatur oft „head“) auch gleichzeitig das Ende („tail“):
public class Queue {
private Knoten kopf;
private Knoten ende;
public Queue() {
kopf = null;
ende = null;
}
public void enqueue(Object pInhalt) {
if (pInhalt != null) {
if (isEmpty()) {
kopf = new Knoten(pInhalt);
ende = kopf;
} else {
ende.setNaechster(new Knoten(pInhalt));
ende = ende.getNaechster();
}
}
}
public void dequeue() {
if (!isEmpty()) {
if (ende == kopf) { // nur ein Knoten vorhanden
kopf = null;
ende = null;
} else { // mehrere Knoten vorhanden
kopf = kopf.getNaechster();
}
}
}
public Object front() {
if (!isEmpty()) {
return kopf.getInhalt();
} else {
return null;
}
}
public boolean isEmpty() {
return kopf == null;
}
}
Betrachten wir die Methoden im Einzelnen:
Im Konstruktor wird eine leere Queue erstellt, so dass sowohl kopf als auch ende auf null zeigen.
In der Methode enqueue() wird zunächst geprüft, ob pInhalt nicht null ist, denn wenn dem so wäre, soll gar nichts passieren.
Ist pInhalt nicht null, so muss ein neuer Knoten angehängt werden. Hier wird geprüft mit if (isEmpty()), ob die Schlange leer ist, da dies ein Sonderfall ist. In diesem Fall muss nämlich kopf auf einen neuen Knoten zeigen, in dem der neue Inhalt abgelegt wird. Der Zeiger ende muss auf denselben Knoten zeigen (siehe auch die Abbildung oben).
Ist die Schlange nicht leer, wird der neue Knoten an den letzten Knoten gehängt und der Zeiger ende wird dem neuen Knoten zugewiesen.
In der Methode dequeue() prüfen wir, ob die Schlange nicht leer ist, denn dann wäre nichts zu tun.
Danach behandeln wir zunächst den Fall, dass nur ein Knoten vorhanden ist. Dieser wird entfernt, indem einfach kopf und ende das leere Objekt null zugewiesen wird.
Andernfalls müssen noch mehr Knoten vorhanden sein und wir können einfach kopf eins weiter „nach rechts“ verschieben.
Die Methode front() prüft, ob die Schlange nicht leer ist. Ist sie nicht leer, kann der Inhalt von kopf zurückgegeben werden. Ansonsten muss null geliefert werden.
Die Methode isEmpty() ist sehr kompakt. Hier nutzen wir aus, dass die Queue genau dann leer ist, wenn kopf == null gilt. Man könnte auch eine if-Abfrage verwenden, aber diese kurze Schreibweise klappt auch!
Nun ist es Zeit, unsere Queue zu testen:
public class WarteschlangenTest {
public static void main(String[] args) {
Queue meineQueue = new Queue();
meineQueue.enqueue(new Auto("Rot", 50));
meineQueue.enqueue(new Auto("Gelb", 60));
meineQueue.enqueue(new Auto("Grün", 40));
meineQueue.enqueue(new Auto("Blau", 70));
Auto aktuell;
while (!meineQueue.isEmpty()) {
aktuell = (Auto) meineQueue.front();
aktuell.schreibeInfos();
meineQueue.dequeue();
}
meineQueue.enqueue(new Auto("Rot", 50));
meineQueue.enqueue(new Auto("Gelb", 60));
meineQueue.enqueue(new Auto("Grün", 40));
meineQueue.enqueue(new Auto("Blau", 70));
while (!meineQueue.isEmpty()) {
aktuell = (Auto) meineQueue.front();
aktuell.schreibeInfos();
meineQueue.dequeue();
}
meineQueue.dequeue();
}
}
Hier werden zweimal die Daten der Autos angezeigt. Bei einem Test von Datenstrukturen ist es nämlich immer empfehlenswert, sie einmal zu füllen, dann zu leeren und erneut zu füllen. Oft bemerkt man erst dann mögliche Programmierfehler.
Die letzte Anweisung dient auch dazu, zu testen, ob ein Versuch aus einer leeren Schlangen etwas zu entfernen zu einem Fehler führt.
Eine generische Klasse Queue
Wir werden unsere Queue nun so verändern, dass ein explizites Casten (zum Glück) nicht mehr nötig ist. Dies lässt sich in der folgenden Weise erreichen:
public class Queue<Type> { // In den spitzen Klammern steht der Datentyp!
private Knoten kopf;
private Knoten ende;
public Queue() {
kopf = null;
ende = null;
}
public void enqueue(Type pInhalt) { // Nur passende Objekte erlaubt!
if (pInhalt != null) {
if (isEmpty()) {
kopf = new Knoten(pInhalt);
ende = kopf;
} else {
ende.setNaechster(new Knoten(pInhalt));
ende = ende.getNaechster();
}
}
}
public void dequeue() {
if (!isEmpty()) {
if (ende == kopf) { // nur ein Knoten vorhanden
kopf = null;
ende = null;
} else { // mehrere Knoten vorhanden
kopf = kopf.getNaechster();
}
}
}
public Type front() { // Ein Objekt der Klasse Type wird geliefert!
if (!isEmpty()) {
return (Type)kopf.getInhalt(); // Casten passiert hier!
} else {
return null;
}
}
public boolean isEmpty() {
return kopf == null;
}
}
Beim Erstellen einer Queue müssen wir ab jetzt angeben, von welcher Klasse die Inhaltsobjekte sein sollen. Entsprechend taucht nirgendwo mehr das Wort „Object“ auf! Stattdessen steht dort nun immer der angegebene Datentyp.
Hier sehen wir einen Einsatz dieser Variante:
public class WarteschlangenTest {
public static void main(String[] args) {
Queue<Auto> meineQueue = new Queue();
meineQueue.enqueue(new Auto("Rot", 50));
meineQueue.enqueue(new Auto("Gelb", 60));
meineQueue.enqueue(new Auto("Grün", 40));
meineQueue.enqueue(new Auto("Blau", 70));
while (!meineQueue.isEmpty()) {
meineQueue.front().schreibeInfos();
meineQueue.dequeue();
}
}
}
Wie versprochen ist hier kein Casten mehr nötig! Ganz im Gegenteil ist die Anweisung meineQueue.front().schreibeInfos(); erfreulich kompakt.
Eine private innere Klasse
Die Abiturklasse Queue in NRW verwendet eine private innere Klasse, um die Knoten zu modellieren. Passen wir unsere Implementierung an, sieht sie so aus:
public class Queue<Type> { // In den spitzen Klammern steht der Datentyp!
// Beginn der privaten inneren Klasse
private class Knoten {
private Type inhalt; // Hier wird auch Type benutzt!
private Knoten naechster;
public Knoten(Type pInhalt) { // Hier wird auch Type benutzt!
inhalt = pInhalt;
naechster = null;
}
public Knoten getNaechster() {
return naechster;
}
public Type getInhalt() { // Hier wird auch Type benutzt!
return inhalt;
}
public void setNaechster(Knoten pNaechster) {
naechster = pNaechster;
}
}
// Ende der privaten inneren Klasse
private Knoten kopf;
private Knoten ende;
public Queue() {
kopf = null;
ende = null;
}
public void enqueue(Type pInhalt) { // Nur passende Objekte erlaubt!
if (pInhalt != null) {
if (isEmpty()) {
kopf = new Knoten(pInhalt);
ende = kopf;
} else {
ende.setNaechster(new Knoten(pInhalt));
ende = ende.getNaechster();
}
}
}
public void dequeue() {
if (!isEmpty()) {
if (ende == kopf) { // nur ein Knoten vorhanden
kopf = null;
ende = null;
} else { // mehrere Knoten vorhanden
kopf = kopf.getNaechster();
}
}
}
public Type front() { // Ein Objekt der Klasse Type wird geliefert!
if (!isEmpty()) {
return (Type) kopf.getInhalt(); // Casten passiert hier!
} else {
return null;
}
}
public boolean isEmpty() {
return kopf == null;
}
}
Dies hat zur Folge, dass Objekte der Klasse Knoten nur von einer Queue erzeugt werden können. Hängt man eine neues Objekt an eine Queue an, so erzeugt sie – wie gewohnt – einen Knoten und legt dort das Objekt ab. Möchte man selbst aber manuell einen Knoten erstellen, so stellt man fest, dass man keinen Zugriff auf die Klasse Knoten hat und daher keinen Knoten erstellen kann.
Das ist hier durchaus sinnvoll, denn eigentlich interessiert uns ja nur das Erstellen und Anwenden von Queues. Das „im Hintergrund“ Knoten verwendet werden, kann uns egal sein!