Queue

La Queue (o Coda) è una struttura dati di tipo FIFO (First In First Out), ovvero dove il primo oggetto che viene inserito è il primo che esce. Questa struttura dati contiene due operazioni fondamentali:

• enqueue: inserisce un elemento nella coda
• dequeue: preleva un elemento dalla coda

Una implementazione semplice ma molto lenta consiste nell'inserire gli elementi in un array partendo dal primo ed estrarre sempre il primo elemento, facendo traslare tutti gli altri.

Proprio questa necessaria traslazione è molto lenta, poiché comporta un numero di operazioni pari al numero di elementi. Una implementazione più veloce consiste nell'utilizzare un array circolare.

Questo tipo di array contiene due puntatori, chiamati tail e head (coda e testa) che indicano l'inizio e il termine del gruppo di elementi che sono stati inseriti. Quando uno dei due puntatori raggiunge il termine dell'array torna alla prima posizione.

Un array è quindi vuoto quando i due puntatori occupano la stessa posizione. Analogamente allo stack, il puntatore head fa riferimento alla prossima posizione dove si può inserire il nuovo elemento. In aggiunta il puntatore tail indica il prossimo elemento che verrà estratto, ed indica anche il primo elemento dell'insieme.

Implementazione

Nell'implementazione vengono utilizzati due puntatori chiamati tail e head. Ogni puntatore avanza di una posizione a seconda dell'operazione effettuata. Poiché l'array è circolare, il puntatore che supera l'ultima posizione viene portato nella prima posizione. Questa procedura può essere compiuta agevolmente attraverso l'operatore modulo, che in C# è '%'. In questo modo, se la lunghezza dell'array è N, le posizioni degli elementi appartengono all'intervallo 0, N-1. Quando un puntatore giunge nella posizione N-1 e deve essere avanzato, si aumenta di una unità il suo indice e si calcola il modulo N, quindi si ha (N-1) + 1 mod N = N mod N = 0.

La collezione è vuota quando i due puntatori puntano allo stesso elemento, mentre è piena quando il puntatore head è di una posizione indietro a quello del puntatore tail oppure quando il puntatore head è al termine dell'array e il puntatore tail è al suo inizio. La coda quindi può contenere N-1 elementi. Il sacrificio di un elemento permette di distinguere la condizione di coda piena dalla condizione di coda vuota.

interface IQueue
{
    void Enqueue(object x);
    object Dequeue();
}    
 
class Queue : IQueue
{
    object[] data;
        int tail, head;
 
    public bool IsEmpty
    {
        get
        {
            return (tail == head);
        }
    }
 
        public Queue(int length)
        {
            data = new object[length];
            tail = 0;
            head = 0;
        }
 
        public void Enqueue(object x)
        {
                if ((head == tail - 1) || (head == data.Length && tail == 0))
                {
                    Console.Out.WriteLine("Coda piena");
                }
                else
                {
                    data[head] = x;
                    head = (head + 1) % data.Length;
                }
        }
 
        public object Dequeue()
        {
                if (head == tail)
                {
                    Console.Out.WriteLine("Coda vuota");
                    return null;
                }
                else
                {
                    int oldtail = tail;
                    tail = (tail + 1) % data.Length;
                    return data[oldtail];
            }
    }
}