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, oder null, 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, wird null zurück gegeben.

Das Klassendiagramm hat damit folgende Form (kein UML sondern Java-spezifisch):

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

1. Vor Aufruf der Methode push(Karte k) besteht der Stapel aus zwei Karten.
2. Die als k referenzierte Karte wird als Parameter übergeben.
3. Der Nachfolger der Karte k soll die bisherige Karte top sein.
4. Die oberste Karte des Stapels soll nun k sein.

Klicke auf die einzelnen Schritte zur Veranschaulichung.

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:

1. 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.
2. 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.