Im Spiel: Wellen, Weg zurück, Bestand
Optional. Diese Seite ist ein Zusatzangebot am Ende des Kapitels. Sie führt nichts Neues ein, und weder der Rückblick noch die späteren Kapitel setzen sie voraus.
Stapel, Schlange und Liste unterscheiden sich nicht darin, was sie speichern, sondern darin, wer als Nächstes drankommt. Diese Seite zeigt alle drei im selben Spiel – jede an der Stelle, an der ihre Antwort auf diese Frage die richtige ist.
Scratch for Java in fünf Minuten
Diese Seite macht einen Entwurf mit der Grafikbibliothek Scratch for Java sichtbar. Du musst sie nicht kennen – hier steht alles, was du dafür brauchst. Geladen wird sie über libraries="scratch"; import-Zeilen gibt es nicht.
| Begriff | Was er bedeutet |
|---|---|
Stage |
die Bühne, 480 × 360 Pixel. Der Punkt (0, 0) liegt in der Mitte, die y-Achse zeigt nach oben. Man schreibt eine eigene Klasse, die von Stage erbt. |
Sprite |
eine Figur auf der Bühne. Auch dafür schreibt man eigene Klassen, die von Sprite erben. |
addCostume("coin_gold") |
gibt einer Figur ihr Bild. Die Bibliothek bringt über 1700 fertige Kostüme mit. |
this.add(objekt) |
fügt eine Figur oder einen Text der Bühne hinzu. Was nicht hinzugefügt wurde, sieht man nicht. |
run() |
wird für jedes Objekt etwa 60-mal pro Sekunde aufgerufen. Alles Fortlaufende steht hier drin. |
getTouchingSprite(Muenze.class) |
liefert das berührte Objekt oder null, wenn gerade keins berührt wird. Das null muss man immer abfragen. |
Dazu isKeyPressed(KeyCode.RIGHT) für die Tastatur, changeX(4) zum Bewegen, remove() zum Entfernen und new Text(text, x, y, breite) mit showText(...) für die Anzeige.
Zum Nachlesen: Die erste Grafik erklärt Bühne und Koordinatensystem, Eigene Sprites die eigenen Figurenklassen mit run(). Alle Methoden auf einen Blick: Referenz.
Die Programmierbereiche dieser Seite laden beide Bibliotheken – im Attribut libraries stehen sie kommasepariert: nrw,scratch.
Damit stehen Stack, Queue und List der NRW-Klassenbibliothek zusammen mit Stage und Sprite zur Verfügung. Es sind dieselben Klassen wie im Rest des Kapitels – nur diesmal mit etwas darin, das man sieht.
Drei Fragen, drei Strukturen
| Was das Spiel braucht | Wer kommt als Nächstes dran? | Struktur |
|---|---|---|
| Gegnerwellen nacheinander | die zuerst eingeplante Welle | Schlange |
| zurück zum letzten sicheren Platz | der zuletzt besuchte Platz | Stapel |
| alle noch offenen Gegenstände durchgehen | jeder, der Reihe nach | Liste |
Das ist keine willkürliche Zuordnung. Jede dieser drei Fragen hat genau eine passende Antwort, und wer die falsche Struktur nimmt, merkt es sofort.
Die Schlange: Wellen
Gegner kommen nicht alle auf einmal, sondern in Wellen. Die Welle, die zuerst eingeplant wurde, kommt zuerst – FIFO, das ist die Warteschlange.
wellen = new Queue<String>();
wellen.enqueue("MMM");
wellen.enqueue("MMFF");
wellen.enqueue("MHFFF");Jede Welle ist eine Zeichenkette, in der jedes Zeichen für einen Gegenstand steht. Ist die Bühne leer, wird die nächste Welle entnommen.
Die Schlange vergisst, was sie herausgegeben hat. Genau das ist hier richtig: Eine gespielte Welle kommt nicht wieder.
Und sie kennt keine Position. Man kann sie nicht fragen „was ist die dritte Welle?" – nur „was kommt als Nächstes?". Für Wellen ist das keine Einschränkung, sondern eine Zusicherung.
Der Stapel: der Weg zurück
Der Spieler hinterlässt bei jedem Schritt seine Position auf einem Stapel. Drückt man die Leertaste, wird der oberste Platz entnommen, und die Figur springt dorthin zurück – Schritt für Schritt rückwärts durch die eigene Spur.
Das geht nur mit einem Stapel. Der zuletzt besuchte Platz muss als Erstes zurückkommen: LIFO.
Warum speichert der Stapel die Position und nicht das Objekt?
Weil ein remove() in dieser Bibliothek endgültig ist: Eine entfernte Figur lässt sich nicht wieder auf die Bühne setzen. Ein Stapel aus Figuren wäre also ein Stapel aus Erinnerungen an Dinge, die es nicht mehr gibt.
Daten kann man aufheben, Objekte nicht immer. Diese Unterscheidung ist keine Eigenart der Bibliothek – sie ist derselbe Gedanke wie bei den Referenzen in 2.2.
Die Liste: der Bestand
Die Bühne weiß, welche Figuren sie zeichnet. Aber das Spiel braucht eine eigene Auskunft: Welche Gegenstände dieser Welle sind noch offen? Dafür führt es eine Liste und durchläuft sie mit toFirst, hasAccess, next.
Spiele eine Welle, halte dann die Leertaste gedrückt und sieh der Figur beim Rückwärtslaufen zu. Sie läuft die Spur ab, die du selbst gelegt hast – rückwärts, weil ein Stapel nichts anderes kann.
Aufgabe 1: die Strukturen ausreizen
a) Vertausche Schlange und Stapel: Speichere die Wellen in einem Stack. In welcher Reihenfolge kommen sie – und warum ist das für Wellen falsch?
b) Der Stapel wächst bei jedem Schritt. Schätze: Wie viele Plätze liegen nach zehn Sekunden Laufen darauf? (Die run-Methode läuft etwa 60-mal pro Sekunde.) Was bedeutet das für den Speicherbedarf?
c) Begrenze die Spur auf die letzten 200 Plätze. Warum ist das mit einem Stapel unangenehm – und welche Struktur könnte beides, vorn wegnehmen und hinten anhängen?
d) Zeige die Zahl der Plätze auf dem Stapel in der Anzeige an. Der NRW-Stapel hat kein anzahl() – wie kommst du trotzdem an die Zahl, ohne den Stapel zu zerstören?
Aufgabe 2: die Liste befragen
a) offen() läuft jedes Mal durch die ganze Liste. Wie oft passiert das pro Sekunde – und was würdest du stattdessen tun?
b) Schreibe wertDerWelle(): die Summe der Punkte, die in dieser Welle noch zu holen sind. Nur Münzen zählen.
c) Warum steht in streiche ein Vergleich mit == und nicht mit equals? Was würde equals hier vergleichen?
d) Was passiert, wenn du in streiche das return nach dem remove() weglässt? Sage es voraus, bevor du es ausprobierst.
Und ohne Spiel?
| Im Spiel | Dieselbe Struktur woanders |
|---|---|
| Wellen der Reihe nach | Druckaufträge, Warteschlange an der Kasse, Nachrichten im Postfach |
| Weg zurück, Schritt für Schritt | Rückgängig im Textprogramm, Zurück-Knopf im Browser, Aufrufstapel |
| Bestand der offenen Gegenstände | Warenkorb, Teilnehmerliste, alle Nachrichten eines Chats |
Wer in der Klausur entscheiden muss, welche Struktur passt, stellt genau eine Frage: Wer kommt als Nächstes dran – der Erste, der Letzte, oder alle der Reihe nach?