Base di conoscenzaCentro esami
ITItaliano
Scegli la lingua13

CKTIS / C

Pila LIFO basata su un array dinamico in C

Una pila LIFO estrae per primo l’ultimo record inserito. Distingui il numero di elementi dalla capacità ed espandi il buffer senza perdere dati se l’allocazione fallisce.

Versione: ISO C23; implementation support may vary

Sintassi

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

Una pila LIFO segue il principio «l’ultimo entrato è il primo a uscire». push inserisce un elemento in cima, peek copia l’elemento in cima senza rimuoverlo e pop lo copia e lo rimuove. Sono funzioni dell’esempio, non della libreria standard del C. peek e pop richiedono un puntatore valido a un oggetto Process separato e scrivibile. Se la pila è vuota, restituiscono false senza modificare l’oggetto di uscita.

L’invariante è 0 <= size <= capacity: size conta i record memorizzati e capacity i posti riservati. L’elemento in cima ha indice size - 1 solo se size > 0. pop riduce size senza liberare il buffer. Il valore iniziale NULL indica che il buffer non esiste ancora. La macro NULL, disponibile tra l’altro in <stdlib.h>, si espande in una costante di puntatore nullo definita dall’implementazione.

Quando la pila è piena, push parte da un posto e poi raddoppia la capacità senza superare SIZE_MAX / sizeof *s->data. SIZE_MAX, da <stdint.h>, è il valore massimo di size_t, non la quantità di memoria disponibile. Il limite evita l’overflow nel calcolo della capacità e del numero di byte. Il risultato di realloc con dimensione non nulla va in un puntatore temporaneo: NULL indica un fallimento e la pila resta invariata. Dopo una riallocazione riuscita non usare più i vecchi puntatori al buffer o ai suoi elementi, anche se l’indirizzo non è cambiato.

Se la capacità non può aumentare o l’allocazione fallisce, push restituisce false. main segnala l’errore su stderr, libera il buffer con free e restituisce EXIT_FAILURE da <stdlib.h> per notificare all’ambiente ospitante che il programma è terminato con un errore, senza presumere un codice numerico specifico.

Il letterale composto (Process){ .id = 10 } crea un oggetto Process senza nome; non è un cast. Questo letterale ha durata di memorizzazione automatica e push memorizza il record per valore, non il suo indirizzo. L’esempio è conforme a ISO C23; questa forma del letterale esiste da C99, ma il supporto della modalità C23 dipende dall’implementazione.

Esempi

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

Risultato

peek: 20
pop: 20
pop: 10
empty

Due inserimenti fanno passare la capacità da 1 a 2. Dopo una chiamata riuscita a `peek`, il programma mostra l’identificativo `20`. Le prime due chiamate a `pop` restituiscono entrambe `true` e scrivono tramite `out` prima il record con identificativo `20`, poi quello con identificativo `10`. La chiamata successiva a `pop` restituisce `false` perché la pila è vuota.

Lezioni correlate

  • C · Lezione 87 · Avanzato · Versione: 3

Fonti