CKTIS / C
LIFO stog s dinamičkim poljem u C-u
LIFO stog najprije uklanja posljednji dodani zapis. Razlikujte broj elemenata od kapaciteta i povećajte međuspremnik bez gubitka podataka ako alokacija ne uspije.
Verzija: ISO C23; implementation support may vary
Sintaksa
/* 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);LIFO stog radi po načelu „zadnji ušao, prvi izašao”. push dodaje element na vrh, peek kopira vršni element bez uklanjanja, a pop ga kopira i uklanja. To su funkcije iz primjera, a ne iz standardne biblioteke C-a. peek i pop zahtijevaju valjan pokazivač na zaseban objekt Process u koji se može pisati. Kad je stog prazan, vraćaju false i ne mijenjaju izlazni objekt.
Invarijanta je 0 <= size <= capacity: size broji pohranjene zapise, a capacity rezervirana mjesta. Vrh je na indeksu size - 1 samo kad vrijedi size > 0. pop smanjuje size bez oslobađanja međuspremnika. Početni NULL označava da međuspremnik još ne postoji. Makro NULL, dostupan među ostalim u <stdlib.h>, proširuje se u konstantu nul-pokazivača koju određuje implementacija.
Kad je stog pun, push kreće od jednog mjesta pa udvostručuje kapacitet najviše do SIZE_MAX / sizeof *s->data. SIZE_MAX iz <stdint.h> najveća je vrijednost size_t, a ne količina dostupne memorije. Ograničenje sprječava prekoračenje pri izračunu kapaciteta i broja bajtova. Rezultat poziva realloc s veličinom različitom od nule pohranjuje se u privremeni pokazivač: NULL znači neuspjeh, a stog ostaje nepromijenjen. Nakon uspješne realokacije ne upotrebljavajte stare pokazivače na međuspremnik ili njegove elemente, čak ni ako se adresa nije promijenila.
Ako se kapacitet ne može povećati ili alokacija ne uspije, push vraća false. Funkcija main prijavljuje pogrešku na stderr, oslobađa međuspremnik pomoću free i vraća EXIT_FAILURE iz <stdlib.h>. Tako okruženju javlja da je program završio neuspješno, bez pretpostavke o konkretnoj brojčanoj vrijednosti statusa.
Složeni literal (Process){ .id = 10 } stvara neimenovani objekt Process; nije pretvorba tipa. Taj literal ima automatsko trajanje pohrane, a push pohranjuje zapis po vrijednosti, a ne njegovu adresu. Primjer je usklađen s ISO C23; ovaj oblik literala postoji od C99, no podrška za način rada C23 ovisi o implementaciji.
Primjeri
#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;
}
Rezultat
peek: 20 pop: 20 pop: 10 empty
Dva umetanja povećavaju kapacitet s 1 na 2. Nakon uspješnog poziva `peek` program ispisuje identifikator `20`. Prva dva poziva funkcije `pop` vraćaju `true` i preko pokazivača `out` upisuju najprije zapis s identifikatorom `20`, a zatim zapis s identifikatorom `10`. Sljedeći poziv funkcije `pop` vraća `false` jer je stog prazan.
Povezane lekcije
- C · Lekcija 87 · Napredno · Verzija: 3