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