CKTIS / C
LIFO-Stapel mit dynamischem Array in C
Ein LIFO-Stapel entnimmt den zuletzt abgelegten Datensatz zuerst. Unterscheide Elementzahl und Kapazität und vergrößere den Puffer ohne Datenverlust bei einem Allokationsfehler.
Version: ISO C23; implementation support may vary
Syntax
/* Application-defined operations in ISO C23; not standard-library APIs. */
/* Inside main, after the application types and functions are defined. */
Stack s = { .data = NULL, .size = 0, .capacity = 0 };
Process p;
if (!push(&s, (Process){ .id = 42 }) ||
!peek(&s, &p) ||
!pop(&s, &p)) {
free(s.data);
return EXIT_FAILURE;
}
/* All three calls succeeded; p holds the record copied by pop. */
free(s.data);Ein LIFO-Stapel arbeitet nach dem Prinzip „zuletzt hinein, zuerst heraus“. push legt oben ein Element ab, peek kopiert das oberste Element, ohne es zu entfernen, und pop kopiert und entfernt es. Das sind Funktionen des Beispiels, keine Funktionen der C-Standardbibliothek. peek und pop brauchen einen gültigen Zeiger auf ein separates, beschreibbares Process-Objekt. Bei einem leeren Stapel liefern sie false und lassen die Ausgabe unverändert.
Die Invariante lautet 0 <= size <= capacity: size zählt gespeicherte Datensätze, capacity reservierte Plätze. Das oberste Element hat nur bei size > 0 den Index size - 1. pop verringert size, ohne den Puffer freizugeben. Das anfängliche NULL zeigt an, dass es noch keinen Puffer gibt. NULL ist unter anderem in <stdlib.h> verfügbar und expandiert zu einer implementierungsdefinierten Nullzeigerkonstante.
Ist der Stapel voll, beginnt push mit einem Platz und verdoppelt danach die Kapazität, höchstens bis SIZE_MAX / sizeof *s->data. SIZE_MAX aus <stdint.h> ist der größte size_t-Wert, nicht die verfügbare Speichermenge. Die Grenze verhindert Überläufe bei der Berechnung von Kapazität und Bytezahl. Das Ergebnis von realloc mit einer Größe ungleich null landet in einem temporären Zeiger: Bei NULL bleibt der Stapel unverändert. Nach erfolgreicher Reallokation dürfen alte Zeiger auf den Puffer oder seine Elemente nicht mehr verwendet werden, selbst wenn die Adresse gleich geblieben ist.
Kann die Kapazität nicht wachsen oder schlägt die Allokation fehl, liefert push den Wert false. main meldet den Fehler auf stderr, gibt den Puffer mit free frei und liefert EXIT_FAILURE aus <stdlib.h>. So wird der Umgebung ein erfolgloses Programmende gemeldet, ohne einen bestimmten Zahlenwert vorauszusetzen.
Das zusammengesetzte Literal (Process){ .id = 10 } erzeugt ein unbenanntes Process-Objekt und ist kein Cast. Dieses Literal hat automatische Speicherdauer; push speichert den Datensatz als Wert, nicht seine Adresse. Das Beispiel entspricht ISO C23. Diese Literalform gibt es seit C99, doch die Unterstützung des C23-Modus hängt von der Implementierung ab.
Beispiele
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
typedef struct { int id; } Process;
typedef struct {
Process *data;
size_t size;
size_t capacity;
} Stack;
static bool push(Stack *s, Process value)
{
if (s->size == s->capacity) {
const size_t limit = SIZE_MAX / sizeof *s->data;
if (s->capacity == limit)
return false;
size_t next = s->capacity == 0 ? 1
: s->capacity > limit / 2 ? limit
: s->capacity * 2;
Process *new_data = realloc(s->data, next * sizeof *s->data);
if (new_data == NULL)
return false;
s->data = new_data;
s->capacity = next;
}
s->data[s->size] = value;
++s->size;
return true;
}
static bool peek(const Stack *s, Process *out)
{
if (s->size == 0)
return false;
*out = s->data[s->size - 1];
return true;
}
static bool pop(Stack *s, Process *out)
{
if (!peek(s, out))
return false;
--s->size;
return true;
}
int main(void)
{
Stack s = { .data = NULL, .size = 0, .capacity = 0 };
if (!push(&s, (Process){ .id = 10 }) ||
!push(&s, (Process){ .id = 20 })) {
fputs("Cannot grow stack\n", stderr);
free(s.data);
return EXIT_FAILURE;
}
Process p;
if (peek(&s, &p))
printf("peek: %d\n", p.id);
while (pop(&s, &p))
printf("pop: %d\n", p.id);
puts("empty");
free(s.data);
return EXIT_SUCCESS;
}
Ergebnis
peek: 20 pop: 20 pop: 10 empty
Zwei Aufrufe von `push` erhöhen die Kapazität von 1 auf 2. Nach dem erfolgreichen `peek`-Aufruf gibt das Programm die ID `20` aus. Die ersten beiden Aufrufe von `pop` geben jeweils `true` zurück und schreiben über `out` erst den Datensatz mit der ID `20`, dann den mit der ID `10`. Der nächste `pop`-Aufruf gibt `false` zurück, weil der Stapel leer ist.
Zugehörige Lektionen
- C · Lektion 87 · Fortgeschritten · Version: 3