Stack mit Doubly Linked List

Aufgabe

So funktioniert ein Stack auf einer doppelt verketteten Liste

1. Stapel: Ein Stack funktioniert nach dem LIFO-Prinzip (Last In, First Out): Was zuletzt hineinkommt, kommt als Erstes wieder heraus. Zugänglich ist immer nur das oberste Element.
2. Oben = tail: Das oberste Element ist der letzte Knoten der Liste (tail), das unterste der erste (head). Ein leerer Stack ist eine leere Liste: head und tail sind NULL.
3. push: legt eine Zahl oben auf den Stack, also ans Ende der Liste – genau wie insert_end in der vorigen Aufgabe: neuer Knoten mit prev = tail und next = NULL; der bisher oberste Knoten zeigt mit next auf ihn (bei leerem Stack stattdessen head); danach zeigt tail auf ihn.
4. pop: entfernt den obersten Knoten. tail rückt über prev auf den Knoten darunter; dessen next wird NULL. War es der einzige Knoten, werden head und tail NULL. Danach wird der entfernte Knoten mit free freigegeben. Weil jeder Knoten seinen Vorgänger kennt, muss pop dafür nicht die ganze Liste durchlaufen.
5. top: liefert den Wert des obersten Knotens (tail->value), ohne etwas zu ändern.
6. Ausgabe: von oben nach unten, also von tail über prev bis NULL.

Beispiel: Nach push 5, push 9 und push 2 sieht die Liste so aus (head → 5, tail → 2):

Der Stack von oben nach unten ist 2 9 5. pop entfernt 2: tail zeigt jetzt auf 9, next von 9 wird NULL, Knoten 2 wird freigegeben.

Jetzt liefert top den Wert 9, und der Stack von oben nach unten ist 9 5.

Demo

So sieht ein Lauf des fertigen Programms aus (hinter > und den Fragen stehen die Eingaben):

$ ./stack
(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
> 1
Zahl: 5
> 1
Zahl: 9
> 2
Stack (oben -> unten): 9 5
> 3
Pop: 9
> 4
Top: 5
> 5
Stack geleert.
> 0
Programm beendet.

Aufgabenmaterial

Für diese Aufgabe werden Sie ein von uns zur Verfügung gestelltes Codegerüst vervollständigen. Legen Sie einen Ordner stack an und darin die Datei stack.c mit diesem Inhalt:

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

int main(void)
{
    // Menü nur einmal ausgeben
    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)
    {
        // Benutzerauswahl abfragen
        int choice = get_int("> ");

        // Operationen auswerten
        switch (choice)
        {
            case 1:
                // Zahl auf den Stack legen
                break;
            case 2:
                // Stack ausgeben
                break;
            case 3:
                // oberstes Element entfernen
                break;
            case 4:
                // oberstes Element anzeigen
                break;
            case 5:
                // gesamten Stack löschen
                break;
            case 0:
                // gesamten Stack löschen
                printf("Programm beendet.\n");
                return 0;
            default:
                printf("Ungültige Auswahl.\n");
        }
    }
}

Spezifikation

Datenstruktur. Definieren Sie dieselbe Struktur node wie in Doubly Linked Lists und zwei globale Pointer auf den ersten und den letzten Knoten:

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

node *head = NULL; // zeigt auf den ersten Knoten (unten)
node *tail = NULL; // zeigt auf den letzten Knoten (oben)

Funktionen. Die Funktionen geben selbst nur dort etwas aus, wo es in der Tabelle steht; alle anderen Meldungen gibt main aus.

Weil -1 auch ein gewöhnlicher Wert auf dem Stack sein kann, prüft main vor top und pop mit is_empty, ob der Stack leer ist.

Menü. main gibt das Menü einmal aus und fragt dann immer wieder mit > nach einer Auswahl:

Die Zahlen in der Ausgabe sind Beispiele; eingesetzt werden jeweils die Werte auf dem Stack.

Hilfestellung

Klicken Sie auf die folgenden Tipps, um einige Ratschläge zu erhalten. Versuchen Sie aber zunächst, selbst so weit wie möglich zu kommen.

node *tmp = tail;
tail = tail->prev;

Testen

Stellen Sie beim Testen Ihres Codes sicher, dass dieser mit folgenden Szenarien umgehen kann:

• Ausgabe, pop und top bei leerem Stack (Stack (oben -> unten): bzw. Stack ist leer.)
• mehrere push; die Ausgabe zeigt die zuletzt eingegebene Zahl zuerst
• pop bis zum letzten Element, danach erneut push – so fallen falsch gesetzte head- und tail-Pointer auf
• top ändert den Stack nicht: Zweimal hintereinander top liefert denselben Wert
• Löschen des gesamten Stacks (5) und danach erneutes push
• eine ungültige Menünummer

Korrektheit

Führen Sie in Ihrem Terminal den folgenden Befehl aus, um die Korrektheit Ihrer Arbeit zu überprüfen:

check50 -l inf-zone/exercises/2026/stack

Speicher

Ob Ihr Programm allen Speicher freigibt, zeigt valgrind (siehe Vorlesung 4). Legen Sie ein paar Zahlen auf den Stack, entfernen Sie einige und beenden Sie das Programm mit 0:

valgrind ./stack

Style

Führen Sie den folgenden Befehl aus, um den Stil Ihres Codes mit style50Prüfprogramm von CS50, das zeigt, wo Ihr Code von den Formatierungsregeln abweicht. In Grün zeigt es, was Sie ergänzen sollten, in Rot, was wegfallen soll. Glossar → zu analysieren:

style50 stack.c

Abgeben

Geben Sie im Ordner stack ab:

inf upload stack

Danach sehen Sie, welche Tests Ihr Programm besteht und ob die Übung für die Bonuspunkte zählt. Wie Sie inf installieren und sich anmelden, steht unter Abgeben mit inf.