Generischer Stack

Teil des Abschnitts Object Oriented Programming der C-Journey von Coddy — Lektion 60 von 61.

Aufgabe

Einfach

Ein Stack (Stapel) ist eine grundlegende Datenstruktur, die dem Last-In-First-Out (LIFO)-Prinzip folgt — das letzte hinzugefügte Element wird als erstes wieder entfernt. Denken Sie an einen Stapel Teller: Sie legen oben einen Teller auf und nehmen ihn auch von oben wieder weg.

Lassen Sie uns einen Generic Stack bauen — eine vielseitige Datenstruktur, die mithilfe von void*-Pointern jeden Datentyp speichern kann. Ihr Stack wird dem Last-In-First-Out-Prinzip folgen und alle wesentlichen Operationen enthalten.

Sie werden Ihren Code auf drei Dateien verteilen:

stack.h: Definieren Sie das Stack-Struct mit drei Membern: ein void**-Array für die Elemente, ein int für den Top-Index (nächster freier Platz) und ein int für die Kapazität. Deklarieren Sie Funktionsprototypen zum Erstellen eines Stacks (nimmt eine Kapazität entgegen), zum Hinzufügen eines Elements (push), zum Entfernen eines Elements (pop), zum Ansehen des obersten Elements (peek), zum Überprüfen, ob der Stack leer ist, und zum Freigeben des Stacks.
stack.c: Implementieren Sie Ihren generischen Stack:
- create_stack — alloziert einen Stack auf dem Heap, alloziert das items-Array mit der angegebenen Kapazität, initialisiert top auf 0 und gibt den Pointer zurück
- push — fügt ein Element oben hinzu, wenn noch Platz ist (wenn top kleiner als capacity ist)
- pop — entfernt das oberste Element und gibt es zurück, oder gibt NULL zurück, wenn der Stack leer ist
- peek — gibt das oberste Element zurück, ohne es zu entfernen, oder NULL, wenn der Stack leer ist
- is_empty — gibt 1 zurück, wenn der Stack keine Elemente enthält, andernfalls 0
- free_stack — gibt zuerst das items-Array frei und dann das Stack-Struct selbst
main.c: Lesen Sie die Anzahl der auszuführenden Operationen ein. Lesen Sie dann für jede Operation einen Befehl ein: push gefolgt von einem ganzzahligen Wert, pop oder peek. Erstellen Sie einen Stack mit der Kapazität 10. Für push allozieren Sie einen Integer auf dem Heap und pushen dessen Pointer. Für pop rufen Sie das Element ab, geben seinen Wert aus und geben den Integer frei. Für peek geben Sie den Wert aus, ohne ihn zu entfernen. Wenn pop oder peek auf einem leeren Stack aufgerufen werden, geben Sie empty aus. Geben Sie nach allen Operationen alle verbleibenden Elemente und den Stack frei.

Ihr Programm erhält:

Die Anzahl der Operationen
Jede Operation in einer separaten Zeile (push X, pop oder peek)

Beispielhafte Ausgabe, wenn die Eingaben 5, dann push 10, push 20, peek, pop, pop sind:

20
20
10

Beispielhafte Ausgabe, wenn die Eingaben 3, dann pop, push 42, peek sind:

empty
42

Beispielhafte Ausgabe, wenn die Eingaben 4, dann push 5, push 15, pop, pop sind:

15
5

Denken Sie daran, dass Ihr Stack void*-Pointer speichert — der Aufrufer ist für das Allozieren und Freigeben der eigentlichen Daten verantwortlich. Casten Sie beim Poppen den zurückgegebenen void* zurück in einen int*, um auf den Wert zuzugreifen. Verwenden Sie strcmp aus <string.h>, um Befehls-Strings zu vergleichen.

Probier es selbst

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "stack.h"

int main() {
    int n;
    scanf("%d", &n);
    
    // TODO: Erstelle einen Stack mit einer Kapazität von 10
    
    // TODO: Verarbeite jede Operation
    for (int i = 0; i < n; i++) {
        char command[10];
        scanf("%s", command);
        
        if (strcmp(command, "push") == 0) {
            int value;
            scanf("%d", &value);
            // TODO: Reserviere einen Integer auf dem Heap und pushe seinen Pointer
        }
        else if (strcmp(command, "pop") == 0) {
            // TODO: Entferne das Element (pop)
            // - Wenn nicht NULL, gib den Wert aus und gib den Integer frei
            // - Wenn NULL (leerer Stack), gib "empty" aus
        }
        else if (strcmp(command, "peek") == 0) {
            // TODO: Sieh dir das oberste Element an (peek)
            // - Wenn nicht NULL, gib den Wert aus (nicht entfernen oder freigeben)
            // - Wenn NULL (leerer Stack), gib "empty" aus
        }
    }
    
    // TODO: Gib alle verbleibenden Elemente im Stack frei
    // TODO: Gib den Stack selbst frei
    
    return 0;
}