Realizzazione del TDA Coda con array
Ricordiamo ancora che realizzare il Tipo di Dati Astratto Coda (cioè l'interfaccia Java Queue) significa fornire un Tipo di Dati (una classe) le cui operazioni (metodi) rispettino la specifica dei corrispondenti metodi astratti in Queue, cioè il tipo e il significato descritto informalmente.

Esamineremo una sola realizzazione del TDA Coda, ArrayQueue, in cui una istanza (cioè una coda) memorizza i suoi elementi in un array. 

Come per le pile,

  • Poiché il numero di elementi di una coda può crescere a piacere mentre la dimensione di un array è fissata al momento della creazione, quando l'array si riempie, lo sostituiamo con uno più grande.

    •  
  • Utilizziamo un array e non un Vector per avere controllo sulla complessità delle varie operazioni.
Ma la realizzazione è un po' più complessa di quella delle pile...

Scelte progettuali (1a)
Prima idea:
  • mettiamo gli elementi della coda nelle prime posizioni dell'array (di lunghezza n)
  • ricordiamo la posizione dell'ultimo elemento inserito nella variabile back
Stato della coda
<A, B, C>
 
Rappresentazione con array (1)
A
B
C
          
0
1
2
3
4
...
  
n-1
back
 2 
 
 

Scelte progettuali (1b)
Per le operazioni:
  • enqueue: come la push delle pile (con raddoppio dell'array se necessario). L'effetto di enqueue(D) sarebbe:
A
B
C
 D
        
0
1
2
3
4
...
  
n-1
back
 3 
  • dequeue: occorre eliminare l'elemento in testa e spostare tutti gli altri. dequeue()restituirebbe A e modificherebbe l'array così:
B
C
D
 
        
0
1
2
3
4
...
  
n-1
back
 2 

PROBLEMA: la dequeue ha complessità lineare nel numero di elementi della coda. Si può fare di meglio...

Scelte progettuali (2a)
Seconda idea:
  • mettiamo gli elementi della coda in posizioni contigue dell'array (non necessariamente all'inizio)
  • oltre a back, usiamo una variabile front per indicare il prossimo elemento da estrarre
Stato della coda
<A, B, C>
 
Rappresentazione con array (2)
A
B
C
          
0
1
2
3
4
...
  
n-1
 front
 0 
 back
 2 
 
  • enqueue: come prima (inserisce e incrementa back, se necessario dopo aver raddoppiato l'array);
  • dequeue: restituisce l'elemento di posizione front e incrementa front: la complessità è costante.

Scelte progettuali (2b)
PROBLEMA: Cattiva gestione della memoria. Si rischia di raddoppiare l'array anche se la coda contiene pochi elementi. Ad esempio, potremmo avere
 
Stato della coda
<P,Q,R,S>
 
A
B
C
...
P
Q
R
S
0
1
2
...
n-4
n-3
n-2
n-1
 front
 n-4 
 back
 n-1 
 
L'operazione enqueue(T) raddoppierebbe l'array. Si noti che invece si potrebbero riutilizzare le posizioni 0, 1, ..., n-5 dell'array che contengono elementi già estratti.

Questo ci porta alle seguenti scelte finali...

Scelte progettuali (finali)
  • Gestiamo l'array in modo circolare: concettualmente, dopo la posizione n-1 c'è la posizione 0. Questo si ottiene incrementando gli indici modulo n.
  • Gli elementi della coda sono posti in posizioni contigue dell'array circolare: front indica il prossimo elemento da estrarre, back l'ultimo inserito.
  • Usiamo una variabile ausiliaria size che memorizza il numero di elementi della coda. Invariante: (size == (back - front + n + 1) % n)
Stato della coda
<P,Q,R,S,T,U>
 
T
U
C
...
P
Q
R
S
0
1
2
...
n-4
n-3
 n-2
n-1
 front
 n-4 
 back
 1 
 size
 6 
 
  • La coda è vuota se e solo se size vale 0.
  • In una enqueue, raddoppiamo l'array solo se size è uguale alla sua dimensione.
  • Quando si raddoppia l'array, gli elementi della coda vengono ricopiati nelle posizioni 0,1,2,..., indipendentemente dalla posizione nell'array originale.

La classe ArrayQueue
Il codice della realizzazione diventa, a questo punto, quasi autoesplicativo.
Tutte le operazioni hanno complessità costante nel caso pessimo [O(1)], tranne enqueue che ha complessità lineare, O(n). Tuttavia enqueue ha complessità ammortizzata costante, poiché il metodo doubleQueue viene invocato raramente.
.
 
/**
 * Classe ArrayQueue:
 *
 * Realizzazione del TDA Coda mediante array circolare.
 */

public class ArrayQueue implements Queue {
    static final int DEFAULT_SIZE = 32 ;

    protected Object [ ] theArray;
    protected int        size, front, back ;

    /**
    * Costruttore della coda.
    */
    public ArrayQueue ( ) {
        theArray = new Object[ DEFAULT_SIZE ] ;
       size  = 0 ;
        front = 0 ;
        back  = -1 ;
    }

    /**
    * Verifica che la coda sia logicamente vuota.
    * @return  <code>true</code> se la coda &egrave; vuota;
    *          <code>false</code> altrimenti.
    */
    public boolean isEmpty ( ) {
        return size == 0 ;
    }

    /**
    *  Svuota la coda.
    */
    public void clear ( ) {
        size  = 0 ;
        front = 0 ;
        back  = -1 ;
    }

    /**
    * Restituisce l'oggetto in testa alla coda senza estrarlo.
    * @return   l'oggetto in testa.
    * @exception EmptyQueueException con coda vuota.
    */
    public Object front ( ) {
        if ( isEmpty ( ) )
            throw new EmptyQueueException ( ) ;
        return theArray[ front ] ;
    }

    /**
    * 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>. 
    */
    public Object enqueue ( Object x ) {
        if ( x == null )
            throw new IllegalArgumentException ( ) ;
        if ( size == theArray.length )
         doubleQueue ( ) ;
        size++ ;
        back = increment ( back ) ;
        return theArray[ back ] = x ;
    }

    /**
    * Rimuove e restituisce l'oggetto in testa alla coda.
    * @return   l'oggetto in testa.
    * @exception EmptyQueueException con coda vuota.
    */
    public Object dequeue ( ) {
        if ( isEmpty ( ) )
            throw new EmptyQueueException ( ) ;
        size-- ;
      Object item = theArray[ front ] ;
        front = increment ( front ) ; 
        return item ;
    }

    /**
    * Metodo interno per raddoppiare la dimensione di theArray.
    */
    protected void doubleQueue ( ) {
      Object [ ] newArray ;

        newArray = new Object[ theArray.length * 2 ] ;
        for ( int i = 0; i < size; i++, front = increment ( front ) )
            newArray[ i ] = theArray[ front ] ;
        theArray = newArray ;
        front = 0 ;
        back = size - 1 ;
    }

    /**
    *Metodo interno per l'incremento circolare. Restituisce x+1 oppure 0.
    */
    protected int increment ( int x ) {
        return ( x + 1 ) % theArray.length ;
    }
}

Esercizi su realizzazione di code
1) Si fornisca una implementazione dell'interfaccia Queue, utilizzando la classe Vector.

2) Si consideri la seguente interfaccia
 
import lab2.*;
public interface ReverseQueue extends Queue {
    /**
    * Rovescia il contenuto della coda
    * @return  una nuova coda, che contiene i valori della coda
    * che esegue il metodo, ma in ordine inverso
    */
    Queue reverse ( ) ;
}

dove il metodo introdotto rovescia il contenuto di una coda, senza alterare la coda originale. 
Si definisca una classe ArrayReverseQueue, che estenda ArrayQueue ed implementi l'interfaccia.

3) Si consideri la seguente interfaccia
 
import lab2.*;
public interface IntegerQueue extends Queue {
    /**
    * Restituisce il massimo elemento della coda, assumendo
    * che gli elementi contenuti siano istanze di Integer
    */
    Integer maxDequeue ( ) ;

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

dove i metodi introdotti devono rispettivamente cercare il massimo fra gli elementi presenti nella coda (sollevando l'eccezione EmptyQueueException nel caso la coda sia vuota), ed ordinare il contenuto di una coda, assumendo che gli elementi contenuti siano istanze di Integer.
Si definisca una classe ArrayIntegerQueue, che estenda ArrayQueue ed implementi l'interfaccia.

4) Si fornisca una realizzazione ListQueue dell'interfaccia Queue utilizzando una lista concatenata per memorizzare gli elementi di una coda. Come per la classe ListStack, i nodi della lista saranno istanze della classe ListNode. Poiché enqueue e dequeue lavorano sulle estremità opposte della coda, sarà opportuno avere in ogni istanza di  ListQueue due puntatori alla lista: uno al primo elemento e uno all'ultimo.