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 lista di ordini da evadere, ...
 
 
 
 

 

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>
 
A
 B C
 
 

Operazioni su code
La specifica del TDA coda comprende normalmente le seguenti operazioni:
  • Inserimento di un elemento in fondo alla coda (enqueue)
  • Estrazione dell'elemento in testa alla coda (dequeue)
  • Lettura dell'elemento in testa alla coda, senza eliminarlo (front)
  • Svuotamento della coda (clear)
  • Controllo se la coda è vuota oppure no (isEmpty)
Esempio di estrazione e inserimento: 
A
 B C
 coda iniziale
B C
 dopo l'estrazione della testa
B
 C D
 dopo l'inserimento di D

Si noti che pile e code si distinguono solo per il significato delle operazioni!

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

    // Inserisce un oggetto in fondo alla coda
    Object enqueue ( Object x ) ;

    // Rimuove e restituisce l'oggetto in testa alla coda
    Object dequeue ( ) ;

    // Restituisce l'oggetto in testa alla coda senza rimuoverlo
    Object front ( ) ;

    // Verifica che la coda sia logicamente vuota.
    boolean isEmpty ( ) ;

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

Significato dei metodi
Il significato dei metodi (la loro semantica) viene spiegato (in modo informale) dai commenti al codice, leggibili anche con un browser grazie a javadoc: 
 
/**
* Inserisce un oggetto in fondo alla coda.
* @param x  l'oggetto da inserire.
* @return   l'oggetto inserito.
* @exception  IllegalArgumentException se l'argomento passato
*            &egrave; <code>null</code>. 
*/
Object enqueue ( Object x ) ;

Quindi:

  • il paramentro attuale viene inserito in fondo alla coda;
  • tale parametro viene anche restituito alla fine del metodo;
  • viene lanciata un'eccezione di tipo IllegalArgumentException  [locale, Medialab, Sun] se il parametro vale null.
Vediamo la documentazione di dequeue:
 
/**
* Rimuove e restituisce l'oggetto in testa alla coda.
* @return   l'oggetto in testa.
* @exception EmptyQueueException con coda vuota.
*/
Object dequeue ( ) ;

Si noti il metodo lancia un'eccezione se viene eseguito da una coda vuota. L'eccezione EmptyQueueException è definita all'interno del package lab2.Exceptions.

Esempio: scorrere una coda
Supponiamo di voler esaminare tutti gli elementi presenti in una coda, ad esempio per stamparli. L'uso di un iteratore sulla coda (come anche su di una pila) sarebbe improprio, visto che permetterebbe di aggirare la politica di accesso (LIFO per pile, FIFO per code).

Il seguente metodo stampa tutti gli elementi della coda passata per argomento, estraendoli con dequeue:
 
public static void printDestroy (Queue que) {
   if (que == null)
      throw new IllegalArgumentException("printDestroy");
   System.out.print("Contenuto della coda:"); 
   while ( ! que.isEmpty( ))
      System.out.print(" " + que.dequeue());
}

Il ciclo while potrebbe anche essere scritto nel seguente modo, sfruttando l'eccezione EmptyQueueException:
 
// soluzione alternativa con while con eccezione
try{
    while ( true ) 
       System.out.print ( " " + que.dequeue());
} catch ( EmptyQueueException e ) {}
 

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 static void print (Queue que) {
   if (que == null)
       throw new IllegalArgumentException("print");
         // creo una coda ausiliaria 
   Queue qaux = new ArrayQueue();
   System.out.print("Contenuto della coda:"); 
   while ( ! que.isEmpty( )){
       qaux.enqueue(que.front());  // salvo l'elemento 
       System.out.print(" " + que.dequeue()); // lo stampo
   }
         // ripristino la coda originaria
   while ( ! qaux.isEmpty( ))
       que.enqueue(qaux.dequeue()); 
}

Esercizi sull'uso di code
1) Si definisca una classe con la seguente struttura:
 
 
public class ReverseQ {
    /**
    * Restituisce una nuova coda, che contiene i valori 
    * della coda passata per argomento, ma in ordine inverso. 
    * La coda originale non viene modificata. 
    */
    public static Queue reverse( Queue input ) {
        // DA DEFINIRE
    }
}

2)    Si fornisca una implementazione della seguente classe astratta:
 
import lab2.*;
import lab2.Exceptions.*;

abstract class IntegerQueueInterface {
    protected Queue prior ;

    public IntegerQueueInterface( Queue input ) {
        prior = input ;
    }

    /**
     * Restituisce il più alto elemento della coda, assumendo
     * che gli elementi contenuti siano istanze di Integer.
     * Lancia una EmptyQueueException se 'prior' è null
     * oppure è la coda vuota.
     */
    abstract Integer maxDequeue( ) ;

    /**
     * Ordina il contenuto della coda, assumendo che
     * gli elementi contenuti siano istanze di Integer
     */
     abstract void ordina( ) ;
}


3)    Si definisca una classe con la seguente struttura:
 
 
public class CloneQ {
    /**
     * Restituisce una copia della coda passata come parametro
     */
    public static Queue clone( Queue daClonare ) {
        // DA DEFINIRE
    }
}