La maggior parte dei principianti presuppone che le strutture dati siano statiche. Non lo sono. Uno stack collegato è una bestia dinamica. Cresce e si restringe al volo. Non preallochi la memoria. Lo prendi quando ne hai bisogno. Rilascialo quando hai finito.
Questo esempio utilizza numeri interi. Cambia typedef int stack_data in float o char se vuoi. La logica rimane la stessa.
L’interfaccia
Guarda l’intestazione. È un contratto.
stack_init crea il caos. “stack_clear” lo cancella. stack_empty ti dice se è rimasto qualcosa. “push” inserisce i dati. “pop” li estrae.
Semplice. Pulito.
Il motore
Il file di codice nasconde il coraggio.
“top” punta all’elemento più recente. “NULL” significa vuoto.
stack_init reimposta semplicemente top su NULL. Fatto.
“stack_clear” viene visualizzato finché non è vuoto. È un ciclo. È economico.
stack_empty controlla se “top” è “NULL”. Restituisce 1 se vero. 0 se falso.
stack_push fa il lavoro pesante.
Alloca memoria. Imposta i dati. Lo collega al vecchio top. Aggiorna “top”.
stack_pop inverte il processo.
Cattura i dati. Sposta l'”alto” verso il basso. Libera il vecchio nodo. Restituisce il valore.
Se lo stack è vuoto? Restituisce spazzatura. Non uscire da una pila vuota.
Nascondere informazioni
Questa è la chiave.
Vedi solo l’intestazione. Non vedi il codice.
Lo stack potrebbe utilizzare array. Puntatori. File. Un elenco collegato. Non importa.
Finché l’interfaccia funziona, non ti interessa come è costruita.
Questa è l’informazione nascosta. Non è solo una parola d’ordine. È il modo in cui crei un software che non si rompe quando cambi i componenti interni.
C Gotcha
C non perdona gli errori.
- Le parentesi contano.
(*p).inon è la stessa cosa di*p.i. Innanzitutto si dereferenzia il puntatore. L’altro accede al membro quindi dereferenzia. Se sbagli, ti schianti. - Perdite di memoria. Non impostare mai semplicemente
top = NULL. Rendi orfano ogni nodo nell’elenco. Perdi i dati. Perdi la memoria. Utilizza “gratuito”. Sempre. - Includi intestazioni.
NULLrisiede instdio.h. Se lo dimentichi, il tuo codice potrebbe essere compilato su alcuni compilatori. Non lo farà con gli altri. Oppure definirà “NULL” come zero in un modo strano. Includi
Qual è il prossimo passo?
Lo stack di base è semplice. Gli stack reali hanno bisogno di più.
Aggiungi “dup”. Duplica l’elemento superiore. Aggiungi “conteggio”. Restituisce il numero di elementi. Aggiungi “aggiungi”. Apri i primi due, aggiungili, spingi il risultato.
Costruisci un programma di guida. Scrivi un makefile. Compilarlo. Eseguilo.
Se si blocca, hai perso un “gratuito”. Oppure hai avuto accesso alla memoria liberata. Esegui il debug.
Il controllo della realtà
L’allocazione dinamica è veloce. Fino a quando non lo è più.
“malloc” e “free” hanno un sovraccarico. In circuiti stretti, i conti si sommano.
Ma per uso generale? È flessibile. È standard. È ciò che vedrai nella maggior parte dei codebase C.
Lo stack collegato è un elemento costitutivo.
Lo utilizzerai per le chiamate di funzione. Per la valutazione dell’espressione. Per i pulsanti Annulla.
È ovunque.
Ricorda solo: se lo assegni, lo liberi. Oppure.
“Il codice è come l’umorismo
