CKTIS / C
Zásobník LIFO s dynamickým poľom v C
Zásobník LIFO odoberá najprv naposledy vložený záznam. Rozlišujte počet prvkov a kapacitu a zväčšujte vyhradenú pamäť bez straty údajov pri zlyhaní alokácie.
Verzia: 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);Zásobník LIFO sa riadi pravidlom „posledný dnu, prvý von“. push pridá prvok na vrchol, peek skopíruje vrchný prvok bez odobratia a pop ho skopíruje a odoberie. Sú to funkcie príkladu, nie štandardnej knižnice C. peek a pop vyžadujú platný ukazovateľ na samostatný zapisovateľný objekt Process. Pri prázdnom zásobníku vrátia false a výstupný objekt nezmenia.
Invariant je 0 <= size <= capacity: size udáva počet uložených záznamov a capacity počet vyhradených miest. Vrchol má index size - 1 len vtedy, keď size > 0. pop zníži size, ale pamäť neuvoľní. Počiatočné NULL znamená, že pamäť pre pole ešte nebola pridelená. Makro NULL, dostupné okrem iného v <stdlib.h>, sa expanduje na konštantu nulového ukazovateľa definovanú implementáciou.
Keď je zásobník plný, push začne s jedným miestom a potom zdvojnásobuje kapacitu najviac do SIZE_MAX / sizeof *s->data. SIZE_MAX z <stdint.h> je najväčšia hodnota size_t, nie množstvo dostupnej pamäte. Hranica zabraňuje pretečeniu pri výpočte kapacity a počtu bajtov. Výsledok realloc s nenulovou veľkosťou sa uloží do dočasného ukazovateľa: NULL znamená zlyhanie a zásobník zostane nezmenený. Po úspešnej realokácii nepoužívajte staré ukazovatele na pole ani na jeho prvky, aj keby sa adresa nezmenila.
Ak kapacitu nemožno zväčšiť alebo alokácia zlyhá, push vráti false. Funkcia main vypíše chybu na stderr, uvoľní pamäť pomocou free a vráti EXIT_FAILURE z <stdlib.h>. Tak oznámi hostiteľskému prostrediu neúspešné ukončenie bez predpokladu konkrétneho číselného kódu.
Zložený literál (Process){ .id = 10 } vytvára nepomenovaný objekt Process; nejde o pretypovanie. Tento literál má automatickú dobu uloženia a push uloží záznam hodnotou, nie jeho adresu. Príklad je v súlade s ISO C23; táto podoba literálu existuje od C99, ale podpora režimu C23 závisí od implementácie.
Príklady
#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;
}
Výsledok
peek: 20 pop: 20 pop: 10 empty
Dve vloženia zvýšia kapacitu z 1 na 2. Po úspešnom volaní `peek` program vypíše identifikátor `20`. Prvé dve volania `pop` vrátia `true` a cez ukazovateľ `out` zapíšu najprv záznam s identifikátorom `20` a potom záznam s identifikátorom `10`. Ďalšie volanie `pop` vráti `false`, pretože zásobník je prázdny.
Súvisiace lekcie
- C · Lekcia 87 · Pokročilá · Verzia: 3