CodeUtility
Facilitiamo la vita agli sviluppatori!
Strutture dati in C/C++

La coda circolare (circular queue) in C e C++

In questa lezione implementerai una coda, secondo la regola primo a entrare, primo a uscire, con un array circolare in C e std::queue in C++.

Introduzione

La coda (queue) segue la regola primo a entrare, primo a uscire (FIFO). Con un array normale, ogni estrazione richiederebbe di spostare gli elementi rimasti. La coda circolare (circular buffer) risolve il problema facendo ripartire gli indici dall'inizio e riutilizzando le posizioni liberate.

Punti importanti

  • Definisci le condizioni che devono essere sempre vere (invarianti) prima di scrivere le operazioni.
  • Gestisci i casi di struttura vuota, piena e di allocazione di memoria fallita.
  • Valuta insieme la complessità e la gestione della memoria di ogni operazione.

Guarda come funziona

Fai enqueue e dequeue per vedere che gli elementi escono nello stesso ordine in cui sono arrivati.

Esempi di codice C e C++

C
Esegui →
main.c
#include <stdio.h>

typedef struct {
    int data[4];
    int head;
    int size;
} Queue;

int push(Queue *queue, int value) {
    if (queue->size == 4) return 0;
    int tail = (queue->head + queue->size) % 4;
    queue->data[tail] = value;
    ++queue->size;
    return 1;
}

int pop(Queue *queue, int *value) {
    if (queue->size == 0) return 0;
    *value = queue->data[queue->head];
    queue->head = (queue->head + 1) % 4;
    --queue->size;
    return 1;
}

int main(void) {
    Queue queue = {{0}, 0, 0};
    int value;
    push(&queue, 7);
    push(&queue, 9);
    pop(&queue, &value);
    printf("%d\n", value);
}
Risultato dell'esecuzione
7
C++
Esegui →
main.cpp
#include <iostream>
#include <queue>

int main() {
    std::queue<int> values;
    values.push(7);
    values.push(9);
    std::cout << values.front() << '\n';
    values.pop();
}
Risultato dell'esecuzione
7

Confronto tra C e C++

La coda in C conserva la posizione dell'inizio, head, e il numero di elementi, size. La posizione di un nuovo elemento si calcola con il resto della divisione (head + size) % 4, quindi, arrivato in fondo all'array, l'indice torna all'inizio. In C++, std::queue è un adattatore di contenitore (container adapter) che offre già le operazioni front, push e pop.

C

I dati (struct) e le operazioni sono separati, e la memoria viene allocata e liberata a mano.

C++

Classi e contenitori proteggono la coerenza dei dati e gestiscono da soli le proprie risorse.

Esercizi di approfondimento

Esegui entrambe le versioni e poi modifica il codice per osservare la differenza di sicurezza che offre ciascun linguaggio.

  • Aggiungi test per la struttura vuota e per quando raggiunge la capacità massima.
  • Scrivi la liberazione della memoria e controlla che non ci siano perdite.
  • Confronta la complessità con il contenitore equivalente della libreria standard.

Esercitati con una sfida

Usa ciò che questa lezione spiega per risolvere un problema reale. Ogni sfida gira nel browser, con test immediati e una revisione dell'IA.

Tutte le sfide