Che cos’è uno stack?
Uno stack è un insieme dinamico di elementi, dove ogni elemento viene inserito “sopra” all’altro. Possiamo pensare ad uno stack come ad una pila di piatti, dove ogni piatto è un elemento. Essenzialmene uno stack implementa due tipi di operazioni, chiamate PUSH e POP.
L’operazione di PUSH consente di inserire un nuovo elemento in cima alla pila, mentre l’operazione POP rimuove l’elemento in cima. Per questo motivo, si dice che lo stack implementa lo schema LIFO (Last-In, First-Out), ovvero l’ultimo elemento ad essere stato aggiunto è anche il primo ad essere tolto.
Rappresentazione dello stack
Lo stack si può implementare con vari metodi. Per semplicità lo implementeremo con un array, assumendo dunque che esso non possa contenere più di n elementi. Sarà comodo conoscere dunque il numero di elementi presenti nello stack, per sapere poi dove si trova l’elemento in cima alla pila. Inoltre, dobbiamo sapere quando lo stack è vuoto, in modo da poter segnalare un errore qualora si cercasse di effettuare un’operazione di POP.
Implementazione dei 3 metodi
Nella nostra implementazione utilizzeremo una variabile globale top che indica la posizione dell’ultimo elemento dello stack. Quando inizializzeremo lo stack, essa assumerà valore -1, mentre quando avrà un solo elemento, assumerà il valore 0. Il numero di elementi nello stack è quindi di top+1.
Stack-Vuoto
Per sapere se lo stack è vuoto, ci basterà controllare che il valore top non sia negativo.
int stack-vuoto() {
if (top < 0)
return -1;
else
return 0;
}Push
Banalmente, quando inseriamo un nuovo elemento, la posizione di quest’ultimo aumenta di 1. Dobbiamo stare però attenti ad eventuali errori di stack-overflow e quindi controllare che lo stack non sia già pieno. Per far ciò ci aiutiamo con una procedura ausiliaria che chiameremo stack-pieno().
int stack-pieno() {
if (top == GRANDEZZA-MAX)
return 1;
else
return 0;
}
void push(int x) {
if (!stack-pieno()) {
top = top + 1;
stack[top] = x;
} else {
printf("Non è possibile inserire più elementi. Lo stack è pieno!\n");
}
}Pop
Quando invece togliamo un elemento dalla pila, dobbiamo salvaguardarci da errori di stack underflow. Ci aiutiamo dunque con la procedura stack-vuoto() che abbiamo scritto prima.
void pop() {
if (!stack-vuoto()) {
} else {
printf("Lo stack è vuoto. Non posso eliminare elementi.\n");
}
}Tutto insieme
Bene, abbiamo tutto l’occorrente per creare un semplice programmino d’esempio. Il seguente programma chiede 6 numeri in input che vengono posizionati in cima allo stack. Poi viene tolto ogni numero finchè lo stack non rimane vuoto.
#include <stdio.h>
#include <time.h>
int GRANDEZZA_MAX = 6;
int stack[6];
int top = -1;
int stack_vuoto() {
if (top < 0)
return 1;
else
return 0;
}
int stack_pieno() {
if (top == GRANDEZZA_MAX-1)
return 1;
else
return 0;
}
int pop() {
if ( !stack_vuoto() ) {
int data = stack[top];
top = top - 1;
return data;
}
else
printf("Stack vuoto: non ci sono elementi da eliminare\n");
}
int push(int x) {
if (!stack_pieno() ) {
top = top + 1;
stack[top] = x;
}
else
printf("Elemento non inserito: stack pieno\n");
}
int main () {
printf("Pronti per inserire elementi nello stack...\n");
int i;
while ( !stack_pieno() ) {
int data;
printf("Inserisci l'elemento numero %d: ", top+2 );
scanf("%d", &data);
push(data);
printf("L'indice dell'ultimo elemento è %d\n\n", top);
}
printf("Bene, ora lo stack è pieno...\n");
printf("Togliamo tutti gli elementi...\n");
// pause for some time
struct timespec tim, tim2;
tim.tv_sec = 1;
tim.tv_nsec = 0;
while (!stack_vuoto()){
int data = pop();
printf("\nTolto l'elemento %d", data);
printf("\nRimangono %d elementi\n", top+1);
nanosleep(&tim, &tim2);
}
printf("\nOra lo stack è vuoto...");
}Puoi copiare ed incollare il programmino sul tuo text editor di fiducia e compilarlo. Per avere un’idea di come funziona, guarda la gif sotto.
