La coda può essere descritta come una struttura di dati lineare non primitiva che segue l'ordine FIFO in cui gli elementi di dati vengono inseriti da un'estremità (estremità posteriore) e cancellati dall'altra estremità (front end). Le altre varianti della coda sono la coda circolare, la coda doppiamente terminata e la coda di priorità.
Grafico comparativo
| Base per il confronto | Coda lineare | Coda circolare |
|---|---|---|
| Di base | Organizza gli elementi dei dati e le istruzioni in ordine sequenziale uno dopo l'altro. | Dispone i dati nel modello circolare in cui l'ultimo elemento è collegato al primo elemento. |
| Ordine di esecuzione dell'attività | Le attività vengono eseguite nell'ordine in cui sono state inserite prima (FIFO). | L'ordine di esecuzione di un'attività può cambiare. |
| Inserimento e cancellazione | Il nuovo elemento viene aggiunto dalla parte posteriore e rimosso dalla parte anteriore. | L'inserimento e la cancellazione possono essere eseguiti in qualsiasi posizione. |
| Prestazione | Inefficiente | Funziona meglio della coda lineare. |
Definizione di coda lineare
Una coda lineare è razionalmente una prima nella prima lista ordinata. È così chiamato lineare perché assomiglia a una linea retta in cui gli elementi sono posizionati uno dopo l'altro. Contiene una raccolta omogenea degli elementi in cui nuovi elementi vengono aggiunti a un'estremità e cancellati da un'altra estremità. Il concetto di coda può essere compreso dall'esempio di una coda del pubblico che aspetta fuori dal contatore del biglietto per ottenere il biglietto del teatro. In questa coda, la persona si unisce all'estremità posteriore della coda per prendere il ticket e il ticket viene emesso nella parte anteriore della coda.
Ci sono diverse operazioni eseguite in coda
- Innanzitutto la coda viene inizializzata a zero (cioè vuota).
- Determina se la coda è vuota o meno.
- Determina se la coda è piena o no.
- Inserimento del nuovo elemento dalla parte posteriore (Accoda).
- Cancellazione dell'elemento dalla parte anteriore (Dequeue).
La coda può essere implementata in due modi
- Staticamente (usando gli array)
- Dinamicamente (usando i puntatori)
La limitazione della coda lineare è che crea uno scenario in cui non è possibile aggiungere nuovi elementi nella coda anche se la coda contiene spazi vuoti. Questa situazione sopra è illustrata nella figura sotto riportata. Qui il retro punta verso l'ultimo indice mentre tutte le caselle sono ancora vuote, nessun nuovo elemento può essere aggiunto.
Definizione di coda circolare
Una coda circolare è una variante della coda lineare che supera efficacemente la limitazione della coda lineare. Nella coda circolare, il nuovo elemento viene aggiunto nella primissima posizione della coda se l'ultimo è occupato e lo spazio è disponibile. Quando si tratta di coda lineare, l'inserimento può essere eseguito solo dalla parte posteriore e la cancellazione dalla parte anteriore. In una coda completa dopo aver eseguito una serie di cancellazioni successive nella coda, si verifica una situazione in cui nessun nuovo elemento può essere aggiunto ulteriormente, anche se lo spazio disponibile è ancora presente perché la condizione di underflow (Rear = max - 1) esiste ancora.
La coda circolare collega le due estremità attraverso un puntatore in cui il primo elemento arriva dopo l'ultimo elemento. Inoltre tiene traccia della parte anteriore e posteriore implementando una logica aggiuntiva in modo che possa tracciare gli elementi che devono essere inseriti ed eliminati. Con questo, la coda circolare non genera la condizione di overflow finché la coda non è piena in tempo reale.
Alcune condizioni seguite dalla coda circolare:
- Anteriore deve puntare al primo elemento.
- La coda sarà vuota se Front = Rear.
- Quando viene aggiunto un nuovo elemento, la coda viene incrementata del valore uno (Posteriore = Posteriore + 1).
- Quando un elemento viene cancellato dalla coda, il fronte viene incrementato di uno (Fronte = Fronte + 1).
Differenze chiave tra coda lineare e coda circolare
- La coda lineare è una lista ordinata in cui gli elementi dei dati sono organizzati nell'ordine sequenziale. Al contrario, la coda circolare memorizza i dati in modo circolare.
- La coda lineare segue l'ordine FIFO per l'esecuzione dell'attività (l'elemento aggiunto nella prima posizione verrà eliminato nella prima posizione). Viceversa, nella coda circolare, l'ordine delle operazioni eseguite su un elemento può cambiare.
- L'inserimento e la cancellazione degli elementi è fisso in coda lineare, cioè l'aggiunta dalla parte posteriore e la cancellazione dalla parte anteriore. D'altra parte, la coda circolare è in grado di inserire ed eliminare l'elemento da qualsiasi punto fino a quando non è occupato.
- La coda lineare spreca lo spazio di memoria mentre la coda circolare fa un uso efficiente dello spazio.
Implementazione della coda lineare
L'algoritmo indicato di seguito illustra l' aggiunta di elementi in una coda:
La coda ha bisogno di tre variabili di dati tra cui un array per memorizzare la coda e l'altro per memorizzare la posizione iniziale anteriore e posteriore che è -1.
insert (item, queue, n, rear) {if (rear == n) quindi stampa "overflow della coda"; else {rear = rear + 1; coda [posteriore] = oggetto; }} L'algoritmo indicato di seguito illustra la cancellazione di elementi in una coda:
delete_circular (item, queue, rear, front) {if (rear == front) quindi stampa "underflow della coda"; else {front = front + 1; item = queue [front]; }} Implementazione della coda circolare
Un algoritmo per interpretare l' aggiunta dell'elemento nella coda circolare:
insert_circular (item, queue, rear, front) {rear = (rear + 1) mod n; se (fronte == retro) quindi stampare "la coda è piena"; else {queue [rear] = item; }} Algorithm spiega la cancellazione dell'elemento nella coda circolare:
delete_circular (item, queue, rear, front) {if (front == rear) quindi stampa ("queue is empty"); else {front = front + 1; item = queue [front]; }} Conclusione
La coda lineare è inefficiente in alcuni casi in cui gli elementi sono necessari per passare agli spazi vuoti per eseguire l'operazione di inserimento. Questo è il motivo per cui tende a sprecare lo spazio di archiviazione mentre la coda circolare fa un uso appropriato dello spazio di archiviazione man mano che gli elementi vengono aggiunti in qualsiasi posizione se esiste uno spazio vuoto.
