# Stack mit Doubly Linked List Quelle: https://dev.inf.zone/exercises/09/stack/ ## Aufgabe **Auf einen Blick** - **Was:** Ein Programm, das einen Stack aus ganzen Zahlen verwaltet. Der Stack ist mit einer doppelt verketteten Liste umgesetzt wie in [Doubly Linked Lists](https://dev.inf.zone/exercises/09/doublylinkedlist/). Der Benutzer wählt die Operationen über ein Menü. - **Datei:** `stack.c` in einem Ordner `stack`. Ausgangspunkt ist das Codegerüst unten: Es enthält nur das Menü. - **Eingabe:** eine Menünummer (`> `), bei *push* danach eine Zahl. - **Ausgabe:** je nach Menüpunkt der Stack von oben nach unten, das entfernte oder das oberste Element. - **Ihre Arbeit:** die Struktur `node`, die Pointer `head` und `tail`, die sechs Funktionen `push`, `pop`, `top`, `is_empty`, `print_stack` und `clear_stack` sowie ihre Aufrufe in `main`. **Wozu das Ganze?** Sie verwenden die doppelt verkettete Liste aus der vorigen Aufgabe wieder, diesmal als Baustein für eine andere Datenstruktur. Dabei üben Sie erneut Pointer und dynamische Speicherverwaltung mit `malloc` und `free`. ### 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): | Knoten | `prev` | `next` | | ------ | ------ | ------ | | 5 | `NULL` | 9 | | 9 | 5 | 2 | | 2 | 9 | `NULL` | 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. | Knoten | `prev` | `next` | | ------ | ------ | ------ | | 5 | `NULL` | 9 | | 9 | 5 | `NULL` | 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): ```text $ ./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: **Codegerüst** ```c #include #include #include #include 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](https://dev.inf.zone/exercises/09/doublylinkedlist/) und zwei globale Pointer auf den ersten und den letzten Knoten: ```c 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. | Funktion | Aufgabe | | --------------------------- | ----------------------------------------------------------------------------------------------------------------------------------------------------------- | | `void push(int value)` | Legt mit `malloc` einen neuen Knoten an und hängt ihn ans Ende der Liste (Regel 3), auch wenn der Stack leer ist. | | `void pop(void)` | Entfernt den obersten Knoten und gibt ihn mit `free` frei (Regel 4). Ist der Stack leer, tut die Funktion nichts. | | `int top(void)` | Gibt den Wert des obersten Knotens zurück, ohne den Stack zu ändern. Ist der Stack leer, gibt sie `-1` zurück. | | `bool is_empty(void)` | Gibt `true` zurück, wenn der Stack leer ist, sonst `false`. | | `void print_stack(void)` | Gibt `Stack (oben -> unten): ` aus, dann die Werte von `tail` bis `head`, durch Leerzeichen getrennt, dann einen Zeilenumbruch. | | `void clear_stack(void)` | Gibt alle Knoten mit `free` frei und setzt `head` und `tail` auf `NULL`. | 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: | Auswahl | Eingabe | Ausgabe | | ------- | -------- | ------------------------------------------------------------------------------------------- | | `1` | `Zahl: ` | – | | `2` | – | `Stack (oben -> unten): 9 5` | | `3` | – | `Pop: 9` (erst ausgeben, dann entfernen) oder bei leerem Stack `Stack ist leer.` | | `4` | – | `Top: 5` oder bei leerem Stack `Stack ist leer.` | | `5` | – | `Stack geleert.` | | `0` | – | `Programm beendet.` – vorher wird der Stack freigegeben | | sonst | – | `Ungültige 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. **Was aus Doubly Linked Lists lässt sich übernehmen?** - `node`, `head` und `tail` sind dieselben wie in [Doubly Linked Lists](https://dev.inf.zone/exercises/09/doublylinkedlist/), ebenso der Aufbau von `main` mit `switch`. - `push` ist `insert_end` unter anderem Namen. - `print_stack` ist `print_backward` mit anderem Text am Zeilenanfang. - Neu sind nur `pop`, `top` und `is_empty`. Wie ein Stack grundsätzlich funktioniert, zeigt das Short [Stacks](https://dev.inf.zone/lectures/5-datenstrukturen/short-5-3-stacks/). Wie in der vorigen Aufgabe gilt: Wenn Sie in einem `case` eine Variable anlegen (etwa `int value = get_int("Zahl: ");`), setzen Sie den Inhalt des `case` in geschweifte Klammern `{ … }`. **Implementierung von `pop`** Merken Sie sich den obersten Knoten in einem Hilfs-Pointer, bevor Sie `tail` verschieben – sonst können Sie ihn danach nicht mehr freigeben: ```c node *tmp = tail; tail = tail->prev; ``` Jetzt gibt es zwei Fälle: Ist `tail` nicht `NULL`, ist es der neue oberste Knoten, und sein `next` muss `NULL` werden. Ist `tail` `NULL`, war `tmp` der einzige Knoten, und auch `head` muss `NULL` werden. Zum Schluss `free(tmp)`. **Implementierung von `clear_stack`** Sie können die Knoten wie `clear_list` in der vorigen Aufgabe einzeln durchlaufen und freigeben. Kürzer geht es mit den Funktionen, die Sie schon haben: Rufen Sie `pop` auf, solange der Stack nicht leer ist. ## 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: ```bash check50 -l inf-zone/exercises/2026/stack ``` ### Speicher Ob Ihr Programm allen Speicher freigibt, zeigt `valgrind` (siehe [Vorlesung 4](https://dev.inf.zone/lectures/4-memory/notes4/)). Legen Sie ein paar Zahlen auf den Stack, entfernen Sie einige und beenden Sie das Programm mit `0`: ```bash valgrind ./stack ``` ### Style Führen Sie den folgenden Befehl aus, um den Stil Ihres Codes mit `style50` zu analysieren: ```bash style50 stack.c ``` ## Abgeben Geben Sie im Ordner `stack` ab: ```bash 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`](https://dev.inf.zone/faq/uebung-solutions/#inf-installieren).