Code

Note

Una coda (Queue) è una struttura dati con le seguenti operazioni:

• Enqueue(Q,e): aggiunge e alla fine della coda
• Dequeue(Q): restituisce l’elemento all’inizio della coda, cancellandolo dalla stessa
• Empty(Q): restituisce true se la coda è vuota

Come nel caso della pila, è possibile realizzare una coda sia con una lista che con un vettore.

Implementazione con una lista

Se lo stoccaggio dei dati è effettuato negli elementi di una lista, teniamo traccia dell’ultimo elemento della lista (oltre al primo) con un puntatore tail. Le operazioni diventano:

• Enqueue(Q,e): inserisci l’elemento e in coda alla lista, aggiornando tail
• Dequeue(Q): restituisci l’elemento in testa se diverso da NIL, cancellandolo e aggiornando head
• Empty(Q): Restituisci head = tail

Implementazione con un vettore

Se lo stoccaggio dei dati è effettuato nelle celle di un vettore lungo , teniamo traccia della posizione dove va inserito un nuovo elemento e di quella dell’elemento più vecchio con due indici tail e head e del numero di elementi contenuti n. Gli indici vengono incrementati di :

• Enqueue(Q,e): se , inserisci l’elemento in A[tail], incrementa e tail
• Dequeue(Q): se , restituisci A[head] corrente, decrementa n, incrementa head
• Empty(Q): restituisci n = 0

Per ampliare lo stoccaggio è necessaria un allocazione fresca e copia degli elementi estraendoli con Dequeue(Q)