Realizzazione di code con array
Esamineremo una sola realizzazione delle code, la classe ArrayQueue, in cui gli elementi di una coda sono memorizzati 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.
Ma la realizzazione risulta più complessa di quella delle pile... ed è proprio per questo che è istruttivo vederla!

L'interfaccia Coda<E> è del tutto equivalente alla Queue<E> già vista. 


public interface Coda<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(); 

    /**
     * Conversione in array
     * @return un array di Object con gli elementi della struttura
     */
    Object[] toArray(); 
}

Scelte progettuali I
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 
 

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: se la coda contiene n elementi, bisogna fare n-1 assegnamenti! Si può fare di meglio...

Scelte progettuali II
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: ora la complessità è costante.

 

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 CodaArray
Si consiglia di guardare il codice completo della classe CodaArray solo dopo avere provato a scriverne una propria.

Qui diamo solo il metodo increment che realizza la scansione circolare.
  
    // Metodo interno per l'incremento circolare. Restituisce x+1 oppure 0.
    int increment(int x) {
        return (x + 1) % theArray.length;
    }

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 doubleArray viene invocato sempre più raramente.


Esercizi
Si consideri la seguente interfaccia
  
public interface RevCoda<E> extends Coda<E> {

    /**
     * Rovescia il contenuto della coda
     */
    void reverse();
}

Si scriva la classe RevCodaArray che estende CodaArray e implementa l'interfaccia RevCoda in modo tale che il metodo reverse() rovesci la coda su cui viene chiamato.

SOLUZIONE