Datenstruktur - Stack

Ein Stack ist eine lineare Datenstruktur, die dem Last-In-First-Out-Prinzip (LIFO) folgt. Man kann ihn sich anschaulich als einen Stapel Teller vorstellen – man kann nur oben einen ablegen und nur von oben einen entnehmen.

Stack-Konzept und Prinzip

Stack — Illustration des LIFO-Prinzips

Oben — Operationen können nur hier ausgeführt werden

Teller 1 (Unten)

Teller 2

Teller 3

Teller 4 (Oben)

Unten — kann nur zuletzt entfernt werden

▲ push ▼ pop

LIFO-Überprüfung: push 10→20→30, pop 30→20→10 (zuletzt hinein, zuerst heraus) | Der Stack kümmert sich nur um das oberste Element, nicht um die Mitte

Array-Implementierung (sequenzieller Stack)

Speicherung: Array fester Größe + top-Zeiger

push：items[++top] = value

pop：return items[top--]

Vorteile: schneller Zugriff, cache-freundlich, einfache Implementierung

Nachteile: feste Kapazität, kann überlaufen

Implementierung mit verketteter Liste (verketteter Stack)

Speicherung: dynamische Knoten + top-Zeiger (Kopf der verketteten Liste)

push: Kopf-Einfügemethode newNode->next = top

pop: top = top->next; free(old head)

Vorteile: keine Kapazitätsbegrenzung, flexible dynamische Erweiterung

Nachteile: zusätzlicher Zeiger-Overhead, cache-unfreundlich

Array-Implementierung eines Stacks

Beispiel

#include <stdio.h>
#include <stdbool.h> /* bool-Typ */

#define MAX_SIZE 100 /* Maximale Kapazität des Stacks */

/* Stack-Struktur: enthält Datenarray und Top-Zeiger */
struct Stack {
int items[MAX_SIZE]; /* Array, das Stack-Elemente speichert */
int top; /* Top-Zeiger, -1 bedeutet, dass der Stack leer ist */
};

/* Stack initialisieren: top auf -1 setzen */
void initStack(struct Stack* s) {
s->top = -1;
}

/* Auf Leerheit prüfen: Stack ist leer, wenn top -1 ist */
bool isEmpty(struct Stack* s) {
return s->top == -1;
}

/* Prüfen, ob voll: Der Stack ist voll, wenn top die Kapazitätsgrenze -1 erreicht */
bool isFull(struct Stack* s) {
return s->top == MAX_SIZE - 1;
}

/* Push: ein Element oben auf den Stack legen
Zuerst top verschieben, dann die Daten schreiben */
void push(struct Stack* s, int value) {
if (isFull(s)) {
printf("Stack ist voll, kann nicht pushen!\n");
return;
}
s->items[++s->top] = value; /* top wird zuerst um 1 erhöht, dann wird value zugewiesen */
printf("Push: %d\n", value);
}

/* Pop: das oberste Element entfernen und zurückgeben
Zuerst die Daten abrufen, dann top verschieben */
int pop(struct Stack* s) {
if (isEmpty(s)) {
printf("Der Stapel ist leer, pop ist nicht möglich!\n");
return -1; /* Gibt einen speziellen Wert zurück, um einen Fehler anzuzeigen */
}
return s->items[s->top--]; /* Zuerst den Wert zurückgeben, dann top dekrementieren */
}

/* Peek: entnimmt nicht, betrachtet nur das oberste Element */
int peek(struct Stack* s) {
if (isEmpty(s)) {
printf("Der Stapel ist leer!\n");
return -1;
}
return s->items[s->top];
}

int main() {
struct Stack s;
initStack(&s);

push(&s, 10); /* Push: 10 */
push(&s, 20); /* Push: 20 */
push(&s, 30); /* Push: 30 */

printf("Top element: %d\n", peek(&s)); /* Ausgabe: oberstes Element: 30 */

printf("Pop: %d\n", pop(&s)); /* Ausgabe: pop: 30 (zuletzt rein, zuerst raus) */
printf("Pop: %d\n", pop(&s)); /* Ausgabe: pop: 20 */
printf("Pop: %d\n", pop(&s)); /* Ausgabe: pop: 10 */

if (isEmpty(&s)) {
printf("Stack is empty\n"); /* Ausgabe: Stack ist leer */
}
return 0;
}

Implementierung eines Stacks mit verketteter Liste

Beispiel

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

/* Knoten der verketteten Liste */
struct Node {
int data;
struct Node* next;
};

/* Push: verwendet den Kopf der verketteten Liste als oberstes Stack-Element, Einfügen am Kopf
Zeitkomplexität: O(1) */
struct Node* push(struct Node* top, int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->next = top; /* Neuer Knoten zeigt auf das ursprüngliche oberste Stack-Element */
printf("Push: %d\n", value);
return newNode; /* Der neue Knoten wird zur neuen Stapelspitze */
}

/* Pop: den Kopfknoten der verketteten Liste entfernen
Zeitkomplexität: O(1) */
struct Node* pop(struct Node* top) {
if (top == NULL) {
printf("Der Stapel ist leer!\n");
return NULL;
}
struct Node* temp = top;
printf("Entfernt: %d\n", top->data);
top = top->next; /* Top zurücksetzen */
free(temp); /* Alten obersten Knoten freigeben */
return top;
}

/* Prüfen, ob leer */
bool isEmpty(struct Node* top) {
return top == NULL;
}

int main() {
struct Node* stackTop = NULL; /* Zu Beginn ist der Stapel leer */

stackTop = push(stackTop, 100); /* Push: 100 */
stackTop = push(stackTop, 200); /* Push: 200 */
stackTop = push(stackTop, 300); /* Push: 300 */

printf("Spitze: %d\n", stackTop->data); /* Ausgabe: Spitze: 300 */

stackTop = pop(stackTop); /* Pop: 300 */
stackTop = pop(stackTop); /* Pop: 200 */
stackTop = pop(stackTop); /* Pop: 100 */

if (isEmpty(stackTop)) {
printf("Stack ist leer\n"); /* Ausgabe: Stack ist leer */
}
return 0;
}

Der Vorteil der Implementierung eines Stacks mit einer verketteten Liste besteht darin, dass es theoretisch keine feste Kapazitätsgrenze gibt, die nur durch den verfügbaren Speicher des Systems begrenzt ist. Allerdings benötigt jeder Knoten zusätzlichen Speicherplatz für Zeiger.

Stack-Anwendungsszenarien

Anwendungsszenarien	Beschreibung	Warum Stack verwenden
Funktionsaufruf-Stack	Rücksprungadressen und lokale Variablen von Funktionen speichern	Funktionsaufrufe sind verschachtelt, natürlich LIFO
Klammerabgleich	Prüfen, ob Klammern im Code korrekt gepaart sind	Linke Klammer auf den Stack legen, rechte Klammer entfernen, wenn sie mit dem oberen Element des Stacks übereinstimmt
Rückgängig-Operation	Rückgängig-Funktion in Texteditoren und Browsern	Jede Operation wird auf den Stack gelegt und beim Rückgängigmachen entfernt
Ausdrucksauswertung	Infix-/Postfix-Ausdrücke auswerten	Operanden werden auf den Stack gelegt, das Ergebnis wird nach der Operatorberechnung auf den Stack gelegt
Tiefensuche	DFS-Traversierungsalgorithmus für Graphen	Explizit Stack oder Rekursion verwenden (implizit unter Verwendung des Call-Stacks)

Weitere Erweiterungen