Lezione XXVII lu 14-Nov-2005 adt coda (Queue)



Scaricare 486 b.
Pagina1/8
02.02.2018
Dimensione del file486 b.
  1   2   3   4   5   6   7   8


Lezione XXVII Lu 14-Nov-2005 ADT Coda (Queue)


Coda (queue)

  • In una coda (queue) gli oggetti possono essere inseriti ed estratti secondo un comportamento definito FIFO (First In, First Out)

    • il primo oggetto inserito è il primo a essere estratto
    • il nome è stato scelto in analogia con persone in coda
  • L’unico oggetto che può essere ispezionato è quello che verrebbe estratto

  • Esistono molti possibili utilizzi di una struttura dati con questo comportamento

    • la simulazione del funzionamento di uno sportello bancario con più clienti che arrivano in momenti diversi userà una coda per rispettare la priorità di servizio


Coda (queue)

  • I metodi che caratterizzano una coda sono

    • enqueue() per inserire un oggetto nella coda
    • dequeue() per esaminare ed eliminare dalla coda l’oggetto che vi si trova da più tempo
    • getFront() per esaminare l’oggetto che verrebbe eliminato da dequeue(), senza estrarlo
  • Infine, ogni ADT di tipo “contenitore” ha i metodi



Coda (queue)

  • Si notino le similitudini con la pila

    • enqueue() corrisponde a push()
    • dequeue() corrisponde a pop()
    • getFront() corrisponde a top()


Coda (queue)



Coda (queue)

  • Per realizzare una coda si può usare una struttura di tipo array “riempito solo in parte”, in modo simile a quanto fatto per realizzare una pila

  • Mentre nella pila si inseriva e si estraeva allo stesso estremo dell’array (l’estremo “destro”), qui dobbiamo inserire ed estrarre ai due diversi estremi

    • decidiamo di inserire a destra ed estrarre a sinistra


Coda (queue)

  • Come per la pila, anche per la coda bisognerà segnalare l’errore di accesso a una coda vuota e gestire la situazione di coda piena (segnalando un errore o ridimensionando l’array)

  • Definiamo

    • EmptyQueueException e FullQueueException






Coda (queue)

  • Questa semplice realizzazione con array, che abbiamo visto essere molto efficiente per la pila, è al contrario assai inefficiente per la coda

    • il metodo dequeue() è O(n), perché bisogna spostare tutti gli oggetti della coda per fare in modo che l’array rimanga “compatto”
    • la differenza rispetto alla pila è dovuta al fatto che nella coda gli inserimenti e le rimozioni avvengono alle due estremità diverse dell’array, mentre nella pila avvengono alla stessa estremità


Coda (queue)

  • Per realizzare una coda più efficiente servono due indici anziché uno soltanto

    • un indice punta al primo oggetto della coda (front) e l’altro indice punta al primo posto libero dopo l’ultimo oggetto della coda (back)
  • In questo modo, aggiornando opportunamente gli indici, si ottiene la realizzazione di una coda con un “array riempito solo nella parte centrale” in cui tutte le operazioni sono O(1)

    • la gestione dell’array pieno ha le due solite soluzioni, ridimensionamento o eccezione






Coda (queue)

  • Per rendere la coda ridimensionabile, usiamo la stessa strategia vista per la pila, estendendo la classe FixedArrayQueue e sovrascrivendo il solo metodo enqueue()



Prestazioni della coda

  • La realizzazione di una coda con un array e due indici ha la massima efficienza in termini di prestazioni temporali, tutte le operazioni sono O(1), ma ha ancora un punto debole

  • Se l’array ha N elementi, proviamo a

    • effettuare N operazioni enqueue()
  • e poi

    • effettuare N operazioni dequeue()
  • Ora la coda è vuota, ma alla successiva operazione enqueue() l’array sarà pieno

    • lo spazio di memoria non viene riutilizzato


Coda con array circolare

  • Per risolvere quest’ultimo problema si usa una tecnica detta “array circolare

    • i due indici, dopo essere giunti alla fine dell’array, possono ritornare all’inizio se si sono liberate delle posizioni
    • in questo modo l’array risulta pieno solo se la coda ha effettivamente un numero di oggetti uguale alla dimensione dell’array
    • le prestazioni temporali rimangono identiche


Coda con array circolare






  1   2   3   4   5   6   7   8


©astratto.info 2017
invia messaggio

    Pagina principale