Strutture dati: la coda

Mauro Brunato

Argomenti correlati: [ Strutture dati astratte ]
Una tipica struttura dati astratta è la coda. Si tratta di un oggetto sul quale possiamo compiere due operazioni fondamentali: inserire un dato ed estrarre un dato. Quando estraiamo un dato dalla coda, otteniamo il più vecchio tra i dati inseriti, ossia quello inserito per primo. Per questo motivo, la coda è una struttura di tipo FIFO (First In, First Out: il primo dato inserito è il primo a essere estratto).

La struttura serve dunque a gestire situazioni simili a quelle che si verificano quando più persone devono accedere a un servizio, ad esempio una biglietteria, e si mettono in coda. L'operazione di "inserimento in coda" avviene quando arriva una nuova persona; l'operazione di "estrazione dalla coda" avviene quando lo sportello si libera e una nuova persona viene servita, nell'ordine d'arrivo.

Un esempio pratico

Supponiamo di voler gestire un sistema di iscrizione a un esame orale. Questo sistema deve gestire due operazioni: In realtà, un sistema veramente flessibile dovrebbe prendere in considerazione anche eventuali priorità ben motivate, rinunce ed altri particolari, ma consideriamo un caso semplice. Per semplificare ulteriormente la trattazione, supponiamo che la coda contenga i numeri di matricola degli studenti.

Per realizzare la coda abbiamo bisogno innanzitutto di una struttura in grado di contenere i dati. Trattandosi di dati omogenei (tutti dello stesso tipo), decidiamo di memorizzarli in un vettore v di interi, per esempio 100: 

int v[100];
Consideriamo, per analogia, l'iscrizione classica a un esame: gli studenti scrivono il loro nome sulle righe successive di un foglio di carta (le caselle del vettore), mentre il professore estrae i nomi a partire dall'inizio della lista. Una coda, quindi, è caratterizzata da due indici: uno, che chiameremo in, indica in quale posizione andrà scritto il prossimo dato (indica, cioè, la prima casella libera del vettore). Il secondo indica il prossimo elemento da estrarre (l'indice dell'elemento più vecchio ancora presente nella coda): 
int in, out;
All'inizio del programma, ad indicare che la coda è vuota, entrambi gli indici verranno posti a zero.

L'inserimento di un numero n nella coda è semplice: si tratta di assegnare il valore di n alla casella di v di indice in, incrementando in seguito l'indice: 

v[in++] = n;
L'estrazione di un elemento consiste semplicemente nel prendere il valore di v contenuto all'indice out, incrementando in seguito out per segnalare la successiva posizione da cui estrarre. Ad esempio, l'istruzione seguente estrae un elemento dalla coda e lo assegna alla variabile n: 
n = v[out++];
Nell'immagine che segue, la porzione in grigio del vettore è quella che contiene i dati inseriti ma non ancora estratti.

L'inserimento di un nuovo dato nella coda avviene nella posizione indicata dall'indice in. Ecco il risultato dell'inserimento del numero 2 nella coda (il nuovo elemento inserito è evidenziato in giallo):

L'estrazione avviene invece a partire dall'indice out, che viene poi incrementato. La seguente operazione di estrazione "rimuove" dalla coda il numero 4 (la cui "rimozione" è simboleggiata dallo sfondo più scuro):

Naturalmente, in una coda ben fatta bisogna prevedere dei controlli per stabilire se la coda è vuota (in==out), oppure se sono stati inseriti troppi elementi rispetto alla capacità del vettore.

Codice

Il vettore v e gli indici in e out possono essere raccolti in uno struct. Ecco un file header contenente la definizione della struttura dati e i prototipi delle funzioni che servono a inizializzare il contenuto, inserire ed estrarre un dato.

Ecco il corrispondente codice.

Possibili migliorie

La coda, così come definita finora, è una struttura "a perdere": una volta che l'indice in è arrivato in fondo al vettore, non è più possibile inserire nulla, solo estrarre. È opportuno trovare un modo di "riciclare" il vettore.

La soluzione è quella di considerare il vettore come se fosse circolare: una volta che in è arrivato alla fine del vettore, si può ricominciare dall'inizio. A tale scopo, è sufficiente riportare l'indice a zero se questo, dopo l'incremento, ha superato il limite massimo.

Un altro miglioramento si può ottenere inserendo la lunghezza del vettore come parametro della funzione di inizializzazione, invece che lasciarlo fisso a 100.

Ecco il file header, il file cpp e un abbozzo del programma principale per una coda dinamica.