Stack mit Doubly Linked List

Aufgabe

Ein Stack ist eine Datenstruktur nach dem LIFO-Prinzip (Last In, First Out).
In dieser Aufgabe sollen Sie auf Basis einer doppelt verketteten Liste (engl. doubly linked list) einen Stack implementieren, sodass die folgenden Operationen möglich sind:

  1. Elemente auf den Stack legen (push)
  2. Das oberste Element entfernen (pop)
  3. Das oberste Element abfragen (top)
  4. Prüfen, ob der Stack leer ist (is_empty)
  5. Den gesamten Stack ausgeben (print_stack)
  6. Den gesamten Stack löschen (clear_stack)
  7. Ein Kommandozeilen-Menü, über das der Benutzer diese Operationen auswählen kann.

Ziel dieser Aufgabe ist es, bestehende Funktionen der Doubly Linked List wiederzuverwenden, Zeigeroperationen, dynamische Speicherverwaltung (malloc, free) und Datenstrukturdesign zu üben.

Aufgabenmaterial

Für diese Aufgabe werden Sie ein von uns zur Verfügung gestelltes Codegerüst vervollständigen.

Codegerüst
#include <cs50.h>
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

int main(void)
{
    printf(
        "(1) push (Element auf Stack legen)\n"
        "(2) Stack ausgeben\n"
        "(3) pop (oberstes Element entfernen)\n"
        "(4) top (oberstes Element anzeigen)\n"
        "(5) Stack löschen\n"
        "(0) Programm beenden\n"
    );

    while (true)
    {
        int choice = get_int("> ");

        switch (choice)
        {
            case 1:
            // Zahl einfügen
                break;
            case 2:
            // Stack ausgeben
                break;
            case 3:
            // oberstes Element entfernen
                break;
            case 4:
            // oberstes Element anzeigen
                break;
            case 5:
            // Stack leeren
                break;
            case 0:
            // Stack leeren & Programm beenden
                return 0;
            default:
                printf("Ungültige Auswahl.\n");
        }
    }
}

Anforderungen

Sie sollen ein vollständiges C-Programm selbst entwickeln, das die folgenden Punkte erfüllt.

1. Strukturdefinition

Definieren Sie eine Struktur node, die wie folgt aufgebaut ist:

typedef struct node
{
    int value;
    struct node *next;
    struct node *prev;
} node;

2. Der Benutzer soll über ein Menü verschiedene Operationen auswählen können 

(1) push (Element auf Stack legen)
(2) Stack ausgeben
(3) pop (oberstes Element entfernen)
(4) top (oberstes Element anzeigen)
(5) Stack löschen
(0) Programm beenden

Das Menü wird nur einmal beim Programmstart ausgegeben.

3. Push

Beim Einfügen eines neuen Wertes auf den Stack müssen Sie:

  • Speicher für einen neuen Knoten mit malloc() anfordern
  • value, prev und next korrekt setzen
  • Unterscheiden, ob der Stack leer ist oder nicht
void push(int value);

4. Pop

Beim Entfernen des obersten Elements müssen Sie:

  • Prüfen, ob der Stack leer ist
  • Den obersten Knoten entfernen
  • Kopf/Ende korrekt anpassen
  • Speicher mit free() freigeben
void pop(void);

5. Top

Beim Abfragen des obersten Elements müssen Sie:

  • Prüfen, ob der Stack leer ist
  • Den Wert des obersten Elements zurückgeben
int top(void);

6. Prüfen, ob der Stack leer ist 

bool is_empty(void);

true, falls stack leer, sonst false

7. Stack ausgeben

Ausgabe von oben nach unten (Tail → Head)

void print_stack(void);

8. Stack löschen

Den gesamten Stack freigeben, keine Memory Leaks Kopf und Tail auf NULL setzen

void clear_stack(void);

9. Beispielinteraktion

1
Zahl: 5

1
Zahl: 9

2
Stack (oben -> unten): 9 5

3
Pop: 9

4
Top: 5

5
Stack geleert.

0
Programm beendet.

Doubly Linked Lists