Rückblick
Schlange, Stapel und Liste unterscheiden sich nicht darin, was sie speichern, sondern darin, wer als Nächstes drankommt: der Erste, der kam, der Letzte, der kam, oder der, den man auswählt. Genau diese Frage muss man bei einer 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 kommt man trotzdem an das Element, das entfernt wird?
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 dran.
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 der, den ich auswähle? Manchmal braucht man 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 dann 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.