Implementierung eines Stapels
Stapel von Spielkarten
Es gibt unterschiedliche Möglichkeiten, wie man einen Stapel von Karten im Computer realisieren kann. Eine mögliche Variante ist im folgenden Objektdiagramm dargestellt:
Das Objekt der Klasse Stapel
ist hier für die Verwaltung der Objekte zuständig
und besitzt eine Referenz auf das oberste Element mit dem Namen top
.
Jede Karte besitzt eine Referenz auf die Karte, die im Stapel unter ihr liegt.
Die unterste Karte hat keine nächste Karte, speichert also folglich den Wert null
.
Operationen, die man an einem Stapel üblicherweise ausführen möchte, sind:
-
isEmpty()
prüft, ob der Stapel leer ist. -
top()
gibt das oberste Objekt des Stapels zurück, odernull
, falls der Stapel leer ist. -
push(Karte k)
legt ein Objekt -in unserem Fall eine Karte- auf den Stapel. -
pop()
gibt das oberste Objekt des Stapel zurück und entfernt dieses. Falls der Stapel leer ist, wirdnull
zurück gegeben.
Das Klassendiagramm hat damit folgende Form:
Beachte insbesondere die Beziehung zwischen Karte
und Karte
.
Da eine Karte eine Referenz auf eine andere Karte speichert, erhält man im Klassendiagramm
eine reflexive Beziehung, also eine Beziehung zwischen
Objekten des gleichen Typs.
Für die Implementierung und das systematische Testen des Spiels ist es von Vorteil den Konstruktor
der Klasse Karte
zu überladen. Der parameterlose Konstruktor erzeugt eine Karte mit
zufälligem Wert, während der Konstruktor mit Parameter den Wert der Karte übergeben bekommt.
Der Wert einer Karte soll zur Vereinfachung eine ganze Zahl sein.
Die Methode getWert()
der Klasse Karte
könnte auch weggelassen werden,
wenn man das Attribut wert
nicht als privat
definiert.
Für automatische Unit-Tests
ist es aber von Vorteil die Methode zu implementieren.
Aufgabe 1 - Beziehungen
Diskutiere die dargestellten Beziehungstypen. Welche Beziehungstypen werden benutzt? Warum? Welche Alternativen wären noch denkbar?
Implementierung des Grundgerüsts
Zuerst muss das Klassendiagramm in Quellcode überführt werden.
Aufgabe 2 - Klassendiagramm übersetzen
Erstelle ein neues BlueJ-Projekt und übersetze das Klassendiagramm in Java-Code.
Die Methoden des Stapels können dabei noch leer bleiben.
Damit sich das Projekt compilieren lässt, müssen Methoden mit Rückgabewert Dummywerte
zurück geben. Als Wahrweitswert könnte also immer false
zurückgegeben werden.
Methoden mit Rückgabetyp Karte
können z.B. immer null
zurückgeben.
class Karte {
int wert;
Karte next;
Karte() {
wert = new java.util.Random().nextInt(15) + 1; }
Karte(int kartenwert) {
wert = kartenwert; }
int getWert() { return wert; }
}
class Stapel {
Karte top;
void push(Karte k) { }
Karte pop() {
return null; }
boolean isEmpty() {
return false; }
Karte top() {
return null; }
}
Aufgabe 3 - (optional) JUnit-Test
Um die korrekte Funktionsweise der Implementierung des Stapels zu überprüfen, müssen systematisch Tests durchgeführt werden. Dazu kann man Testframeworks wie JUnit verwenden. Bei entsprechender Vorbereitung können die Tests sogar schon vor der eigentlichen Implementierung definiert werden. Wie dies funktioniert, kannst Du im Abschnitt Exkurs - Unit-Tests lesen.
Bearbeite den Abschnitt und überlege Dir anschließend unterschiedliche Testfälle, so dass Du nach erfolgreichem Test Deiner Implementierung vertraust. (Diese Aufgabe kann ausgelassen werden, wenn automatische Tests und testgetriebene Entwicklung nicht behandelt werden sollen.)
Methoden ohne Änderung des Stapels
Die Methoden isEmpty
und top
verändern den Stapel nicht und
sind leicht zu implementieren.
Die Methode isEmpty
muss überprüfen, ob die oberste Karte gleich null
ist.
Falls dies der Fall ist, gibt sie true
zurück, ansonsten false
.
Die Methode top
muss nur das oberste Element zurück geben.
Falls der Stapel noch leer ist, wird null
zurück gegeben.
Aufgabe 4 - isEmpty und top
Implementiere die beiden Methoden.
Karten ablegen
Um eine Karte abzulegen, wird die Methode push(Karte k)
aufgerufen.
Aufgabe 5 - Leerer Stapel
Überlege Dir ob und/oder inwiefern sich die Vorgehensweise bei einem leeren Stapel unterscheiden muss.
Aufgabe 6 - push
Implementiere die Methode push
.
Teste die Methode mit Hilfe des Objektinspektors wie im Video dargestellt:
Karten entfernen
Beim Entfernen einer Karte muss die top
-Referenz neu gesetzt und
die Karte vom Stapel isoliert werden:
Der Garbage-Collector (deutsch: Müllsammler) von Java
erkennt Objekte, auf die keine Referenz mehr existiert, und entfernt diese aus dem Speicher.
Die Karte mit dem Wert 8 kann dann entfernt werden.
(Knobelaufgabe: Warum ist es notwendig, dazu auch das next
-Attribut der zu entfernenden Karte
auf null
zu setzen? Beschreibe eine entsprechende Situation.)
Aufgabe 7 - Entfernen im Objektdiagramm
Zeichne in das Objektdiagramm ähnlich der obigen Darstellung die Schritte ein, die notwendig sind, um das oberste Element des Stapels zu löschen und anschließend zurückzugeben. Drucke die Grafik dazu aus oder benutze eine entsprechende Software. Tipp: Du benötigst eine lokale Variable.
Aufgabe 8 - pop
Implementiere die Methode und teste sie mit Hilfe des Objektinspektors wie oben. Überlege Dir inwiefern die Vorgehensweise sich bei einem leeren Stapel unterscheiden muss.
Aufgabe 9 - Test des Stapelklasse
Teste die fertiggestellte Stapel-Klasse ausführlich. Falls Du JUnit-Tests angelegt hast, musst Du nun nur noch den entsprechenden Button klicken :-)
Schwächen der Modellierung
Die Stapel-Klasse ist nun funktionstüchtig und das Spiel kann implementiert werden. Soll die Stapelklasse außerhalb des Spiels nicht wieder benutzt werden, ist die Modellierung auf die obige Art auch in Ordnung. Prinzipiell besitzt sie aber zwei Nachteile:
- Man hat Funktionalität in eine Klasse verlagert, die rein logisch dort nicht
hin gehört: Eine Karte besitzt von der eigentlichen Logik keinen Nachfolger.
Um auch andere Objekttypen analog auf einen Stapel zu legen, müsste man
immer ein
next
-Attribut einführen. - Die Stapel-Klasse muss für andere Anwendungen immer angepasst werden.
Die Funktionalität bleibt gleich, aber die Datentypen müssen geändert werden.
Falls das
next
-Attribut der zu stapelnden Objekte einen anderen Namen hat, muss auch dieser geändert werden.
Insgesamt ist der Entwurf also richtig, lässt sich aber nicht direkt für andere Projekte wiederverwenden. Wenn Du wissen möchtest wie man den Entwurf wiederverwendbar gestaltet, dann bearbeite den Abschnitt Exkurs - Generische und innere Klassen und passe die Stapel- und Karten-Klasse an.