Base de conhecimentoCentro de Exames
PT · PTPortuguês (Portugal)
Escolher idioma13

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

Fontes