Informatica I - l'ADT coda

La struttura di una 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 ad essere estratto. L'unico oggetto che può essere ispezionato è il primo oggetto della coda.

Per realizzare una coda si usa una struttura di tipo array "riempito solo in parte". Le operazioni (metodi) che caratterizzano una coda sono:

• enqueue: inserisce un oggetto nella coda
• dequeue: elimina dalla coda l'oggetto inserito per primo
• getFront: esamina il primo oggetto, senza estrarlo

Inoltre, una coda (come ogni Container) ha i metodi:

• size: per sapere quanti oggetti ci sono nel contenitore
• isEmpty: per sapere se il contenitore è vuoto

Come si realizzano l'inserimento e l'estrazione di elementi ai due diversi.

estremi dell'array? Nella pila si inseriscono e si estraggono elementi allo stesso estremo dell'array (l'estremo "destro"), nella coda invece decidiamo di inserire a destra ed estrarre a sinistra.

Per migliorare l'efficienza servono due indici:

• front: punta al primo elemento nella coda
• back: punta al primo posto libero dopo l'ultimo elemento nella coda

Aggiornando opportunamente gli indici si realizza una coda con un "array riempito solo nella parte centrale", in cui tutte le operazioni sono O(1).

Il numero di elementi è (back - front), in particolare quando front == back l'array è vuoto.

Per rendere la coda ridimensionabile, usiamo la stessa strategia vista per la pila: sovrascriviamo il metodo enqueue.

Tutte le operazioni continuano ad avere la massima efficienza: sono O(1).

Se l'array è lungo n, effettuare n operazioni enqueue e n operazioni dequeue (anche non consecutive) PROBLEMA produce front=back=n.

ovvero la coda è vuota e quindi lo spazio liberato dadequeue non viene riutilizzato. array circolare: si usa una struttura detta " ”: I due indici, una voltaSOLUZIONEgiunti alla fine dell'array, possono ritornare all'inizio se si sono liberate delleposizioni.L'array circolare è pieno quando la coda contiene un numero di oggetti uguale an–1 (e non n).Si "spreca" quindi un elemento dell'array: ciò è necessario per distinguere lacondizione di coda vuota (front==back) dalla condizione di coda piena. Leprestazioni temporali rimangono identiche.: Effettuiamo un resize come su un array ordinario raddoppiando laRIDIMENSIONARE UN ARRAY CIRCOLAREdimensione, però affinché l'array rimanga compatto dobbiamo spostare nella seconda metà dell'array la prima partedella coda.CODA DOPPIA dequeIn una coda doppia, (double-ended queue) gli oggetti possono essere inseriti ed estratti ai

due estremi di una disposizione lineare, cioè all'inizio e alla fine. Inoltre è consentita l'ispezione dei due oggetti presenti alle due estremità.