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