Coda circolare in C: come implementare?

I dati sono disposti in una coda circolare secondo uno schema circolare in cui l'ultimo elemento è collegato al primo elemento. A differenza della coda lineare in cui le attività vengono eseguite su FIFO (First In First Out), l'ordine della coda circolare di esecuzione delle attività può cambiare. Le operazioni di inserimento ed eliminazione possono essere eseguite in qualsiasi posizione.

La coda circolare è più efficiente della coda lineare. Nella rappresentazione grafica di una coda circolare, si può osservare che le posizioni anteriore e posteriore sono collegate, creando un cerchio in cui le operazioni vengono eseguite sempre su base FIFO. Ogni nuovo elemento viene aggiunto nella parte posteriore e cancellato dalla parte anteriore. Una coda circolare ha un utilizzo migliore e ha una complessità temporale di O(1).

Fonte

Applicazioni di una coda circolare

• Programmazione CPU: le code circolari utilizzano gli spazi di memoria vuoti che si trovano nelle code lineari.
• Sistema del traffico: Nel sistema del traffico, con l'ausilio delle code circolari, i semafori vengono azionati all'intervallo di tempo impostato.
• Gestione della memoria: i sistemi operativi spesso mantengono una linea di processi pronti per l'esecuzione o in attesa che si verifichi un evento specifico.

Impara: Programma C per l'ordinamento delle bolle: Ordinamento delle bolle in C

Esempio di codice con spiegazione

Riga 1: // (1) Preprocessori

Riga 2: // Imposta il limite della coda su 5 elementi

Riga 3: #include<stdio.h>

Riga 4: #define LIM 5

Riga 5: // (2) Dichiarazioni del tipo di dati della coda

Riga 6: // i dati contengono i dati; delPos, posizione da cui eliminare; lunghezza, n. di

Riga 7: // elementi attualmente presenti in coda

Riga 8: code struct typedef {

Riga 9: int data[LIM], delPos, lunghezza;

Riga 10: } D;

Riga 11: // (3) Dichiarazioni globali

Riga 12: // Funzioni e variabile globale q del tipo di coda struct

Riga 13: Qq;

Riga 14: void ui_Q_Ops(), insertQel(), deleteQel(), displayQels(), initQ();

Riga 15: // (4) Richiama la funzione dell'interfaccia utente dopo l'inizializzazione

Riga 16: int main()

Riga 17: {

Riga 18: initQ();

Riga 19: ui_Q_Ops();

Riga 20: ritorno 0;

Riga 21: }

Riga 22: // (5) Inizializza la coda

Riga 23: void initQ()

Riga 24: {

Riga 25: q.lunghezza = 0;

Riga 26: q.delPos = 0;

Riga 27: }

Riga 28: // (6) Menu Driven Loop richiama le funzioni corrette

Riga 29: void ui_Q_Ops()

Riga 30: {

Riga 31: int scelta=0;

Riga 32: char input[16];

Riga 33: mentre(scelta!=4){

Riga 34: printf(” \n ———————-\n “);

Riga 35: printf(” 1. Inserisci in coda \n “);

Riga 36: printf(” 2. Elimina dalla coda \n “);

Riga 37: printf(” 3. Visualizza elementi in coda \n “);

Riga 38: printf(” 4. Esci dal programma \n “);

Riga 39: printf(" Inserisci scelta: ");

Riga 40: if (fgets(input, 15, stdin) != NULL){

Riga 41: if (sscanf(input, “%d”, &choice) == 1){

Riga 42: interruttore(scelta){

Riga 43: caso 1: insertQel();

Riga 44: pausa;

Riga 45: caso 2: deleteQel();

Riga 46: pausa;

Riga 47: caso 3: displayQels();

Riga 48: pausa;

Riga 49: caso 4: ritorno;

Riga 50: default: printf(“Scelta non valida\n “);

Linea 51: proseguire;

Riga 52: }

Riga 53: } altro

Riga 54: printf(”Scelta non valida \n “);

Riga 55: }

Riga 56: }

Riga 57: }

Riga 58: // (7) Inserisci nella coda

Riga 59: // Se la lunghezza è uguale a MAX Limit, la coda è piena, altrimenti inserisci

Riga 60: // raggiunto circolarmente con la lunghezza della somma e il modulo delPos da MAX Limit

Riga 61: // e incrementa la lunghezza

Riga 62: void insertQel()

Riga 63: {

Riga 64: int el, inspos;

Riga 65: input di caratteri[16];

Riga 66: if (q.length == LIM){

Riga 67: printf(" La coda è piena \n ");

Linea 68: ritorno;

Riga 69: }

Riga 70: inspos = (q.delPos + q.length) % LIM;

Riga 71: printf(” Inserisci l'elemento da inserire: “);

Riga 72: if (fgets(input, 15, stdin) != NULL){

Riga 73: if (sscanf(input, “%d”, &el)){

Riga 74: q.data[inpos] = el;

Riga 75: q.lunghezza++;

Riga 76: } altro

Riga 77: printf(” Input non valido \n “);

Riga 78: }

Riga 79: }

Riga 80: // (8) Elimina dalla coda

Riga 81: // Se Lunghezza è 0, la coda è vuota, altrimenti elimina in delPos

Riga 82: // e decrementa la lunghezza

Riga 83: void deleteQel()

Riga 84: {

Riga 85: if (q.length == 0){

Riga 86: printf(" La coda è vuota \n ");

Riga 87: } altro {

Riga 88: printf(”Elemento eliminato %d \n “, q.data[q.delPos]);

Riga 89: q.delPos = (q.delPos + 1) % LIM;

Riga 90: q.lunghezza–;

Riga 91: }

Riga 92: }

Riga 93: // (9) Visualizza elementi della coda

Riga 94: // Visualizza in modo circolare eseguendo un ciclo a partire da delPos

Riga 95: // e aggiunta di iteratore e modulo di Max Limit

Riga 96: void displayQels()

Riga 97: {

Riga 98: int i;

Riga 99: if (q.length == 0){

Riga 100: printf(" La coda è vuota \n ");

Riga 101: } altro {

Riga 102: printf(” Gli elementi della coda sono: “);

Riga 103: for(i = 0; i < q.lunghezza; i++){

Riga 104: printf(“%d “, q.data[(q.delPos+i)%LIM]);

Riga 105: }

Riga 106: printf(” \n “);

Riga 107: }

Riga 108: }

Riga 109:

Uscite:

Operazioni su una coda circolare

1. insertQel() – Inserimento di un elemento nella coda circolare

In una coda circolare, la funzione enQueue() viene utilizzata per inserire un elemento nella coda circolare. In una coda circolare, la nuova funzionalità è sempre inserita in posizione arretrata. La funzione enQueue() prende un valore intero come parametro e lo inserisce nella coda circolare. Per inserire un elemento nella coda circolare vengono implementati i seguenti passaggi:

Passaggio 1: verificare se la lunghezza è la stessa del limite MAX. Se vero, significa che la coda è PIENA. Se è PIENO, visualizzare "La coda è piena" e terminare la funzione.

Passaggio 2: se NON è COMPLETO, inserisci il valore ottenuto in modo circolare con la lunghezza della somma e il modulo delPos di MAX Limit e incrementa la lunghezza

2. deleteQel() – Eliminazione di un elemento dalla coda circolare

In una coda circolare, deQueue() è una funzione utilizzata per eliminare un elemento dalla coda circolare. In una coda circolare, l'elemento viene sempre eliminato dalla prima posizione. La funzione deQueue() non accetta alcun valore come parametro. Vengono implementati i seguenti passaggi per eliminare un elemento dalla coda circolare...

Passaggio 1: verificare se la coda è VUOTA. (anteriore == -1 && posteriore == -1)

Passaggio 2: se è VUOTO, visualizzare "La coda è vuota" e terminare la funzione.

Passaggio 3: se NON è VUOTO, visualizza gli elementi eliminati in base alle posizioni. Dopo aver aggiunto ogni elemento, passa al limite di coda mod della posizione successiva.

3. displayQels() – Visualizza gli elementi della coda presenti nella coda circolare. I seguenti passaggi sono implementati per visualizzare gli elementi di una coda circolare:

Passaggio 1: verificare se la coda è VUOTA.

Passaggio 2: se la lunghezza è 0, è VUOTA, quindi visualizzare "La coda è vuota" e terminare la funzione.

Passaggio 3: se NON è VUOTO, definire una variabile intera 'i.'

Passaggio 4: imposta i su 0.

Passaggio 5 – Ancora una volta, visualizza gli elementi in base alla posizione e incrementa il valore di uno (i++). Ripetere lo stesso finché 'i <q.length' diventa FALSE.

La coda circolare può essere implementata anche utilizzando l'elenco collegato. Questi sono gli algoritmi:

• Algoritmo per Accodamento:

if (FRONT == NULL) // Inserimento in una coda vuota

FRONT = REAR = nuovo nodo

finisci se

altro

REAR -> next = newNode // Inserimento dopo l'ultimo elemento

REAR = nuovo nodo

finire altro

POSTERIORE -> successivo = ANTERIORE

Fine coda

• Algoritmo per disaccodare:

if(FRONT == NULL) // Condizione per underflow

Stampa "Coda insufficiente"

fine coda

finisci se

else if(FRONT == REAR) // La coda contiene un solo nodo

temp = FRONTE -> dati

libero (temporaneo)

FRONTE = FRONTE -> successivo

POSTERIORE -> successivo = ANTERIORE

finisci se

else if (FRONT == N – 1) // Se FRONT è l'ultimo nodo

front = 0 // Imposta FRONT come primo nodo

finisci se

fine coda

Leggi anche: Python Vs C: confronto affiancato completo

Conclusione

Le strutture dati e gli algoritmi sono di grande importanza e non solo nella programmazione C ma anche in altri linguaggi. Il suo valore non ha precedenti e, per argomenti di tale importanza, è meglio investire in corsi progettati e seguiti da esperti, che forniranno un eccellente valore aggiunto al tuo portafoglio. upGrad offre una vasta gamma di corsi ricchi di energia che non solo migliorano le tue abilità, ma costruiscono solidi pilastri di base.

È progettato dal rinomato IIIT-B, dove non solo forniscono contenuti di qualità premium, ma ti rendono anche parte di una solida rete in cui ti connetterai con persone che si stanno evolvendo nello stesso percorso di carriera e con gli esperti del settore che risolvere i tuoi dubbi e supportarti ogni volta.

Conoscere la loro mentalità e il processo di pensiero ti aiuterebbe. E una delle cose uniche che ottieni su upGrad è che puoi optare per le opzioni EMI e andare piano con le tue tasche.

Ci auguriamo che avrai un'eccellente opportunità di apprendimento nell'esecuzione di questi progetti C. Se sei interessato a saperne di più e hai bisogno del tutoraggio di esperti del settore, dai un'occhiata al diploma PG di upGrad & IIIT Banglore in sviluppo software full-stack .