Zur Haupt­na­vi­ga­ti­on sprin­gen [Alt]+[0] Zum Sei­ten­in­halt sprin­gen [Alt]+[1]

Ds­op­pel­stun­de 4: Der ADT Stack

In die­ser Dop­pel­stun­de wird der ADT Stack ein­ge­führt. Die Prä­sen­ta­ti­on 05_stack.odp führt das LIFO-Prin­zip an­hand eines Gü­ter­bahn­hofs ein. Da­nach wer­den die Ope­ra­tio­nen vor­ge­stellt und das Ver­hal­ten ana­log zu einem Sta­pel Bü­cher de­mons­triert. Es wird auch ein Aus­blick auf die An­wen­dung des Stacks beim Auf­ruf von Un­ter­pro­gram­men ge­ge­ben. Dies wird aber in der 9. Dop­pel­stun­de noch­mals ver­tieft. Da­nach be­spricht man eine mög­li­che Im­ple­men­ta­ti­on des Stacks als ver­ket­te­te Liste, wobei das obers­te Stack-Ele­ment dem An­fang der Liste ent­spricht. Die Tech­ni­ken dürf­ten den Kurs­mit­glie­dern be­kannt vor­kom­men, sie sind ein Teil der ver­ket­te­ten Liste.

Im An­schluss soll min­des­tens eine Va­ri­an­te des Stacks im­ple­men­tiert wer­den. Dabei ste­hen zur Dif­fe­ren­zie­rung ver­schie­de­ne An­sät­ze zur Ver­fü­gung: Die ver­ket­te­te Liste, wie sie in der Prä­sen­ta­ti­on vor­ge­stellt wurde, ein Ar­ray­List-ar­ti­ges Prin­zip mit einem Array sowie einem Index, der das Ende des gül­ti­gen Be­reichs mar­kiert sowie eine Um­set­zung mit Hilfe der Can­tor­schen Paa­rungs­funk­ti­on. Die­ser ist eher für die schnel­len Schü­le­rin­nen und Schü­ler ge­dacht, da die­ses Prin­zip nur theo­re­tisch nutz­bar ist und keine prak­ti­sche An­wen­dung hat. Es ist hier wich­ti­ger, dass das Prin­zip ma­nu­ell mit Hilfe eines Ta­schen­rech­ners aus­ge­führt wer­den kann. Jede Im­ple­men­ta­ti­on kann mit einer der zu­ge­hö­ri­gen Tes­ter-Klas­se au­to­ma­tisch ge­tes­tet wer­den.

 

Un­ter­richts­ver­lauf: Her­un­ter­la­den [odt][187 KB]

 

Wei­ter zu DS 5: An­wen­dun­gen des Stacks