Generischer Stack

Teil des Abschnitts Objektorientierte Programmierung der C-Journey von Coddy. Lektion 60 von 61.

Aufgabe

Einfach

Ein Stack ist eine grundlegende Datenstruktur, die dem Last-In-First-Out-(LIFO)-Prinzip folgt: Das zuletzt hinzugefügte Element wird als Erstes entfernt. Stell dir einen Tellerstapel vor: Du fügst oben etwas hinzu und entfernst es auch von oben.

Wir erstellen einen Generic Stack: eine vielseitige Datenstruktur, die mithilfe von void*-Zeigern jeden Datentyp speichern kann. Dein Stack folgt dem Last-In-First-Out-Prinzip und enthält alle wesentlichen operation.

Du organisierst deinen Code über drei Dateien:

stack.h: Define die Stack-Struktur mit drei members: einem void**-array für items, einem int für den top index (next free slot) und einem int für capacity. Declare function-Prototypen zum Erstellen eines Stacks (nimmt eine capacity entgegen), zum Hinzufügen eines item, zum Entfernen eines item, zum Anzeigen des obersten item, zum Prüfen, ob der Stack empty ist, und zum Freigeben des Stacks.
stack.c: Implement deinen generischen Stack:
- create_stack: reserviert einen Stack auf dem heap, reserviert das items-array mit der given capacity, initialisiert top mit 0 und gibt den pointer zurück
- push: fügt ein item oben hinzu, wenn Platz vorhanden ist (wenn top kleiner als capacity ist)
- pop: entfernt das oberste item und gibt es zurück oder gibt NULL zurück, wenn der Stack empty ist
- peek: gibt das oberste item zurück, ohne es zu entfernen, oder NULL, wenn der Stack empty ist
- is_empty: gibt 1 zurück, wenn der Stack keine items hat, andernfalls 0
- free_stack: gibt zuerst das items-array und anschließend die Stack-Struktur selbst frei
main.c: Lies die Anzahl der auszuführenden operation. Lies anschließend für jede operation ein command: push gefolgt von einem integer value, pop oder peek. Erstelle einen Stack mit capacity 10. Für push reserviere einen integer auf dem heap und füge dessen pointer hinzu. Für pop hole das item, gib dessen value aus und gib den integer frei. Für peek gib den value aus, ohne ihn zu entfernen. Wenn pop oder peek auf einem empty Stack aufgerufen wird, gib empty aus. Gib nach allen operation die verbleibenden items und den Stack frei.

Dein Programm erhält:

Die Anzahl der operation
Jede operation in einer eigenen Zeile (push X, pop oder peek)

Beispielausgabe, wenn die Eingaben 5, anschließend push 10, push 20, peek, pop, pop sind:

20
20
10

Beispielausgabe, wenn die Eingaben 3, anschließend pop, push 42, peek sind:

empty
42

Beispielausgabe, wenn die Eingaben 4, anschließend push 5, push 15, pop, pop sind:

15
5

Denke daran, dass dein Stack void*-pointer speichert: Der Aufrufer ist dafür verantwortlich, die eigentlichen Daten zu reservieren und freizugeben. Wandle beim Entfernen den zurückgegebenen void* zurück in int* um, um auf den value zuzugreifen. Verwende strcmp aus <string.h>, um command-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 Kapazität 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: Allokiere einen Integer auf dem Heap und pushe seinen Zeiger
        }
        else if (strcmp(command, "pop") == 0) {
            // TODO: Poppe das Element
            // - Wenn nicht NULL, Wert ausgeben und den Integer freigeben
            // - Wenn NULL (leerer Stack), "empty" ausgeben
        }
        else if (strcmp(command, "peek") == 0) {
            // TODO: Peeke auf das oberste Element
            // - Wenn nicht NULL, Wert ausgeben (nicht entfernen oder freigeben)
            // - Wenn NULL (leerer Stack), "empty" ausgeben
        }
    }
    
    // TODO: Gib alle verbleibenden Elemente im Stack frei
    // TODO: Gib den Stack selbst frei
    
    return 0;
}