CKTIS / C
Zásobník LIFO nad dynamickým polem v C
Zásobník LIFO odebírá nejprve naposledy vložený záznam. Rozlišujte počet prvků a kapacitu a zvětšujte vyrovnávací paměť bez ztráty dat při selhání alokace.
Verze: ISO C23; implementation support may vary
Syntaxe
/* 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 se řídí pravidlem „poslední dovnitř, první ven“. push přidá prvek na vrchol, peek vrchní prvek zkopíruje bez odebrání a pop ho zkopíruje a odebere. Jde o funkce příkladu, nikoli standardní knihovny C. peek a pop vyžadují platný ukazatel na samostatný zapisovatelný objekt Process. U prázdného zásobníku vrátí false a výstupní objekt nezmění.
Invariant je 0 <= size <= capacity: size počítá uložené záznamy, capacity rezervované pozice. Vrchol má index size - 1 jen tehdy, když size > 0. pop sníží size, ale paměť neuvolní. Počáteční NULL znamená, že paměť pro pole dosud není přidělena. Makro NULL, dostupné mimo jiné v <stdlib.h>, se expanduje na konstantu nulového ukazatele definovanou implementací.
Je-li zásobník plný, push začne s jednou pozicí a poté kapacitu zdvojnásobuje nejvýše do SIZE_MAX / sizeof *s->data. SIZE_MAX z <stdint.h> je nejvyšší hodnota size_t, nikoli množství dostupné paměti. Limit brání přetečení při výpočtu kapacity a počtu bajtů. Výsledek realloc s nenulovou velikostí se uloží do dočasného ukazatele: NULL znamená selhání a zásobník zůstane nezměněn. Po úspěšné realokaci už nepoužívejte staré ukazatele na pole ani na jeho prvky, ani když se adresa nezměnila.
Nelze-li kapacitu zvětšit nebo selže-li alokace, push vrátí false. Funkce main vypíše chybu na stderr, uvolní paměť pomocí free a vrátí EXIT_FAILURE z <stdlib.h>. Tím oznámí hostitelskému prostředí neúspěšné ukončení, aniž by předpokládala konkrétní číselný kód.
Složený literál (Process){ .id = 10 } vytváří nepojmenovaný objekt Process; nejde o přetypování. Tento literál má automatickou dobu uložení a push ukládá záznam hodnotou, nikoli jeho adresu. Příklad odpovídá ISO C23; tato podoba literálu existuje od C99, ale podpora režimu C23 závisí na implementaci.
Pří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ýsledek
peek: 20 pop: 20 pop: 10 empty
Dvě vložení zvýší kapacitu z 1 na 2. Po úspěšném volání `peek` program vypíše identifikátor `20`. První dvě volání `pop` vrátí `true` a přes ukazatel `out` zapíšou nejprve záznam s identifikátorem `20` a poté záznam s identifikátorem `10`. Další volání `pop` vrátí `false`, protože je zásobník prázdný.
Související lekce
- C · Lekce 87 · Pokročilá · Verze: 3