Znalostní bázeCentrum zkoušek
CSČeština
Vybrat jazyk13

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

Zdroje