Il tipo di dati  astratto Coda
Una coda  (queue)  è un sequenza di zero o più elementi 
 
<A1, A2, ..., An>

in cui è possibile  aggiungere elementi soltanto ad un estremo della sequenza, detto fondo (back), ed è possibile toglierli soltanto dall'altro estremo, detto testa (front).

Politica di accesso:

FIFO (First In, First Out)
[primo elemento inserito, primo elemento rimosso]

Esempi: una coda di persone alla cassa di un cinema, una coda di ordini da evadere, una coda di file da stampare, ...
 

...una coda all'ingresso di un concerto... ...di un palazzo...
...anche una coda di macchine... ma non sempre!

Presentazione grafica di una coda
Rappresentiamo una coda come una sequenza di caselle contenenti i suoi elementi, nell'ordine in cui sono stati inseriti. La casella più a sinistra è la testa (front), quella più a destra è il fondo (back).
 
 
<A, B, C, D, E> 
    
 A   B   C   D   E 
  front         back
coda di cinque elementi vista come sequenza e sua rappresentazione grafica
 

Operazioni su code
Le operazioni definite su una coda sono le seguenti :
  • Inserimento di un elemento in fondo alla coda (chiamata enqueue)

    •  
  • Estrazione dell'elemento in testa alla coda (chiamata dequeue)

    •  
  • Lettura dell'elemento in testa alla coda, senza eliminarlo (chiamata peek)

    •  
  • Controllo se la coda è vuota oppure no (predicato isEmpty)

    •  
  • Svuotamento della coda (chiamata clear)


Si noti che pile e code hanno essenzialmente le stesse operazioni, 
ma con significato (e quindi nome) diverso!

Code in Java: l'interfaccia Queue
La seguente interfaccia definisce il tipo di dati astratto Queue 


public interface Queue<E> {
    /**
     * Inserisce un oggetto in fondo alla coda.
     * @param x  l'oggetto da inserire.
     * @return   l'oggetto inserito.
     * @exception IllegalArgumentException se l'argomento passato è null
     */
    E enqueue( E x );

    /**
     * Rimuove e restituisce l'oggetto in testa alla coda.
     * @return   l'oggetto in testa.
     * @exception NoSuchElementException con coda vuota.
     */
    E dequeue( );

    /**
     * Restituisce l'oggetto in testa alla coda senza estrarlo.
     * @return   l'oggetto in testa.
     * @exception NoSuchElementException con coda vuota.
     */
    E peek( );

    /**
     * Verifica che la coda sia logicamente vuota.
     * @return  true se la coda è vuota;
     *          false altrimenti.
     */
    boolean isEmpty( );

    /**
     *  Svuota la coda.
     */
    void clear( ); 
}
 

Si noti che fino a Java 1.4 le code non erano presenti nelle API, a partire da Java 1.5 sono state introdotte l'interfaccia Queue e numerose classi che la implementano, ma l'approccio è rivolto a risolvere problemi di sincronizzazione di programmi concorrenti e il loro studio esula da questo contesto.


Esempio di uso di code
Assumiamo che 
  • la classe VectorQueue implementi la nostra interfaccia Queue
  • A, B, C e K siano variabili di tipo String
Invocazione di metodo
Stato della coda
dopo l'invocazione
Risultato
(Costruzione dello) Stato iniziale

Queue<String> coda = new VectorQueue<String>();
coda.enqueue(A);
coda.enqueue(B);
 A  B 
 
  
Estrai

coda.dequeue();
 B 
 
A
Inserisci C

coda.enqueue(C);
 B  C 
 
C
Inserisci K

coda.enqueue(K);
 B   C   K 
 
K
Vuota?

coda.isEmpty();
 B   C   K 
 
false
Leggi

coda.peek();
 B   C   K 
 
B
Estrai

coda.dequeue();
 C   K 
 
B
Svuota

coda.clear();
 
 
  
Vuota?

coda.isEmpty();
 
true
 

Esempio: scorrere una coda
Supponiamo di voler esaminare tutti gli elementi presenti in una coda, ad esempio per stamparli. Poiché la politica di accesso FIFO consente di leggere solo l'elemento in testa alla coda,  dobbiamo necessariamente estrarre tutti gli elementi dalla coda con dequeue, come nel metodo seguente: 

    public void printDestroy (Queue<E> que) {
        if (que == null)
            throw new IllegalArgumentException("printDestroy");

        System.out.print("Contenuto della coda:");
        while ( ! que.isEmpty() )
            System.out.print(" " + que.dequeue()); 
    }

NB: poiché la nostra Queue<E> non implementa Iterable non è possibile usare il for semplificato per scorrere la coda.

 

Esempio: stampa non distruttiva
Attenzione: Il metodo printDestroy distrugge la coda, che risulterà vuota anche per il metodo chiamante. Una realizzazione più ragionevole dovrebbe ripristinare il contenuto della coda prima di restituire il controllo: 

    public void print (Queue<E> que) {
        if (que == null)
            throw new IllegalArgumentException("print");

        // crea una coda ausiliaria 
        Queue<E> qaux = new VectorQueue<E>();
        System.out.print("Contenuto della coda:"); 
        while ( ! que.isEmpty() ) {
            qaux.enqueue( que.peek() ); // salva l'elemento in qaux
            System.out.print(" " + que.dequeue() ); // estrae e stampa
        }

        // ripristina la coda originaria (svuotando qaux)
        while ( ! qaux.isEmpty() )
            que.enqueue( qaux.dequeue() ); 
    }

Esercizi sull'uso di code
Per gli esercizi che seguono si usi l'interfaccia Queue.java e la realizzazione delle code fornita dalla classe VectorQueue.java.

Nota Bene

  • la signature dei moduli NON può essere modificata.

  • Si può usare la classe Stack<E>

1)    Si definisca un metodo con la seguente signature 

     /** 
      * Restituisce una nuova coda, che contiene i valori  
      * della coda passata per argomento, ma in ordine inverso.  
      * La coda originale non viene modificata.  
      */ 
     public Queue<E> reverse(Queue<E> input) { 
         // DA DEFINIRE 
     }
}

2)    Si definisca un metodo con la seguente signature 

    /** 
     * Restituisce una copia della coda passata come parametro.
     * La coda originale non viene modificata.
     */ 
    public Queue<E> clone( Queue<E> daClonare ) {
          // DA DEFINIRE 
    }
}

3)   Si scriva una classe che prova i 4 metodi: printDestroy(), print(), reverse(), clone()


Code a Priorità
Le Code a Priorità sono un particolare tipo di coda in cui gli elementi vengono estratti non in base all'ordine di inserimento ma in base al valore di una quantità reale detta priorità.

La testa della coda è l'elemento con la priorità più bassa.

A partire dalla versione 1.5 le Api di Java forniscono un'implementazione efficiente delle code a Priorità, basata sull'uso degli Heap. Per una descrizione esauriente si rimanda alla documentazione ufficiale, qui ci limitiamo a segnalare un costruttore e alcuni metodi.

La classe 

   PriorityQueue<E>

implementa le interfacce java.util.Iterable<E>, java.util.Collection<E>, java.util.Queue<E>.

Un possibile costruttore è 

   PriorityQueue(int initialCapacity, Comparator<E> comparator)

che costruisce una coda a priorità vuota, con capacitagrave; iniziale initialCapacity, i cui elemementi saranno ordinati in base al Comparator<E> comparator

Il metodo 

   add(E item)
inserisce un elemento di tipo E, aumentando la capacità della coda se necessario.

Il metodo 

   E poll()
restituisce, togliendolo dalla coda, l'elemento con la priorità più bassa, oppure null se la coda è vuota.

Il metodo 

   E peek()
restituisce, senza toglierlo dalla coda, l'elemento con la priorità più bassa, oppure null se la coda è vuota.

Inoltre, tra gli altri, vi sono i metodi clear(), isEmpty(), toArray(), size(), dall'ovvio significato.

Esempio (schematico) di uso di una java.util.PriorityQueue.

Per un esempio completo si veda il documento PDF sulla Ricerca in spazi di stati. 

import java.util.Comparator;
import java.util.PriorityQueue;

public class UsaCodaPriorita<E> implements Comparator<E>{

   private PriorityQueue<E> q;         // la coda 

   final static int limitSize = 1000;  // la dimensione iniziale della coda

	
   public UsaCodaPriorita() {
      q = new PriorityQueue<E>(limitSize, this);

// ...... inserimento di un elemento 
      E item1 = new E(...) ;
      q.add(item1);

// ...... estrazione di un elemento 
      E item2 = q.poll();
   }

	
/**
 * Comparator per la  PriorityQueue
 * Si presuppone che il tipo E abbia un metodo con firma
 *
 *    double value()
 *
 * @return il segno della differenza arg0.value()-arg1.value()
 */
   public int compare(E arg0, E arg1) {
      return (int) Math.signum(arg0.value()-arg1.value());
   }

}