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.
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.
Ecco il corrispondente codice.
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.