Stapel (Stacks)

Zu prüfen, ob die Klammern in {[()()]} richtig zusammenpassen, braucht einen Stapel und 8 Push- und Pop-Vorgänge, einen für jede Klammer.

Last in, first out

Denk an einen Tellerstapel. Einen sauberen Teller legst du oben drauf, und wenn du einen brauchst, nimmst du ihn von oben. Der zuletzt hinzugefügte Teller kommt als Erster heraus. Ein Stapel (Stack, Kellerspeicher) ist eine Datenstruktur mit genau dieser Regel, genannt last in, first out (LIFO). Er bietet zwei Hauptoperationen: push legt einen Wert oben drauf, und pop entfernt den obersten Wert und gibt ihn zurück. Viele Stapel bieten außerdem peek, das sich den obersten Wert ansieht, ohne ihn zu entfernen.

In den Unterlagen von MIT 6.006 ist der Stapel ein Spezialfall der Sequenz-Schnittstelle: insert last(x) und delete last(). Das verrät schon, wie man einen baut. Leg die Werte in ein dynamisches Array und behandle das Ende des Arrays als Spitze. In der letzten Einheit war das Ende das billige Ende, also kosten push und pop je 1 Schritt (amortisiert, wegen der gelegentlichen Kopie). Die Größe des Stapels spielt keine Rolle. Ein Pop von einem Stapel mit 3 Werten oder mit 3 Millionen Werten ist derselbe einzelne Schritt.

const stack = [];
stack.push(4);
stack.push(8);
stack.push(5);
console.log(stack.pop());           // 5, der zuletzt hineingelegte
console.log(stack[stack.length - 1]); // peek: 8
console.log(stack.length);          // 2

Klammern prüfen

Eine klassische Anwendung für einen Stapel ist die Prüfung, ob Klammern ausgeglichen sind, und genau das tut jeder Code-Editor und jeder Compiler. Lies den Text von links nach rechts. Jede öffnende Klammer, (, [ oder {, kommt per push auf den Stapel. Jede schließende Klammer muss zur öffnenden oben auf dem Stapel passen: Wenn ja, wird diese per pop entfernt. Ist der Stapel leer oder liegt oben eine andere Sorte, ist die Folge nicht ausgeglichen. Am Ende muss der Stapel leer sein, sonst wurde eine Klammer nie geschlossen.

Probier die Folgen im Labor. {[()()]} braucht 4 Pushs und 4 Pops, 8 Schritte, und endet mit einem leeren Stapel. ([)] scheitert am dritten Zeichen: Die ) kommt, während [ oben liegt. (() wird bis zum Ende gelesen, und eine ( bleibt übrig. Warum passt ein Stapel zu dieser Aufgabe? Klammern sind verschachtelt, und die zuletzt geöffnete muss als Erste geschlossen werden. Das ist last in, first out.

Wo Stapel sonst vorkommen

• Der Aufrufstapel. Wenn Funktion a die Funktion b aufruft und b die Funktion c, legt der Computer für jeden Aufruf einen Eintrag ab. Wenn c zurückkehrt, wird sein Eintrag entfernt, und b macht dort weiter, wo es aufgehört hat. Endlose Rekursion füllt diesen Stapel, das ist der Fehler „Stack Overflow“.
• Rückgängig. Ein Editor legt jede Änderung auf einen Stapel. „Rückgängig“ nimmt die letzte Änderung herunter und macht sie rückgängig.
• Zurück-Taste. Ein Browser legt jede Seite ab, die du verlässt; „Zurück“ nimmt die letzte herunter.
• Tiefensuche. Der Algorithmenkurs hat einen Stapel benutzt, um in einem Labyrinth so tief wie möglich zu gehen, bevor er umkehrt.