Dsoppelstunde 4: Der ADT Stack

In dieser Doppelstunde wird der ADT Stack eingeführt. Die Präsentation 05_stack.odp führt das LIFO-Prinzip anhand eines Güterbahnhofs ein. Danach werden die Operationen vorgestellt und das Verhalten analog zu einem Stapel Bücher demonstriert. Es wird auch ein Ausblick auf die Anwendung des Stacks beim Aufruf von Unterprogrammen gegeben. Dies wird aber in der 9. Doppelstunde nochmals vertieft. Danach bespricht man eine mögliche Implementation des Stacks als verkettete Liste, wobei das oberste Stack-Element dem Anfang der Liste entspricht. Die Techniken dürften den Kursmitgliedern bekannt vorkommen, sie sind ein Teil der verketteten Liste.

Im Anschluss soll mindestens eine Variante des Stacks implementiert werden. Dabei stehen zur Differenzierung verschiedene Ansätze zur Verfügung: Die verkettete Liste, wie sie in der Präsentation vorgestellt wurde, ein ArrayList-artiges Prinzip mit einem Array sowie einem Index, der das Ende des gültigen Bereichs markiert sowie eine Umsetzung mit Hilfe der Cantorschen Paarungsfunktion. Dieser ist eher für die schnellen Schülerinnen und Schüler gedacht, da dieses Prinzip nur theoretisch nutzbar ist und keine praktische Anwendung hat. Es ist hier wichtiger, dass das Prinzip manuell mit Hilfe eines Taschenrechners ausgeführt werden kann. Jede Implementation kann mit einer der zugehörigen Tester-Klasse automatisch getestet werden.

Unterrichtsverlauf: Herunterladen [odt][187 KB]

Weiter zu DS 5: Anwendungen des Stacks