Queue Circolari in C

Le queue circolari sono una variante delle queue tradizionali, progettate per utilizzare la memoria in modo più efficiente, specialmente in situazioni in cui la dimensione della queue è limitata e predefinita. Una queue circolare è utile per implementare buffer circolari, come quelli utilizzati nella gestione delle risorse di sistema, nei driver di dispositivi e nella programmazione in tempo reale. In questa guida, esploreremo come implementare una queue circolare in C, con esempi pratici di utilizzo.

Cos’è una Queue Circolare?

Una queue circolare è una struttura dati FIFO (First In, First Out) in cui l’ultimo elemento è collegato al primo, formando un ciclo. A differenza di una queue lineare, che può lasciare spazio inutilizzato dopo alcune operazioni di dequeue, la queue circolare sfrutta tutto lo spazio disponibile, “riavvolgendo” gli indici quando raggiungono la fine della queue.

Vantaggi delle Queue Circolari

• Uso Efficiente della Memoria: Utilizzano tutto lo spazio disponibile, senza lasciare “buchi” vuoti dopo le operazioni di dequeue.
• Prestazioni Costanti: Le operazioni di enqueue e dequeue avvengono in tempo costante O(1).

Implementazione di una Queue Circolare

Definizione della Struttura di una Queue Circolare

Iniziamo definendo la struttura per la queue circolare, che include un array per memorizzare gli elementi, due indici (front e rear) e la capacità della queue.

#include <stdio.h>
#include <stdlib.h>

#define SIZE 5  // Definizione della capacità della queue

struct QueueCircolare {
    int elementi[SIZE];
    int front;
    int rear;
    int count;  // Numero di elementi attualmente nella queue
};

Inizializzazione della Queue Circolare

void init_queue(struct QueueCircolare* queue) {
    queue->front = 0;
    queue->rear = -1;
    queue->count = 0;
}

Verifica della Queue Vuota e Piena

int is_empty(struct QueueCircolare* queue) {
    return (queue->count == 0);
}

int is_full(struct QueueCircolare* queue) {
    return (queue->count == SIZE);
}

Operazione di Enqueue

L’operazione di enqueue inserisce un nuovo elemento nella queue. Se la queue è piena, l’elemento non può essere aggiunto.

void enqueue(struct QueueCircolare* queue, int valore) {
    if (is_full(queue)) {
        printf("Queue piena. Impossibile inserire %d\n", valore);
        return;
    }
    queue->rear = (queue->rear + 1) % SIZE;
    queue->elementi[queue->rear] = valore;
    queue->count++;
}

Operazione di Dequeue

L’operazione di dequeue rimuove un elemento dalla queue. Se la queue è vuota, non c’è nulla da rimuovere.

int dequeue(struct QueueCircolare* queue) {
    if (is_empty(queue)) {
        printf("Queue vuota. Impossibile rimuovere elementi.\n");
        return -1;
    }
    int valore = queue->elementi[queue->front];
    queue->front = (queue->front + 1) % SIZE;
    queue->count--;
    return valore;
}

Visualizzazione degli Elementi della Queue

Una funzione per visualizzare tutti gli elementi presenti nella queue.

void stampa_queue(struct QueueCircolare* queue) {
    if (is_empty(queue)) {
        printf("Queue vuota.\n");
        return;
    }
    printf("Elementi della queue: ");
    for (int i = 0; i < queue->count; i++) {
        int indice = (queue->front + i) % SIZE;
        printf("%d ", queue->elementi[indice]);
    }
    printf("\n");
}

Esempio Completo di Utilizzo della Queue Circolare

int main() {
    struct QueueCircolare queue;
    init_queue(&queue);

    enqueue(&queue, 10);
    enqueue(&queue, 20);
    enqueue(&queue, 30);
    enqueue(&queue, 40);
    enqueue(&queue, 50);

    stampa_queue(&queue);

    printf("Dequeue: %d\n", dequeue(&queue));
    printf("Dequeue: %d\n", dequeue(&queue));

    stampa_queue(&queue);

    enqueue(&queue, 60);
    enqueue(&queue, 70);

    stampa_queue(&queue);

    return 0;
}

Uscita:

Elementi della queue: 10 20 30 40 50
Dequeue: 10
Dequeue: 20
Elementi della queue: 30 40 50
Queue piena. Impossibile inserire 70
Elementi della queue: 30 40 50 60 70

Applicazioni Comuni delle Queue Circolari

Le queue circolari trovano applicazione in vari contesti, tra cui:

• Buffer Circolari: Utilizzati nei sistemi operativi per la gestione del buffer di input/output.
• Schedulazione dei Processi: Implementazione di algoritmi di schedulazione nei sistemi operativi.
• Gestione delle Risorse: Allocazione e gestione efficiente delle risorse in ambienti multi-thread.

Considerazioni sull’Uso delle Queue Circolari

• Prevenzione dell’Overflow: La gestione accurata degli indici front e rear è fondamentale per prevenire situazioni di overflow o underflow.
• Efficienza Spaziale: La queue circolare è ideale per ambienti a risorse limitate, dove l’efficienza dell’uso della memoria è cruciale.

Conclusioni

Le queue circolari sono una struttura dati potente e versatile, particolarmente adatta per applicazioni in cui la memoria è limitata e l’efficienza è una priorità. Implementando correttamente le operazioni di enqueue e dequeue, è possibile utilizzare l’intera capacità della queue senza sprecare spazio, rendendola una scelta eccellente per molteplici scenari pratici.