Der Stapel

Ein Ende, zwei Operationen

Stell dir einen Stapel Teller vor. Du legst einen oben drauf und nimmst einen oben weg; an den untersten kommst du nicht heran, ohne die darüber abzuräumen. Genau so viel kann ein Stack, und mehr braucht er nicht: push legt einen Wert oben auf, pop nimmt den obersten herunter und gibt ihn zurück.

Geh den Stapel unten Schritt für Schritt durch. Achte darauf, was pop liefert: nie das, was am längsten liegt, immer das, was zuletzt kam.

Die Gegenfigur ist die Schlange. Sie hat zwei offene Enden: hinten wird angestellt (enqueue), vorn wird bedient (dequeue). Dieselben drei Werte, dieselbe Anzahl Schritte, und trotzdem kommt etwas anderes heraus.

Warum Strg+Z von oben nimmt

Ein Editor merkt sich jede Änderung als eigenen Eintrag: getipptes Wort, eingefügtes Bild, gelöschter Absatz. Diese Einträge landen auf dem Undo-Stapel. Strg+Z nimmt den obersten herunter, kehrt ihn um und legt ihn auf einen zweiten Stapel, den Redo-Stapel; Strg+Y holt ihn von dort zurück.

Der Grund für die Ordnung ist nicht Geschwindigkeit, sondern Zuständigkeit. Jede Änderung ist auf dem Text formuliert, den die vorherige hinterlassen hat: „lösche Zeichen 40 bis 47" ergibt nur Sinn, wenn die vorigen Änderungen alle noch stehen. Nimmt man die dritte von fünf Änderungen heraus, zeigen die beiden jüngeren auf Stellen, die es so nicht mehr gibt. Rückwärts, in umgekehrter Reihenfolge, kann dagegen nichts schiefgehen — und rückwärts heißt: oben vom Stapel.

Der Aufrufstapel

Denselben Stapel benutzt jedes Programm, ohne dass es jemand hinschreibt. Ruft eine Funktion eine andere auf, legt die Maschine einen Rahmen oben auf den Aufrufstapel: die lokalen Variablen und die Adresse, an der es nach dem return weitergeht. Das return nimmt den Rahmen wieder herunter.

function fakultaet(n) {
  if (n <= 1) return 1;
  return n * fakultaet(n - 1);
}

Beim Aufruf fakultaet(4) liegen kurzzeitig vier Rahmen übereinander. Erst wenn der oberste mit 1 zurückkommt, kann der darunter rechnen, und so weiter nach unten.

Woran man einen Stapel erkennt

Das Muster ist immer dasselbe: Etwas wird geöffnet und muss geschlossen werden, bevor das Umgebende schließen darf. Klammern in einem Ausdruck sind der kürzeste Fall. Ein Prüfer legt jede öffnende Klammer auf einen Stapel; bei jeder schließenden nimmt er die oberste herunter und sieht nach, ob sie zu ihr passt. Bleibt am Ende etwas liegen, fehlt eine schließende Klammer; findet er nichts zum Herunternehmen, steht eine zu viel da. ([)] fällt genau daran durch.

Bleibt die Frage, warum man für Rückgängig überhaupt eine eigene Struktur nennt, wo ein Array doch alles kann. Es kann alles, aber nicht überall gleich billig. Am Ende anhängen und am Ende wegnehmen kostet einen Handgriff. In der Mitte einfügen kostet so viele Handgriffe, wie dahinter noch Zellen liegen.