Stack
Stack (deutsch: Stapel oder Kellerspeicher) ist eine fundamentale Datenstruktur in der Informatik, die nach dem LIFO-Prinzip (Last In, First Out) arbeitet. Das bedeutet: Das Element, das zuletzt hinzugefuegt wurde, wird als erstes wieder entnommen. Stacks sind ein grundlegendes Konzept, das du in nahezu jeder Programmiersprache und vielen Anwendungsbereichen antreffen wirst.
Das LIFO-Prinzip anschaulich erklaert
Stell dir einen Stapel Teller vor: Du kannst nur oben einen neuen Teller auflegen und auch nur den obersten Teller wieder herunternehmen. Die Teller darunter sind erst zugaenglich, wenn alle darueber liegenden entfernt wurden. Genau so funktioniert ein Stack in der Programmierung.
Das Gegenstueck zum Stack ist die Queue (Warteschlange), die nach dem FIFO-Prinzip (First In, First Out) arbeitet. Bei einer Queue wird das aelteste Element zuerst entnommen - wie in einer Warteschlange an der Kasse.
Grundlegende Stack-Operationen
Ein Stack unterstuetzt typischerweise folgende Operationen, die alle eine Zeitkomplexitaet von O(1) haben - also konstant schnell sind, unabhaengig von der Groesse des Stacks:
| Operation | Beschreibung |
|---|---|
| push(element) | Legt ein neues Element oben auf den Stack |
| pop() | Entfernt das oberste Element und gibt es zurueck |
| peek() / top() | Gibt das oberste Element zurueck, ohne es zu entfernen |
| isEmpty() | Prueft, ob der Stack leer ist |
| size() | Gibt die Anzahl der Elemente zurueck |
Bei einem leeren Stack fuehrt ein pop()-Aufruf zu einem Fehler (Stack Underflow). Ebenso kann bei einem Stack mit fester Groesse ein push() auf einen vollen Stack einen Stack Overflow verursachen.
Stack-Implementierung in verschiedenen Sprachen
Die meisten Programmiersprachen bieten entweder eine eingebaute Stack-Klasse oder ermöglichen eine einfache Implementierung ueber Arrays oder Listen.
Stack in Java
Java bietet die Klasse java.util.Stack, wobei fuer moderne Anwendungen oft Deque als Stack-Implementierung empfohlen wird:
import java.util.Stack;
public class StackBeispiel {
public static void main(String[] args) {
Stack<String> stack = new Stack<>();
// Elemente auf den Stack legen
stack.push("Erster");
stack.push("Zweiter");
stack.push("Dritter");
// Oberstes Element ansehen (ohne Entfernen)
System.out.println("Top: " + stack.peek()); // Dritter
// Elemente vom Stack nehmen
while (!stack.isEmpty()) {
System.out.println(stack.pop());
}
// Ausgabe: Dritter, Zweiter, Erster
}
}
Stack in Python
In Python kannst du eine Liste als Stack verwenden. Die Methoden append() und pop() entsprechen den Stack-Operationen:
# Liste als Stack verwenden
stack = []
# push - Element hinzufuegen
stack.append("Erster")
stack.append("Zweiter")
stack.append("Dritter")
# peek - oberstes Element ansehen
print(f"Top: {stack[-1]}") # Dritter
# pop - oberstes Element entfernen
while stack:
print(stack.pop())
# Ausgabe: Dritter, Zweiter, Erster
Stack in C#
C# stellt die generische Klasse Stack<T> im Namespace System.Collections.Generic bereit:
using System;
using System.Collections.Generic;
Stack<string> stack = new Stack<string>();
stack.Push("Erster");
stack.Push("Zweiter");
stack.Push("Dritter");
Console.WriteLine($"Top: {stack.Peek()}"); // Dritter
while (stack.Count > 0)
{
Console.WriteLine(stack.Pop());
}
// Ausgabe: Dritter, Zweiter, Erster
Praktische Anwendungsgebiete
Stacks begegnen dir in vielen Bereichen der Softwareentwicklung - oft auch dort, wo du es nicht direkt siehst:
Call Stack bei Funktionsaufrufen
Der Call Stack ist einer der wichtigsten Anwendungsfaelle. Wenn eine Funktion eine andere aufruft, wird die Ruecksprungadresse auf den Stack gelegt. Nach Beendigung der Funktion wird diese Adresse vom Stack genommen, um zur aufrufenden Stelle zurueckzukehren. Das ermoeglicht auch Rekursion - Funktionen, die sich selbst aufrufen.
// Rekursive Fakultaetsberechnung nutzt den Call Stack
public static int fakultaet(int n) {
if (n <= 1) return 1;
return n * fakultaet(n - 1);
}
// fakultaet(4) ruft fakultaet(3) auf, das ruft fakultaet(2) auf, usw.
// Die Rueckgabewerte werden dann in umgekehrter Reihenfolge verarbeitet
Undo-Funktionalitaet
Die Rueckgaengig-Funktion in Texteditoren, Grafikprogrammen oder IDEs basiert typischerweise auf einem Stack. Jede Aktion wird auf den Stack gelegt. Bei "Rueckgaengig" wird die letzte Aktion vom Stack genommen und invertiert ausgefuehrt.
Browser-Verlauf
Der Zurueck-Button im Browser nutzt ebenfalls das Stack-Prinzip. Jede besuchte Seite wird auf einen Stack gelegt. Wenn du "Zurueck" klickst, wird die aktuelle Seite vom Stack genommen und zur vorherigen navigiert.
Klammerung und Syntax-Pruefung
Compiler und Parser verwenden Stacks, um die korrekte Klammerung in Code zu ueberpruefen. Bei einer oeffnenden Klammer wird diese auf den Stack gelegt, bei einer schliessenden Klammer wird geprueft, ob sie zur obersten Klammer auf dem Stack passt:
def klammern_gueltig(ausdruck):
stack = []
paare = {')': '(', ']': '[', '}': '{'}
for zeichen in ausdruck:
if zeichen in '([{':
stack.append(zeichen)
elif zeichen in ')]}':
if not stack or stack.pop() != paare[zeichen]:
return False
return len(stack) == 0
print(klammern_gueltig("((a+b)*c)")) # True
print(klammern_gueltig("((a+b)*c")) # False
print(klammern_gueltig("([a+b])*c)")) # False
Auswertung von Ausdruecken
Die Auswertung arithmetischer Ausdruecke (Infix zu Postfix, Postfix-Auswertung) nutzt Stacks. Der Shunting-Yard-Algorithmus von Dijkstra wandelt beispielsweise Infix-Notation (3 + 4) in Postfix-Notation (3 4 +) um - beides unter Verwendung von Stacks.
Stack vs. Heap
In der Speicherverwaltung unterscheidet man zwischen Stack-Speicher und Heap-Speicher. Der Stack-Speicher wird fuer lokale Variablen und Funktionsaufrufe verwendet und ist automatisch verwaltet. Der Heap hingegen dient fuer dynamisch allokierte Objekte.
| Aspekt | Stack-Speicher | Heap-Speicher |
|---|---|---|
| Verwaltung | Automatisch (LIFO) | Manuell oder via Garbage Collector |
| Geschwindigkeit | Sehr schnell | Langsamer |
| Groesse | Begrenzt (Stack Overflow moeglich) | Groesser, flexibel |
| Lebensdauer | Endet mit Funktionsende | Explizit oder via GC |
| Typische Nutzung | Lokale Variablen, Parameter | Objekte, dynamische Arrays |
Ein Stack Overflow tritt auf, wenn der Stack-Speicher erschoepft ist - typischerweise durch zu tiefe Rekursion oder sehr grosse lokale Datenstrukturen.
Stack in der Praxis
Als Fachinformatiker fuer Anwendungsentwicklung begegnen dir Stacks regelmaessig. Beim Debugging siehst du den Call Stack, um nachzuvollziehen, welche Funktionsaufrufe zu einem Fehler gefuehrt haben. Bei der Entwicklung von Parsern, Compilern oder Interpretern sind Stacks unverzichtbar. Auch bei Algorithmen wie der Tiefensuche (Depth-First Search) in Graphen kommt das Stack-Prinzip zum Einsatz.