CodeUtility
Mach dir das Coderleben leicht!
Datenstrukturen in C/C++

Die Datenstruktur Stapel (stack) in C und C++

In dieser Lektion implementierst du die Operationen eines Stapels nach dem Prinzip zuletzt hinein, zuerst heraus, mit einem festen Array in C und std::stack in C++.

Einführung

Ein Stapel (stack) erlaubt nur Operationen an der Spitze: push legt ein neues Element oben ab, pop nimmt das oberste Element herunter, und peek zeigt das oberste Element an, ohne es zu entfernen. Ein Stapel folgt dem Prinzip zuletzt hinein, zuerst heraus (LIFO), wie ein Bücherstapel.

Wichtige Punkte

  • Lege fest, welche Bedingungen in der Datenstruktur immer gelten müssen (Invarianten), bevor du die Operationen schreibst.
  • Behandle die Fälle leer, voll und fehlgeschlagene Speicherreservierung vollständig.
  • Bewerte bei jeder Operation Komplexität und Speicherverwaltung gemeinsam.

So funktioniert es

Mit push und pop siehst du, dass das zuletzt hineingelegte Element immer zuerst herauskommt.

Codebeispiele in C und C++

C
Code ausführen →
main.c
#include <stdio.h>

typedef struct {
    int data[8];
    int size;
} Stack;

int push(Stack *stack, int value) {
    if (stack->size == 8) return 0;
    stack->data[stack->size++] = value;
    return 1;
}

int pop(Stack *stack, int *value) {
    if (stack->size == 0) return 0;
    *value = stack->data[--stack->size];
    return 1;
}

int main(void) {
    Stack stack = {{0}, 0};
    int value;
    push(&stack, 10);
    push(&stack, 20);
    pop(&stack, &value);
    printf("%d\n", value);
}
Ergebnis der Ausführung
20
C++
Code ausführen →
main.cpp
#include <iostream>
#include <stack>

int main() {
    std::stack<int> values;
    values.push(10);
    values.push(20);
    std::cout << values.top() << '\n';
    values.pop();
}
Ergebnis der Ausführung
20

C und C++ im Vergleich

Die C-Version verwendet ein festes Array mit 8 Elementen und muss deshalb bei push prüfen, ob der Stapel voll ist (Stapelüberlauf), und bei pop, ob er leer ist. In C++ verwaltet std::stack die Kapazität über den darunterliegenden Container und bietet dieselben Operationen push, pop und top nach dem LIFO-Prinzip.

C

Daten (struct) und Operationen sind getrennt, und Speicher wird von Hand reserviert und freigegeben.

C++

Klassen und Container schützen die Korrektheit der Daten und verwalten ihre Ressourcen selbst.

Übungen zur Vertiefung

Führe beide Versionen aus und ändere dann den Code, um zu beobachten, welche Sicherheit jede Sprache bietet.

  • Ergänze Tests für den leeren Zustand und für das Erreichen der Kapazitätsgrenze.
  • Schreibe die Speicherfreigabe und prüfe auf Speicherlecks.
  • Vergleiche die Komplexität mit dem entsprechenden Container der Standardbibliothek.

Mit einer Challenge üben

Nutze den Inhalt dieser Lektion, um ein echtes Problem zu lösen. Jede Challenge läuft im Browser, mit sofortigen Tests und einem KI-Review.

Alle Challenges