Il tipo di dato astratto coda.
Una coda (queue in Inglese) è un tipo di dato parametrico, omogeneo e dinamico. Una coda è costituita da una sequenza di variabili o elementi (tutte dello stesso tipo, e quindi omogenee) in cui l'inserimento e l'eliminazione di elementi avviene secondo la politica FIFO (First In First Out).
L'inserimento e l'eliminazione di elementi avvengono secondo la regola seguente: l'elemento eliminato (o letto) per primo è quello che è stato inserito per primo. Possiamo anche immaginare che l'inserimento avvenga ad una estremità della coda e l'accesso ad un elemento o l'eliminazione di un elemento avvenga all'altra estremità.
Le code vengono utilizzate ad esempio per gestire dei servizi rispettando l'ordine di arrivo delle richieste, per garantire cioè che l'ordine con cui arrivano le richieste (inserendole in una coda) corrisponda cronologicamente all'ordine con cui tali richieste sono servite. Si pensi ad esempio ad un processo gestore di una risorsa in un sistema operativo, come l'invio di stampe ad una unica stampante condivisa, oppure si pensi ad un server su web per la prenotazione di un posto su un aereo, un treno, ecc.
Una coda è un tipo di dato dinamico in quanto viene creata inizialmente vuota (mediante un operatore emptyqueue), poi gli elementi vengono aggiunti uno alla volta mediante una operazione di inserimento (operatore enqueue). Teoricamente può essere inserito un numero di elementi non limitato in una coda. Gli elementi possono essere eliminati dalla coda uno alla volta con una operazione di eliminazione (operatore dequeue). È possibile verificare se una coda è vuota mediante un operatore booleano codavuota. È possibile leggere il valore della prima variabile inserita, quella più vecchia cronologicamente, senza modificarlo mediante l'operatore top.
Sintassi degli operatori (parametrici rispetto ad un tipo T):
emptyqueue: T:type --> Coda(T) enqueue: Coda(T) x T --> Coda(T) dequeue: Coda(T) --> Coda(T) top: Coda(T) --> T
codavuota: Coda(T) --> boolean
Ad esempio per inserire due valori in una coda di interi possiamo utilizzare la seguente sequenza di operazioni: enqueue(enqueue(emptyqueue(int), -4), 8) i valori inseriti sono nell'ordine -4, 8 cioe' prima -4 (cronologicamente) e poi 8. Di conseguenza, secondo la politica FIFO, la coda
dequeue(enqueue(enqueue(emptyqueue(int), -4), 8)) è equivalente a: enqueue(emptyqueue(int), 8) in quanto viene rimosso per primo il valore più 'vecchio', o inserito per primo.
E' possibile descrivere il comportamento degli operatori con le seguenti equazioni, che
rappresentano un frammento della specifica algebrica per il tipo di dato coda (T e' un tipo, X, C, Y variabili):
1) top(enqueue(emptyqueue(T), X))= X
2) top(enqueue(enqueue(C,X), Y))= top(enqueue(C,X)) 3) dequeue(enqueue(emptyqueue(T), X))= emptyqueue(T)
4) dequeue(enqueue(enqueue(C,X), Y))= enqueue(dequeue((enqueue(C,X))),Y) Queste 4 equazioni descrivono il comportamento delle funzioni top e dequeue.
La specifica è parziale, in quanto non definisce ad esempio cosa succede se si applica la funzione top o dequeue alla coda vuota.
Le suddette 4 equazioni permettono di semplificare (valutare) espressioni costruite a partire dagli operatori sulla coda, interpretandole come regole di semplificazione. Se consideriamo una
espressione sulle code, possiamo semplificarne una sottoespressione 's' mediante una 'istanza' di una delle 4 equazioni. La istanza si determina sostituendo uniformemente i simboli di variabile nella parte sinistra della equazione da applicare con altre espressioni in modo tale da rendere la parte sinistra della equazione identica ad 's'. A questo punto si può sostituire 's' con la istanza della parte destra della equazione.
Ad esempio dequeue(enqueue(emptyqueue(int), -4)) si può semplificare con la equazione (3), mediante l'istanza della equazione in cui T è int e X è -4, ottenendo l'espressione semplificata emptyqueue(int) non ulteriormente semplificabile.
La prima implementazione in Java che vedremo è quella classica sequenziale (funzionale) che utilizza 3 strutture dati: un vettore (array monodimensionale) e due variabili intere, che
rappresenteranno rispettivamente gli indici della prima posizione libera nel vettore (indice coda) utilizzabile per aggiungere un nuovo elemento nella coda e della prima posizione (indice testa) occupata all'interno della coda. Questa posizione indicherà l'elemento da leggere mediante
l'operazione top, o l'elemento da eliminare nel caso di un'operazione di dequeue (la posizione più vecchia cronologicamente).
Nella prima implementazione faremo riferimento ad un vettore logicamente 'circolare'. Questo significa che la posizione finale del vettore avrà come sua successiva posizione logica quella di indice zero (prima posizione del vettore). Questo per evitare di dover far operazioni di rilocazione delle variabili contenute nel vettore quando le ultime posizioni sono occupate, mentre le prime posizioni sono libere. Per modellare questa circolarità le operazioni aritmetiche sugli indici testa e coda avverranno sempre modulo la dimensione del vettore, prendendo il resto della divisione intera rispetto alla dimensione del vettore.
Faremo inoltre l'ipotesi di rappresentare la coda vuota col fatto che gli indici di coda e di testa sono identici, e per evitare ambiguità tra la situazione di coda piena e di coda vuota faremo l'ipotesi di dover lasciare sempre almeno una posizione libera nel vettore di implementazione. In altre parole la coda risulterà piena quando l'indice di coda sarà separato da quello di testa da esattamente una posizione libera (ossia aggiungendo 1 all'indice coda, modulo la dimensione del vettore, diventa identico all'indice testa).
Questa implementazione è molto efficiente per le operazioni primitive della coda, che risultano tutte effettuabili con un numero piccolo e costante di istruzioni Java. Rispetto ad una implementazione dinamica ha lo svantaggio di imporre un numero massimo di valori inseribili nella coda, dato dalla dimensione del vettore meno uno. Inoltre anche se la coda è solo parzialmente utilizzata viene allocato in memoria l'intero vettore necessario per la rappresentazione.
--- Abbiamo detto che la coda è un tipo parametrico.
Semplificando possiamo dire che una coda si dice parametrica in quanto le operazioni non dipendono dal tipo degli elementi, che potrebbe essere passato come parametro. La prima implementazione che vedremo comunque si riferirà a code realizzate su un tipo specifico, ad esempio code di valori interi, e quindi il codice della implementazione sarà diverso e dovrà essere modificato manualmente e ricompilato quando si desideri cambiare il tipo delle variabili interne alla coda, ad esempio per realizzare una coda di caratteri.
Nota: in Java esistono i tipi generici (dalla release 5 in poi), che permetterebbero una implementazione parametrica della coda, che non richiede di modificare manualmente il codice quando si cambia il tipo delle variabili interne alla coda. Vedremo successivamente che è possibile generalizzare facilmente la nostra prima implementazione e passare ad una soluzione Java parametrica. Tuttavia la soluzione parametrica non permette di utilizzare direttamente i tipi primitivi, ma richiede l'utilizzo di classi di sistema che 'ricostruiscono' tali tipi.
