Doppelstunde 6: Der ADT Queue

In dieser Doppelstunde wird analog zum ADT Stack die Queue eingeführt. In der Präsentation 07_queue.odp wird zunächst wieder auf das Wartezimmer-Beispiel aus der ersten Doppelstunde zurückgegriffen. Der Zugriff auf die Schlange der wartenden Patienten wird so eingeschränkt, dass tatsächlich nur neue Patienten hinten eingefügt werden und vorne entfernt werden. Es ist also nicht mehr möglich, vorzeitig das Wartezimmer zu verlassen oder Notfälle vorne einzufügen. In den Implementationen wird auf bekannte Techniken verwiesen, so dass weniger Unterrichtszeit dafür nötig sein dürfte.

Als erste Implementationslösung wird die einfach verkettete Liste erläutert. Man definiert das erste Element der Liste (auf das man den Verweis speichert) als „vorderes“ Ende der Queue. Dabei stellt man fest, dass das Entfernen aus der Queue einfach möglich ist, das Einreihen aber aufwendig ist, weil man erst das Ende der Queue suchen muss, indem man die Nachfolger-Verweise durchläuft. Man könnte ebenso den Verweis auf das letzte Element in der Queue speichern, so dass jeder Knoten auf seinen Vorgänger verweist. In diesem Fall wäre das Einreihen einfach, das Entfernen aber schwer.

Als Verbesserung wird dann untersucht, was passiert, wenn man zusätzlich einen Verweis auf das Ende der Queue speichert. Man stellt fest, dass auch das Einreihen in konstanter Zeit möglich ist und damit die Queue sehr effizient arbeiten kann.

Im Anschluss wird optional eine Variante mit Hilfe eines Arrays erklärt. Damit nicht bei jedem Einfügen oder Entfernen alle Elemente kopiert werden müssen, wird ein „Ringpuffer“-Prinzip verwendet (vgl. Präsentation).

Wenn Zeit dafür bleibt, kann dieses Vorgehen als Rollenspiel umgesetzt werden. Dazu stellt man z.B. fünf Stühle nebeneinander und beschriftet sie ggf. mit Zahlen von 0 bis 4. An der Tafel wird stets festgehalten, auf welcher Stuhlnummer die erste Person der Schlange sitzt („Anfang“) und welches die nächste freie Position („Ende“) ist. Dann führt man die folgenden Queue-Operationen aus:

Bildquelle: Rollenspiel von ZPG Informatik [CC BY-NC-SA 3.0 DE], aus 01_unterrichtsverlauf.odt

Im Anschluss soll mindestens eine Implementationsvariante programmiert werden. Das Aufgabenblatt 07_queue.odt beschreibt nochmal das Ringpuffer-Prinzip. Die Implementationen können jeweils mit einer der entsprechenden Tester-Klassen getestet werden.

Danach wird ein Spiel implementiert, das die soeben implementierte Queue verwendet. Es handelt sich dabei um den Klassiker „Snake“. Hier wird einmalig zu Greenfoot gewechselt, weil dort die Umsetzung von grafischen Oberflächen und Animationen sehr einfach machbar ist. Das Blatt 08_snake.odt führt die Schülerinnen und Schüler durch die Umsetzung des Spiels. Ähnlich wie bei Hanoi und Freecell muss hier auch die eigene Implementation der Queue in das Projekt eingefügt werden. Bemerkenswert ist hier auch, dass die Queue „rückwärts“ verwendet wird: Der Kopf der Schlange entspricht dem letzten Element der Queue, der Schwanz dem ersten Element. Dies ist nötig, weil so die Körpersegmente dazwischen nicht in jedem Zeitschritt verändert werden müssen.

Unterrichtsverlauf: Herunterladen [odt][187 KB]

Weiter zu DS 7: Bäume