CKTIS / C
LIFO-stapel met een dynamische array in C
Een LIFO-stapel verwijdert het laatst toegevoegde record als eerste. Houd het aantal elementen en de capaciteit apart en vergroot de buffer zonder gegevensverlies als de allocatie mislukt.
Versie: 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);Een LIFO-stapel werkt volgens het principe ‘laatst erin, eerst eruit’. push legt een element bovenop, peek kopieert het bovenste element zonder het te verwijderen en pop kopieert én verwijdert het. Dit zijn functies uit het voorbeeld, geen functies uit de C-standaardbibliotheek. peek en pop vereisen een geldige pointer naar een afzonderlijk, beschrijfbaar Process-object. Bij een lege stapel geven ze false terug en laten ze het uitvoerobject ongewijzigd.
De invariant is 0 <= size <= capacity: size telt opgeslagen records en capacity telt gereserveerde plaatsen. Het bovenste element heeft alleen index size - 1 als size > 0. pop verlaagt size zonder de buffer vrij te geven. De beginwaarde NULL geeft aan dat er nog geen buffer is. De macro NULL, onder meer beschikbaar via <stdlib.h>, expandeert tot een door de implementatie gedefinieerde nulpointerconstante.
Als de stapel vol is, begint push met één plaats en verdubbelt daarna de capaciteit tot maximaal SIZE_MAX / sizeof *s->data. SIZE_MAX uit <stdint.h> is de maximale waarde van size_t, niet de hoeveelheid beschikbaar geheugen. De grens voorkomt overflow bij de berekening van de capaciteit en het aantal bytes. Bewaar het resultaat van realloc met een grootte groter dan nul in een tijdelijke pointer: NULL betekent dat de allocatie is mislukt en dat de stapel ongewijzigd blijft. Gebruik na een geslaagde herallocatie geen oude pointers naar de buffer of de elementen ervan, ook niet als het adres gelijk is gebleven.
Als de capaciteit niet kan groeien of de allocatie mislukt, geeft push de waarde false terug. main meldt de fout op stderr, geeft de buffer vrij met free en retourneert EXIT_FAILURE uit <stdlib.h> om de uitvoeringsomgeving te melden dat het programma niet succesvol is beëindigd, zonder uit te gaan van een specifieke numerieke status.
De samengestelde literal (Process){ .id = 10 } maakt een naamloos Process-object aan; het is geen cast. Deze literal heeft een automatische opslagduur en push slaat het record op als waarde, niet als adres. Het voorbeeld voldoet aan ISO C23; deze vorm van de literal bestaat sinds C99, maar ondersteuning voor de C23-modus verschilt per implementatie.
Voorbeelden
#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;
}
Resultaat
peek: 20 pop: 20 pop: 10 empty
Door twee elementen toe te voegen groeit de capaciteit van 1 naar 2. Na een geslaagde aanroep van `peek` toont het programma ID `20`. De eerste twee aanroepen van `pop` geven allebei `true` terug en schrijven via `out` eerst het record met ID `20` en daarna het record met ID `10`. De volgende aanroep van `pop` geeft `false` terug omdat de stapel leeg is.
Gerelateerde lessen
- C · Les 87 · Gevorderd · Versie: 3