5.7 Gestione di una coda

La gestione di una coda presenta dei punti in comuni con la gestione della pila, le funzioni che verranno presentate avranno dei punti in comune con le corrispondenti della pila.

Rispetto alla gestione della pila, la coda presenta principalmente una differenza sostanziale che comporta delle soluzioni implementative differenti rispetto a quelle usate nel primo caso.

• Una pila cresce solo da un lato e quindi basta, utilizzando una struttura sequenziale, tenere conto solo di un puntatore (cima) all’ultimo elemento inserito: se l’indicatore raggiunge, in valore, la dimensione della struttura sequenziale, la pila è piena.

• Una coda ha necessità di utilizzare due puntatori (testa e fondo): uno per i prelievi e uno per gli inserimenti. Anche in questo caso si utilizzerà una struttura sequenziale per implementare la coda solo che, stavolta, il puntatore fondo può raggiungere il valore della dimensione della struttura sequenziale, senza che tale condizione comporti come conseguenza il riempimento della coda. La struttura che si sta esaminando è di tipo dinamico, e quindi i prelievi e gli inserimenti si susseguono: può darsi che siano già stati prelevati, per esempio, tutti gli elementi meno uno. In tale caso la zona di memoria riservata alla struttura è praticamente vuota.

Per i motivi espressi prima è opportuno, in questo caso, utilizzare una struttura circolare. Se la struttura sequenziale prevede n elementi si conviene di adottare le seguenti convenzioni:

1. Per 0 <= i < (n-1) il successivo dell’elemento di posizione i sarà l’elemento di posizione i+1

2. Per i = n-1 il successivo sarà l’elemento di posizione 0. Praticamente arrivati all’ultimo elemento si ricomincia dal primo.

Sarà inoltre opportuno fare in modo che testa punti una posizione prima del primo elemento e che fondo punti all’ultimo inserito. Così facendo se da una parte si sarà costretti a non utilizzare un elemento della struttura (quello a cui punta testa), dall’altra la condizione testa == fondo sarà indicativa del fatto che la coda è vuota.

In seguito si esaminerà la nuova struttura con le sue caratteristiche. Il resto del programma può essere identico a quello visto prima per la gestione dello stack.

/* Implementazione della Coda */

#define DIMCODA 8	/*1*/

typedef struct rec {
  char titolo[50]; 
  char autore[20]; 
  char editore[20]; 
  float prezzo; 
}libro;
libro libreria[DIMCODA];
int fondo = -1;
int testa = -1;

/* Funzioni per la gestione della Coda */

int piena();	/*2*/
int vuota();
void aggiungi(const libro *lib);
libro elimina();

/* Funzioni standard per la gestione di una coda */

/* Funzioni che ritornano informazioni sullo stato della coda */

int piena(){
  int numel; 
  numel=(fondo>=testa)?(fondo-testa):(fondo+DIMCODA-testa);	/*3*/ 
  if(numel==DIMCODA-1)	/*4*/ 
    return 1; 
  else
    return 0; 
}

int vuota(){
  if(testa==fondo)	/*5*/ 
    return 1; 
  else 
    return 0; 
}

/* Aggiunge un elemento alla coda */

void aggiungi(const libro *lib){
  fondo = ++fondo % DIMCODA;	/*6*/ 
  libreria[fondo]=*lib;	/*7*/ 
}

/* Elimina un elemento dalla coda */

libro elimina(){
  testa = ++testa % DIMCODA;	/*8*/ 
  return libreria[testa];	/*9*/ 
}

A cominciare da 1 è definita la struttura che è molto simile alla pila tranne per il fatto che qui ci sono due puntatori. Le funzioni di gestione, il cui prototipo si trova in 2, sono anche esse formalmente uguali a quelle di gestione dello stack: cambieranno solo le operazioni di aggiornamento dei puntatori.

La funzione piena calcola in 3 il numero di elementi contenuti come differenza dei valori contenuti nei due puntatori della struttura. Poiché la struttura è circolare potrebbe essere che il valore di fondo sia minore del valore contenuto in testa: in tal caso bisogna effettuare una correzione su tale valore. In ogni caso fondo deve essere inteso maggiore di testa. In 4 viene controllato se la coda è piena; è già stato fatto osservare che una posizione di memoria resta inutilizzata.

La 5 fornisce la condizione per sapere se la coda è vuota.

Nella 6 si calcola il valore di fondo in relazione al fatto che si sta utilizzando una struttura circolare. Viene effettuata una operazione in modulo (l’operatore % è appunto l’operatore che restituisce il resto della divisione intera fra gli operandi): prima viene effettuato l’aggiornamento di fondo ad indicare che c’è un nuovo elemento, poi si calcola il resto in modo tale che il risultato sia sempre un numero compreso fra 0 e DIMCODA-1. L’elemento, attualmente conservato in un deposito temporaneo, viene poi copiato, in 7, nella posizione individuata da fondo.

L’elemento da eliminare si trova, come messo in evidenza in 9, nella posizione testa che è calcolata in 8 sempre tenendo conto che si tratta di una struttura circolare.