Doppelstunde 5: Anwendungen des Stacks

Ziel der Doppelstunde ist, zwei Programme zu implementieren, die Stacks verwenden. Die Verwendung eines Spiels als Anwendung ist motivierend und zudem sind die stapelartigen Strukturen (Scheiben- bzw. Kartenstapel) direkt sichtbar und erleichtern den Transfer. In beiden Anwendungen muss eine der selbstprogrammierten Stack-Implementationen aus der vorangegangenen Stunde verwendet werden und in das BlueJ-Projekt eingefügt werden. Falls einzelne Kursmitglieder die Implementation nicht haben, müsste diese von der Lehrkraft gestellt werden.

Sinnvollerweise sollte mit dem Spiel „Hanoi“ begonnen werden, da dieses einfacher ist. Bei dieser Aufgabe soll nur innerhalb der Klasse HanoiGame gearbeitet werden, die anderen Klassen sollen unverändert gelassen werden. Zudem dürfen bei den vorgegebenen Methoden die Namen und Signaturen nicht verändert werden.

Ein Problem, das sich sowohl bei den Türmen von Hanoi als auch bei Freecell stellt, ist dass man für die grafische Darstellung auch andere Stackelemente als das oberste sehen muss. Zudem gibt der Standard-Stack auch keine Informationen darüber, wie viele Elemente er enthält. Als Lösung sind zwei Ansätze denkbar:

• Man erweitert den Stack um zwei Methoden getHoehe(): int und getNtes(n: int): T – diese geben die Höhe des Stacks und das n-te Element von oben zurück. Dies erlaubt allerdings Manipulationen des Inneren des Stacks und widerspricht daher dem Stack-Prinzip.
• Man erzeugt einen neuen Temporär-Stack, auf den alle Werte des Stacks selbst „umgeschichtet“ werden. Dabei zählt man die Elemente. Wenn der Ausgangsstack leer ist, wird zurückgeschichtet. Analog geht man vor, um das n-te Element von oben zu finden. Dieses Vorgehen ist zwar aufwendiger, lässt aber den ADT Stack unangetastet.

Das Projekt „Hanoi“ wird in Doppelstunde 9 nochmals aufgegriffen, wenn das Lösen des Problems automatisiert wird. Daher ist es wichtig, dass alle das Projekt abgeschlossen haben, bevor sie mit Freecell weitermachen.

Im Projekt Freecell soll – ähnlich wie bei Hanoi – nur in der Klasse FreecellGame gearbeitet werden. Die restlichen Klassen sollen nicht verändert werden. Das Freecell-Projekt ist deutlich komplexer als das Hanoi-Projekt, weil hier drei verschiedene Bereiche und die entsprechenden Regeln zu behandeln sind. Daher ist das Aufgabenblatt gestuft aufgebaut, so dass das Spiel bereits spielbar ist, wenn man nur zwei der fünf Aufgaben gelöst hat. Zudem macht der zufällige Charakter das Reproduzieren und Lösen von Problemen etwas schwierig. Weisen Sie daher ausdrücklich auf den Konstruktor der Klasse FreecellGame hin, der einen int-Parameter annimmt. Mit diesem Parameter kann man den Startwert des Zufallszahlengenerators belegen, so dass dieser stets die gleichen Zufallszahlen und damit immer die gleiche Ausgangssituation erzeugt.

Unterrichtsverlauf: Herunterladen [odt][187 KB]

Weiter zu DS 6: ADT Queue