Implementazione in C di una pila
La struttura dati pila
La pila è una struttura dati di tipo LIFO per cui l'ultimo elemento inserito è il primo a uscire.
Le operazioni sulla pila sono solo tre:
- verifica che la pila [non] sia vuota (empty)
- inserimento di un nuovo elemento (push)
- restituzione di un elemento e cancellazione dalla pila (pop)
Esempio:
push('c')
| c |
push('i')
| c | i |
push('a')
| c | i | a |
push('o')
| c | i | a | o |
pop() // ottengo la o
| c | i | a |
pop() // ottengo la a
| c | i |
Tempo di esecuzione
Inserimento: ο(1)
Cancellazione: ο(1)
Ricerca: ο(n)
Implementazione
In questa implementazione, la pila è un insieme di nodi, ciascuno dei quali contiene un valore di tipo char e un puntatore al nodo successivo.
// in stack.h
typedef struct stack * Stack;
// in stack.c
struct stack {
char c;
Stack next;
};
Nel file di header è definito un tipo Stack che rappresenta una struct stack *, quindi Stack è un puntatore.
Nel file .c è definita la struttura stack (s minuscola) che contiene il valore del nodo e il puntatore al nodo successivo. Una scrittura alternativa, che non fa uso della definizione del tipo Stack è la seguente:
// in stack.c
struct stack {
char c;
stack * next;
};
init
è stata aggiunta una funzione init() che alloca della memoria e restituisce il puntatore a un nodo vuoto.
Stack init() {
Stack s;
s = (Stack)malloc(sizeof(Stack));
s->next = NULL;
return s;
}
Il cast a Stack presente nella malloc non è strettamente necessario.
empty
int empty(Stack s) {
return s->next == NULL;
}
Dal momento che l'ultimo nodo è vuoto, faccio una verifica sul campo next.
push
void push(Stack *s, char c) {
Stack newStack;
newStack = init();
newStack->c = c;
newStack->next = *s;
*s = newStack;
}
push prende in ingresso il puntatore a uno Stack (quindi un puntatore al puntatore di stack con la s minuscola).
In questo modo quando si usa s si sta utilizzando un indirizzo di memoria, e non un valore. Nella pratica, si agisce sul dato contenuto nell'indirizzo puntato da s; viceversa sarebbe fatta una copia del contenuto di s.
| Con puntatore | Senza puntatore |
|---|---|
push(Stack *s, char c)è passato un puntatore a s |
push(Stack s, char c)è passato s: in realtà è una "copia" che ha la funzione come scope |
Stack newStack;Si inizializza un nuovo elemento Stack |
Stack newStack;Si inizializza un nuovo elemento Stack |
newStack->next = *s;il next contiene un puntatore a s |
newStack->next = s;il next contiene s (una copia del contenuto "originale") |
*s = newStack;l'indirizzo a cui punta s è sostituito dall'indirizzo a cui punta newStack |
s = newStack;s è sostituito dall'indirizzo a cui punta newStack |
Al termine di queste operazioni, il contenuto di s nella funzione che utilizza push è cambiato solo nella versione con puntatore; viceversa l'esecuzione di push non ha effetto sulla funzione chiamante nella versione in cui è passato s come valore.
pop
La funzione pop restituisce un char e rimuove l'elemento dalla pila.
char pop(Stack *s) {
char c;
Stack oldS;
oldS = *s;
c = (*s)->c;
*s = (*s)->next;
free(oldS);
return c;
}
Vanno mantenute sia una copia del carattere sia del puntatore, perché dopo aver "spostato" il puntatore a next (*s = (*s)->next;) è necessario prima deallocare lo spazio ormai inutilizzato sia restituire il carattere, che "sopravvive" solo nella copia fatta precedentemente.
Se non si facesse il free dello spazio, questo resterebbe allocato senza che sia puntato da alcun puntatore. Quindi ci sarebbe uno spreco di memoria, crescente a ogni operazione, che si libererebbe solo al termine dell'esecuzione del programma tramite il garbage collector del sistema operativo.
main
main(int argc, char *argv[]) {
Stack s;
char c;
s = init();
push(&s, 'o');
push(&s, 'a');
push(&s, 'i');
push(&s, 'c');
while(!empty(s)) printf("%c", pop(&s));
pop(&s);
getchar();
}
Nel main è necessario passare come parametri non tanto il valore di s, quanto il suo indirizzo di memoria.
L'output di questo esempio sarà "oaic".
Al termine di questo esempio è stato aggiunto un getchar() per comodità.