CKTIS / C
Pilha LIFO baseada num vetor dinâmico em C
Uma pilha LIFO retira primeiro o último registo inserido. Distingue o número de elementos da capacidade e aumenta o buffer sem perder dados se a alocação falhar.
Versão: ISO C23; implementation support may vary
Sintaxe
/* 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);Uma pilha LIFO segue o princípio «último a entrar, primeiro a sair». push insere um elemento no topo, peek copia o elemento do topo sem o retirar e pop copia-o e retira-o. São funções do exemplo, não da biblioteca padrão de C. peek e pop requerem um apontador válido para um objeto Process separado e gravável. Se a pilha estiver vazia, devolvem false e deixam esse objeto inalterado.
O invariante é 0 <= size <= capacity: size conta os registos guardados e capacity conta as posições reservadas. O topo está no índice size - 1 apenas quando size > 0. pop reduz size sem libertar o buffer. O valor inicial NULL indica que ainda não há buffer. A macro NULL, disponível entre outros cabeçalhos em <stdlib.h>, expande-se para uma constante de apontador nulo definida pela implementação.
Quando a pilha está cheia, push começa com uma posição e depois duplica a capacidade até ao limite SIZE_MAX / sizeof *s->data. SIZE_MAX, de <stdint.h>, é o maior valor de size_t, não a quantidade de memória disponível. O limite evita o transbordamento no cálculo da capacidade e do número de bytes. Guarda o resultado de realloc com tamanho diferente de zero num apontador temporário: NULL indica falha e a pilha fica inalterada. Após uma realocação bem-sucedida, não uses apontadores antigos para o buffer ou para os seus elementos, mesmo que o endereço não tenha mudado.
Se não for possível aumentar a capacidade ou se a alocação falhar, push devolve false. main comunica o erro em stderr, liberta o buffer com free e devolve EXIT_FAILURE, de <stdlib.h>, para indicar ao ambiente anfitrião que o programa terminou com uma falha, sem pressupor um código numérico específico.
O literal composto (Process){ .id = 10 } cria um objeto Process sem nome; não é uma conversão de tipo. Este literal tem duração de armazenamento automática e push guarda o registo por valor, não o seu endereço. O exemplo está em conformidade com ISO C23; esta forma de literal existe desde C99, mas o suporte do modo C23 depende da implementação.
Exemplos
#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;
}
Resultado
peek: 20 pop: 20 pop: 10 empty
Duas inserções fazem a capacidade passar de 1 para 2. Após uma chamada bem-sucedida a `peek`, o programa mostra o identificador `20`. As duas primeiras chamadas a `pop` devolvem `true` e escrevem através de `out` primeiro o registo com o identificador `20` e depois o registo com o identificador `10`. A chamada seguinte a `pop` devolve `false` porque a pilha está vazia.
Lições relacionadas
- C · Lição 87 · Avançado · Versão: 3