Baza wiedzyCentrum egzaminacyjne
PLPolski
Wybierz język13

CKTIS / C

Stos LIFO na tablicy dynamicznej w C

Stos LIFO zdejmuje najpierw ostatnio dodany rekord. Rozróżnij liczbę elementów od pojemności i zwiększaj bufor bez utraty danych w razie błędu alokacji.

Wersja: ISO C23; implementation support may vary

Składnia

/* 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);

Stos LIFO działa według zasady „ostatni wszedł, pierwszy wyszedł”. push dodaje element na szczyt, peek kopiuje element ze szczytu bez jego usuwania, a pop kopiuje go i usuwa ze stosu. To funkcje przykładu, nie biblioteki standardowej C. peek i pop wymagają prawidłowego wskaźnika do osobnego obiektu Process, do którego można zapisać wynik. Gdy stos jest pusty, zwracają false i nie zmieniają wyniku.

Niezmiennik to 0 <= size <= capacity: size liczy zapisane rekordy, a capacity wszystkie zarezerwowane miejsca. Szczyt ma indeks size - 1 tylko wtedy, gdy size > 0. pop zmniejsza size, ale nie zwalnia bufora. Początkowe NULL oznacza brak bufora. Makro NULL, dostępne m.in. w <stdlib.h>, rozwija się do stałej wskaźnika pustego o postaci określonej przez implementację.

Gdy stos jest pełny, push zaczyna od jednego miejsca, a następnie podwaja pojemność, nie przekraczając SIZE_MAX / sizeof *s->data. SIZE_MAX z <stdint.h> to największa wartość size_t, a nie ilość dostępnej pamięci. Ograniczenie chroni obliczenia pojemności i liczby bajtów przed przepełnieniem. Wynik realloc dla niezerowego rozmiaru trafia do tymczasowego wskaźnika: NULL oznacza niepowodzenie, a stos pozostaje bez zmian. Po udanej realokacji nie wolno używać starych wskaźników do bufora ani jego elementów, nawet jeśli adres się nie zmienił.

Jeśli pojemności nie można zwiększyć lub alokacja się nie powiedzie, push zwraca false. Funkcja main wypisuje komunikat na stderr, zwalnia bufor przez free i zwraca EXIT_FAILURE z <stdlib.h>, sygnalizując środowisku niepowodzenie bez zakładania konkretnego kodu liczbowego.

Literał złożony (Process){ .id = 10 } tworzy nienazwany obiekt Process i nie jest rzutowaniem. Ten literał ma automatyczny czas przechowywania, a push zapisuje rekord przez wartość, nie jego adres. Przykład jest zgodny z ISO C23; użyta postać literału istnieje od C99, lecz obsługa trybu C23 zależy od implementacji.

Przykłady

#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;
}

Wynik

peek: 20
pop: 20
pop: 10
empty

Dwa wstawienia wymuszają wzrost pojemności z 1 do 2. Po udanym wywołaniu `peek` program wypisuje identyfikator `20`. Pierwsze dwa wywołania `pop` zwracają `true` i zapisują przez `out` rekordy o identyfikatorach odpowiednio `20` i `10`. Kolejne wywołanie `pop` zwraca `false`, ponieważ stos jest pusty.

Powiązane lekcje

  • C · Lekcja 87 · Zaawansowany · Wersja: 3

Źródła