Einstieg: Wer zuletzt kommt
Drück in einem beliebigen Programm zehnmal Strg+Z. Die Änderungen werden rückwärts zurückgenommen – die letzte zuerst, die erste zuletzt. Das Programm hat sie sich gemerkt wie einen Stapel Teller: Neues kommt oben drauf, und heruntergenommen wird auch von oben.
Das ist die zweite Zugriffsregel, die in der Informatik überall auftaucht – und sie ist genau die Umkehrung der Warteschlange.
Ein Stapel (englisch stack, auch Kellerstapel) ist eine lineare Datenstruktur mit nur einer Zugriffsstelle, dem oberen Ende:
pushlegt oben auf,topliest das oberste Element,popentfernt es.
Das Prinzip heißt LIFO – Last In, First Out: Was zuletzt hineinkommt, kommt zuerst wieder heraus.
Der Stapel ist die Struktur für alles, was verschachtelt ist und in umgekehrter Reihenfolge wieder aufgelöst werden muss:
| Wo | Was liegt auf dem Stapel |
|---|---|
| Rückgängig-Funktion | die letzten Änderungen |
| Methodenaufrufe | wohin zurückgesprungen werden muss – der Aufrufstapel |
| Klammerprüfung | die noch offenen Klammern |
| Zurück-Knopf im Browser | die zuletzt besuchten Seiten |
Alle vier haben dieselbe Form: Das zuletzt Begonnene muss als Erstes abgeschlossen werden.
Von außen zeigt die Abiturklasse Stack nur diese Methoden. Wie sie innen aufgebaut ist, spielt für das Benutzen keine Rolle.
classDiagram
class Stack~ContentType~ {
+Stack()
+isEmpty() boolean
+push(pContent: ContentType)
+pop()
+top() ContentType
}
Erst einmal ausprobieren
Unten liegt dieselbe Operationsfolge wie bei der Schlange – nur heißen die Methoden anders. Sage zuerst voraus, welche Ausgaben sie erzeugt, und lass sie dann ablaufen.
a) Notiere die erwarteten Ausgaben, trage sie ein und lass die Folge ablaufen.
b) Vergleiche mit der Schlange: Dieselbe Folge, andere Ausgaben. Erkläre den Unterschied in einem Satz.
c) Lege danach von Hand drei Namen auf und hebe sie wieder ab. In welcher Reihenfolge kommen sie heraus?
Weiterdenken: Du legst die Buchstaben L, A, G, E, R nacheinander auf einen Stapel und hebst sie danach alle wieder ab. Welches Wort entsteht? Wofür könnte man diesen Effekt nutzen?
Wer kommt als Nächstes dran?
Entscheide jeweils, ob ein Stapel oder eine Schlange passt. Begründe mit LIFO oder FIFO.
a) Der Zurück-Knopf eines Browsers.
b) Ein Drucker im Schulnetz bekommt Aufträge von mehreren Rechnern.
c) Ein Zeichenprogramm soll die letzten Schritte rückgängig machen.
d) Ein Stapel Bewerbungen, von denen die Personalabteilung immer die oberste bearbeitet. Ist das gerecht?
Der Aufrufstapel
Der wichtigste Stapel ist einer, den du nie selbst anlegst: Java führt für jedes Programm einen mit, um Methodenaufrufe zu verwalten. Ihn kennst du schon aus 2.3 Kellerstapel und Halde – und aus 3.1 Rekursion, wo du ihn beim Aufrufbaum in Aktion gesehen hast.
a) Erkläre mit den Begriffen dieser Seite, was beim Aufruf einer Methode auf den Aufrufstapel gelegt und was beim return wieder abgehoben wird.
b) Begründe, warum dafür ein Stapel die richtige Struktur ist und keine Warteschlange.
Weiterdenken: Eine Endlosrekursion bricht mit einem StackOverflowError ab. Erkläre den Namen dieses Fehlers.