База знанияИзпитен център
BGБългарски
Избери език13

CKTIS / C

LIFO стек с динамичен масив в C

LIFO стекът премахва първо последния добавен запис. Разграничавайте броя елементи от капацитета и увеличавайте буфера без загуба на данни при неуспешно заделяне на памет.

Версия: ISO C23; implementation support may vary

Синтаксис

/* 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 стекът работи на принципа „последен влязъл, първи излязъл“. push добавя елемент на върха, peek копира върховия елемент, без да го премахва, а pop го копира и премахва. Това са функции от примера, а не от стандартната библиотека на C. peek и pop изискват валиден указател към отделен обект Process, в който може да се записва. При празен стек те връщат false и оставят изходния обект непроменен.

Инвариантът е 0 <= size <= capacity: size брои съхранените записи, а capacity — заделените места. Върхът е на индекс size - 1 само когато size > 0. pop намалява size, без да освобождава буфера. Началното NULL означава, че още няма буфер. Макросът NULL, достъпен наред с други заглавни файлове и чрез <stdlib.h>, се разгъва до константа за нулев указател, определена от реализацията.

Когато стекът е пълен, push започва с едно място, а след това удвоява капацитета до най-много SIZE_MAX / sizeof *s->data. SIZE_MAX от <stdint.h> е най-голямата стойност на size_t, а не количеството налична памет. Ограничението предотвратява препълване при изчисляването на капацитета и броя байтове. Резултатът от realloc с ненулев размер се записва във временен указател: NULL означава неуспех и стекът остава непроменен. След успешно преоразмеряване не използвайте старите указатели към буфера или елементите му, дори адресът да не се е променил.

Ако капацитетът не може да се увеличи или заделянето на памет е неуспешно, push връща false. main извежда съобщение за грешка в stderr, освобождава буфера чрез free и връща EXIT_FAILURE от <stdlib.h>. Така програмата съобщава за неуспешно завършване на средата, без да предполага конкретен числов код.

Съставният литерал (Process){ .id = 10 } създава неименуван обект Process; той не е преобразуване на тип. Този литерал има автоматична продължителност на съхранение, а push записва записа по стойност, а не неговия адрес. Примерът съответства на ISO C23; тази форма на литерала съществува от C99, но поддръжката на режим C23 зависи от реализацията.

Примери

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

Резултат

peek: 20
pop: 20
pop: 10
empty

Две добавяния увеличават капацитета от 1 на 2. След успешно извикване на `peek` програмата извежда идентификатора `20`. Първите две извиквания на `pop` връщат `true` и записват чрез указателя `out` първо записа с идентификатор `20`, а после записа с идентификатор `10`. Следващото извикване на `pop` връща `false`, защото стекът е празен.

Свързани уроци

  • C · Урок 87 · Напреднало · Версия: 3

Източници