Rückblick
Schlange, Stapel und Liste unterscheiden sich nicht darin, was sie speichern, sondern darin, welches Element als Nächstes an die Reihe kommt: das zuerst kam, das zuletzt kam oder das, das du auswählst. Genau diese Frage musst du bei jeder Anwendung stellen – nicht die nach dem Speicherplatz.
Das kann ich jetzt
- Ich kann das FIFO-Prinzip der Schlange erklären und ihre Operationen benennen. (Schlange)
- Ich kann das LIFO-Prinzip des Stapels erklären und seine Operationen benennen. (Stapel)
- Ich kann erklären, wie man mit dem aktuellen Element einer Liste arbeitet. (Liste)
- Ich kann am Objektdiagramm erläutern, was beim Einfügen und Entfernen mit den Verweisen passiert – auch in den Grenzfällen. (Schlange, Stapel, Liste)
- Ich kann zu einem Anwendungsfall die passende Struktur begründet auswählen.
- Ich kann Methoden schreiben, die eine Struktur über ihre Dokumentation benutzen – und sie dabei erhalten, wenn das verlangt ist. (Schlange, Stapel, Liste)
- Ich kann ein Struktogramm in Java umsetzen und zu einer Methode selbst ein Struktogramm entwerfen.
- (LK) Ich kann die Operationen einer Struktur selbst implementieren. (Schlange, Stapel, Liste)
Gemischte Aufgaben
Aufgabe 1: Wer kommt als Nächstes dran?
a) Auf einen leeren Stapel werden nacheinander push("A"), push("B"), push("C") ausgeführt. Danach zweimal pop(), dann push("D"), dann einmal pop(). Was liefert top() jetzt, und was liegt noch auf dem Stapel?
b) Dieselbe Folge mit einer Schlange: enqueue("A"), enqueue("B"), enqueue("C"), zweimal dequeue(), enqueue("D"), einmal dequeue(). Was liefert front() jetzt?
c) In einer Liste stehen A, B, C. Es wird toFirst(), next(), remove(), insert("D") und toLast() ausgeführt. Was liefert getContent() jetzt, und welche Elemente stehen in der Liste?
d) pop() und dequeue() liefern in den Abiturklassen nichts zurück. Wie kommst du dann an das entfernte Element?
e) Welche Vorkehrung muss man treffen, bevor man mit dem Ergebnis von top() weiterarbeitet, etwa top().equals(...)? Was passiert sonst?
Aufgabe 2: Welche Struktur passt?
Wähle für jeden Fall die passende Struktur und begründe mit dem Zugriffsprinzip.
a) Ein Browser hat einen Zurück- und einen Vorwärts-Knopf. Wie viele Strukturen braucht man, und welche?
b) Eine Arztpraxis ruft in der Reihenfolge der Ankunft auf – Notfälle kommen aber immer zuerst an die Reihe.
c) Eine Bestenliste, in die neue Ergebnisse an der richtigen Stelle einsortiert werden.
d) Ein Labyrinth soll so durchsucht werden, dass zuerst der zuletzt betretene Weg weiterverfolgt wird.
Tipp
Stell für jeden Fall genau eine Frage: Wer kommt als Nächstes dran – der Neueste, der Älteste oder das, das ich auswähle? Manchmal braucht es mehr als eine Struktur.
Aufgabe 3: Strukturen kombinieren
a) void umdrehen(Queue<String> pSchlange) soll die Reihenfolge einer Schlange umkehren. Benutze dazu einen Stapel. Entwirf zuerst im Editor ein Struktogramm, setze es anschließend um.
b) boolean istPalindrom(String pWort) soll prüfen, ob ein Wort vorwärts und rückwärts gleich gelesen wird, etwa otto oder anna. Benutze dazu einen Stapel und eine Schlange.
Weiterdenken:
c) Queue<String> alsSchlange(List<String> pListe) liefert eine neue Schlange mit den Elementen der Liste in derselben Reihenfolge.
Tipp: istPalindrom
Leg jeden Buchstaben sowohl auf den Stapel als auch in die Schlange. Danach kommen sie aus dem Stapel rückwärts und aus der Schlange vorwärts heraus. Vergleiche sie paarweise.