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 hinzugefügt 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 erklärt
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 zugänglich, wenn alle darüber liegenden entfernt wurden. Genau so funktioniert ein Stack in der Programmierung.
Das Gegenstück zum Stack ist die Queue (Warteschlange), die nach dem FIFO-Prinzip (First In, First Out) arbeitet. Bei einer Queue wird das älteste Element zuerst entnommen - wie in einer Warteschlange an der Kasse.
Grundlegende Stack-Operationen
Ein Stack unterstützt typischerweise folgende Operationen, die alle eine Zeitkomplexität von O(1) haben - also konstant schnell sind, unabhängig von der Größe des Stacks:
| Operation | Beschreibung |
|---|---|
| push(element) | Legt ein neues Element oben auf den Stack |
| pop() | Entfernt das oberste Element und gibt es zurück |
| peek() / top() | Gibt das oberste Element zurück, ohne es zu entfernen |
| isEmpty() | Prüft, ob der Stack leer ist |
| size() | Gibt die Anzahl der Elemente zurück |
Bei einem leeren Stack führt ein pop()-Aufruf zu einem Fehler (Stack Underflow). Ebenso kann bei einem Stack mit fester Größe 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 über Arrays oder Listen.
Stack in Java
Java bietet die Klasse java.util.Stack, wobei für 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 hinzufügen
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 Rücksprungadresse auf den Stack gelegt. Nach Beendigung der Funktion wird diese Adresse vom Stack genommen, um zur aufrufenden Stelle zurückzukehren. Das ermöglicht 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 Rückgängig-Funktion in Texteditoren, Grafikprogrammen oder IDEs basiert typischerweise auf einem Stack. Jede Aktion wird auf den Stack gelegt. Bei "Rückgängig" wird die letzte Aktion vom Stack genommen und invertiert ausgeführt.
Browser-Verlauf
Der Zurück-Button im Browser nutzt ebenfalls das Stack-Prinzip. Jede besuchte Seite wird auf einen Stack gelegt. Wenn du "Zurück" klickst, wird die aktuelle Seite vom Stack genommen und zur vorherigen navigiert.
Klammerung und Syntax-Prüfung
Compiler und Parser verwenden Stacks, um die korrekte Klammerung in Code zu überprüfen. Bei einer öffnenden Klammer wird diese auf den Stack gelegt, bei einer schließenden 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 Ausdrücken
Die Auswertung arithmetischer Ausdrücke (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 für lokale Variablen und Funktionsaufrufe verwendet und ist automatisch verwaltet. Der Heap hingegen dient für dynamisch allokierte Objekte.
| Aspekt | Stack-Speicher | Heap-Speicher |
|---|---|---|
| Verwaltung | Automatisch (LIFO) | Manuell oder via Garbage Collector |
| Geschwindigkeit | Sehr schnell | Langsamer |
| Größe | Begrenzt (Stack Overflow möglich) | Größer, 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 erschöpft ist - typischerweise durch zu tiefe Rekursion oder sehr grosse lokale Datenstrukturen.
Stack in der Praxis
Als Fachinformatiker für Anwendungsentwicklung begegnen dir Stacks regelmäßig. Beim Debugging siehst du den Call Stack, um nachzuvollziehen, welche Funktionsaufrufe zu einem Fehler geführt 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.