Rückblick
Stapel, Warteschlange und Liste unterscheiden sich nicht darin, was sie speichern, sondern darin, wer als Nächstes drankommt. Genau diese Frage ist es, die man bei einer Anwendung stellen muss – nicht die nach dem Speicherplatz.
Das kann ich jetzt
- Ich kann das LIFO-Prinzip des Stapels erklären und die Operationen benennen. (Stapel)
- Ich kann das FIFO-Prinzip der Warteschlange erklären und die Operationen benennen. (Warteschlange)
- Ich kann beschreiben, wie eine verkettete Liste aus Knoten aufgebaut ist. (Liste)
- Ich kann zu einem Anwendungsfall die passende Struktur begründet auswählen.
- Ich kann die Operationen einer Struktur aus ihrer Dokumentation heraus benutzen, ohne ihre Implementierung zu kennen.
Gemischte Aufgaben
Aufgabe 1: Wer kommt als Nächstes dran?
a) Auf einen leeren Stapel werden nacheinander A, B, C gelegt. Danach wird zweimal pop ausgeführt, dann D gelegt, dann einmal pop. Was liefert der letzte pop, und was liegt danach noch auf dem Stapel?
b) Dieselbe Folge mit einer Warteschlange: enqueue A, enqueue B, enqueue C, zweimal dequeue, enqueue D, einmal dequeue. Was liefert der letzte dequeue?
c) Warum liefert top beziehungsweise front einen Wert, ohne dass sich die Struktur ändert – und warum ist es trotzdem sinnvoll, dass es diese Operation zusätzlich zu pop gibt?
d) Welche Vorkehrung muss man treffen, bevor man pop aufruft? Was passiert sonst?
Aufgabe 2: Welche Struktur passt?
Wähle für jeden Fall die passende Struktur und begründe mit dem Zugriffsprinzip.
a) Die Rückgängig-Funktion eines Zeichenprogramms.
b) Die Warteschlange an einem Druckerserver.
c) Die Aufrufe eines rekursiven Programms – wer merkt sich, wohin zurückgesprungen wird?
d) Die Liste der Teilnehmerinnen einer AG, in die jederzeit an beliebiger Stelle jemand eingefügt werden soll.
e) Die Bearbeitung von Nachrichten in einem Messenger in der Reihenfolge des Eintreffens.
f) Ein Labyrinth so durchsuchen, 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 oder der Älteste?
Kommt es dagegen auf eine Reihenfolge an, in die man an beliebiger Stelle eingreifen können muss, ist keins von beiden gemeint.
Aufgabe 3: Klammern prüfen
Ein Übersetzer muss feststellen, ob die Klammern eines Ausdrucks richtig gesetzt sind. Gültig sind (), [] und {}, beliebig geschachtelt.
a) Warum ist ein Stapel dafür genau die richtige Struktur? Begründe mit der Schachtelung.
b) Beschreib das Verfahren in Worten, bevor du programmierst: Was tust du bei einer öffnenden, was bei einer schließenden Klammer?
c) Woran erkennst du am Ende, dass der Ausdruck gültig war? Zwei Fehlerfälle sind zu unterscheiden.
d) Vervollständige das Programm im Übungsbereich.
e) Teste mit: (a + [b * c]) - {d}, (a + [b * c)], ((a) und a). Welcher Fehlerfall tritt jeweils ein?
Tipp 1: Das Verfahren
- Öffnende Klammer: auf den Stapel legen.
- Schließende Klammer: oberste vom Stapel holen und prüfen, ob sie zur schließenden passt.
- Am Ende: Der Stapel muss leer sein.
Tipp 2: Die zwei Fehlerfälle
- Es kommt eine schließende Klammer, aber der Stapel ist leer – oder oben liegt die falsche Sorte.
- Der Text ist zu Ende, aber auf dem Stapel liegt noch etwas: Es wurde mehr geöffnet als geschlossen.