Informatica I - l'ADT coda

Funzionamento di una coda FIFO

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.

Struttura dati

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

• Enqueue corrisponde a push: enqueue inserisce un oggetto nella coda
• Dequeue corrisponde a pop: dequeue elimina dalla coda l’oggetto inserito per primo
• GetFront corrisponde a top: 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

Inserimento ed estrazione

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.

Coda ridimensionabile

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).

Problema e soluzione

Se l’array è lungo n, effettuare n operazioni enqueue e n operazioni dequeue (anche non consecutive) produce front=back=n, ovvero la coda è vuota e quindi lo spazio liberato da dequeue non viene riutilizzato.

La soluzione è utilizzare una struttura detta array circolare: i due indici, una volta giunti alla fine dell’array, possono ritornare all’inizio se si sono liberate delle posizioni. L’array circolare è pieno quando la coda contiene un numero di oggetti uguale a n–1 (e non n). Si “spreca” quindi un elemento dell'array: ciò è necessario per distinguere la condizione di coda vuota (front==back) dalla condizione di coda piena. Le prestazioni temporali rimangono identiche.

Ridimensionamento

Effettuiamo un resize come su un array ordinario, raddoppiando la capacità per mantenere le prestazioni.