In informatica, una coda è una struttura di dati lineare in cui i componenti vengono inseriti in un'estremità e rimossi dall'altra secondo il principio FIFO (first-in, first-out). Questa struttura dati può essere utilizzata per controllare una sequenza di azioni o memorizzare dati. C è un linguaggio informatico con funzionalità di coda incorporata sotto forma di array o elenchi concatenati.

Caratteristiche:

• Una coda è un tipo di struttura dati lineare che può essere costruita con un array o un elenco collegato.
• Gli elementi vengono spostati in fondo alla coda mentre vengono rimossi dalla parte anteriore.
• Accodare (aggiungere un elemento in secondo piano) e rimuovere dalla coda (rimuovere un elemento in primo piano) sono due operazioni di coda.
• Quando gli elementi vengono aggiunti e rimossi spesso, una coda potrebbe essere creata come una coda circolare per evitare sprechi di memoria.

Utilizzando la matrice:

Per implementare una coda in C utilizzando un array, definire prima la dimensione massima della coda e dichiarare un array di quella dimensione. Gli interi front e back sono stati rispettivamente impostati su 1. La variabile front rappresenta l'elemento front della coda e la variabile back rappresenta l'elemento back.

Prima di spingere il nuovo elemento nella posizione finale della coda, dobbiamo aumentare la variabile back di 1. La coda è ora piena e non è possibile aggiungere altri elementi aggiuntivi quando la posizione back sta raggiungendo la capacità massima della coda. Aggiungiamo un elemento all'inizio della coda e aumentiamo la variabile front di uno solo per rimuovere un elemento dalla coda. Se le posizioni anteriore e posteriore sono uguali e non è possibile eliminare più componenti, allora possiamo dire che la coda è vuota.

Di seguito è riportata un'istanza di una coda scritta in C che utilizza un array:

Linguaggio di programmazione C:

installa Maven

 #define MAX_SIZE 100 int queue[MAX_SIZE]; int front = -1; int rear = -1; void enqueue(int element) { if (rear == MAX_SIZE - 1) { printf('Queue is full'); return; } if (front == -1) { front = 0; } rear++; queue[rear] = element; } int dequeue() { if (front == -1 || front > rear) { printf('Queue is empty'); return -1; } int element = queue[front]; front++; return element; } int main() { enqueue(10); enqueue(20); enqueue(30); printf('%d ', dequeue()); printf('%d ', dequeue()); printf('%d ', dequeue()); printf('%d ', dequeue()); return 0; } 

L'output del codice sarà:

Produzione:

 10 20 30 Queue is empty-1 

Spiegazione:

1. Innanzitutto, accodiamo i tre elementi 10, 20 e 30 nella coda.
2. Quindi rimuoviamo dalla coda e stampiamo l'elemento anteriore della coda, che è 10.
3. Successivamente, rimuoviamo dalla coda e stampiamo nuovamente l'elemento anteriore della coda, che è 20.
4. Quindi, rimuoviamo dalla coda e stampiamo nuovamente l'elemento anteriore della coda, che è 30.
5. Infine, eseguiamo una rimozione dalla coda da una coda vuota che restituisce 'La coda è vuota' e restituisce -1.

Utilizzando l'elenco collegato:

Un altro approccio alternativo alla costruzione di una coda nel linguaggio di programmazione C consiste nell'utilizzare un elenco concatenato. Ciascuno dei nodi della coda viene espresso utilizzando questo metodo da un nodo che contiene il valore dell'elemento e un puntatore al nodo successivo della coda. Per tenere traccia rispettivamente del primo e dell'ultimo nodo nella coda, vengono utilizzati i puntatori anteriore e posteriore.

Stabiliamo un nuovo nodo con il valore dell'elemento e impostiamo il suo puntatore successivo su NULL per aggiungere un elemento alla coda. Al nuovo nodo impostiamo i puntatori anteriore e posteriore se la coda è vuota. In caso contrario, aggiorniamo il puntatore posteriore e impostiamo il puntatore successivo del vecchio nodo posteriore in modo che punti al nuovo nodo.

Quando si elimina un nodo da una coda, viene eliminato prima il nodo precedente, quindi il puntatore anteriore viene aggiornato al nodo successivo nella coda e infine viene rilasciata la memoria che occupava il nodo rimosso. Se il puntatore in primo piano è NULL dopo la rimozione, la coda è vuota.

Ecco un esempio di una coda implementata in C utilizzando un elenco collegato:

Linguaggio di programmazione C:

 #include #include struct Node { int data; struct Node* next; }; struct Node* front = NULL; struct Node* rear = NULL; void enqueue(int element) { struct Node* new_node = (struct Node*)malloc(sizeof(struct Node)); new_node->data = element; new_node->next = NULL; if (front == NULL && rear == NULL) { front = rear = new_node; return; } rear->next = new_node; rear = new_node; } int dequeue() { if (front == NULL) { printf('Queue is empty'); return -1; } struct Node* temp = front; int element = temp->data; if (front == rear) { front = rear = NULL; } else { front = front->next; } free(temp); return element; } int main() { enqueue(10); enqueue(20); enqueue(30); printf('%d ', dequeue()); printf('%d ', dequeue()); printf('%d ', dequeue()); printf('%d ', dequeue()); return 0; } 

L'output del codice sarà:

Produzione:

 10 20 30 Queue is empty-1 

Spiegazione:

1. Innanzitutto, accodiamo i tre elementi 10, 20 e 30 nella coda.
2. Quindi rimuoviamo dalla coda e stampiamo l'elemento anteriore della coda, che è 10.
3. Successivamente, rimuoviamo dalla coda e stampiamo nuovamente l'elemento anteriore della coda, che è 20.
4. Quindi, rimuoviamo dalla coda e stampiamo nuovamente l'elemento anteriore della coda, che è 30.
5. Infine, proviamo a rimuovere la coda dalla coda vuota, che stampa il messaggio 'La coda è vuota' e restituisce -1.

Vantaggi:

• Le code sono particolarmente utili per implementare algoritmi che richiedono che gli elementi vengano elaborati in una sequenza precisa, come la ricerca in ampiezza e la pianificazione delle attività.
• Poiché le operazioni sulle code hanno una complessità temporale O(1), possono essere eseguite velocemente anche su code enormi.
• Le code sono particolarmente flessibili poiché possono essere implementate semplicemente utilizzando un array o una lista concatenata.

Svantaggi:

• Una coda, a differenza di uno stack, non può essere costruita con un singolo puntatore, rendendo l'implementazione della coda leggermente più complessa.
• Se la coda è costruita come un array, potrebbe presto riempirsi se vengono aggiunti troppi elementi, con conseguenti problemi di prestazioni o eventualmente un arresto anomalo.
• Quando si utilizza un elenco collegato per implementare la coda, il sovraccarico di memoria di ciascun nodo può essere significativo, soprattutto per elementi piccoli.

Conclusione:

Le applicazioni che utilizzano le code, una struttura dati cruciale, includono sistemi operativi, reti e giochi, solo per citarne alcuni. Sono ideali per gli algoritmi che devono gestire gli elementi in un ordine particolare poiché sono semplici da creare utilizzando un array o un elenco collegato. Tuttavia, le code presentano degli svantaggi che devono essere considerati quando si seleziona una struttura dati per una particolare applicazione, come il consumo di memoria e la complessità dell'implementazione.