Base di conoscenzaCentro esami
ITItaliano
Scegli la lingua13

CKTIS / C

Coda FIFO con buffer circolare

Implementa una coda FIFO a capacità fissa in un array con due indici e un contatore, così da riutilizzare le celle liberate senza spostare gli elementi.

Versione: ISO C23; implementation support may vary

Sintassi

#include <stddef.h>

enum { CAPACITY = 3 }; /* Positive, fixed capacity for this example. */
typedef struct {
    int data[CAPACITY];
    size_t head, tail, size;
} Queue;

/* Initialize with Queue q = {0}; then pass &q. */
static int enqueue(Queue *q, int value);
static int dequeue(Queue *q, int *out);
/* Both return 1 on success or 0 on full/empty, respectively. */

FIFO significa che si estrae per primo l’elemento inserito prima di tutti quelli ancora in coda. Un buffer circolare mantiene quest’ordine in un array a capacità fissa: dopo l’ultima cella l’indice torna a zero, senza spostare gli elementi. È uno schema di implementazione, non un tipo della libreria standard del C. L’esempio non usa funzionalità esclusive di C23; il supporto per C23 varia a seconda dell’implementazione.

In questa convenzione, head indica il prossimo elemento da leggere se la coda non è vuota, tail la prossima cella da scrivere se non è piena, e size conta gli elementi. Con CAPACITY > 0, entrambi gli indici sono in [0, CAPACITY) e size è in [0, CAPACITY]. Matematicamente, tail vale (head + size) mod CAPACITY. Tutti e tre i campi partono da zero. head == tail vale sia a coda vuota sia a coda piena; size distingue i due casi. Tutte le celle sono utilizzabili.

enqueue rifiuta la scrittura se size == CAPACITY, senza sovrascrivere nulla. Altrimenti scrive all’indice tail, lo fa avanzare e incrementa size. dequeue rifiuta la lettura se size == 0; altrimenti copia il valore all’indice head in *out, fa avanzare head e decrementa size. Entrambe restituiscono 1 in caso di successo e 0 in caso di rifiuto; il rifiuto lascia invariata la coda e l’eventuale variabile di uscita. L’estrazione non cancella la cella. (i + 1) % CAPACITY usa il resto della divisione intera per riportare un indice valido dall’ultima cella a zero. La capacità non deve essere necessariamente una potenza di due; il divisore non può essere zero.

Ogni operazione richiede tempo O(1) e l’array occupa spazio O(CAPACITY). Passa un puntatore a una coda inizializzata ancora in vita; out deve puntare a un oggetto int distinto e scrivibile. L’implementazione non sincronizza gli accessi: se più thread accedono alla coda e almeno uno la modifica, serve una sincronizzazione esterna.

Esempi

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

enum { CAPACITY = 3 };

typedef struct {
    int data[CAPACITY];
    size_t head, tail, size;
} Queue;

static int enqueue(Queue *q, int value)
{
    if (q->size == CAPACITY)
        return 0;
    q->data[q->tail] = value;
    q->tail = (q->tail + 1) % CAPACITY;
    ++q->size;
    return 1;
}

static int dequeue(Queue *q, int *out)
{
    if (q->size == 0)
        return 0;
    *out = q->data[q->head];
    q->head = (q->head + 1) % CAPACITY;
    --q->size;
    return 1;
}

int main(void)
{
    Queue q = {0};
    int value;

    if (!enqueue(&q, 10) || !enqueue(&q, 20) || !enqueue(&q, 30))
        return EXIT_FAILURE;
    if (enqueue(&q, 99))
        return EXIT_FAILURE;
    puts("full: rejected 99");

    if (!dequeue(&q, &value))
        return EXIT_FAILURE;
    printf("dequeued: %d\n", value);
    if (!enqueue(&q, 40))
        return EXIT_FAILURE;

    while (dequeue(&q, &value))
        printf("dequeued: %d\n", value);
    puts("empty: nothing to dequeue");
    return EXIT_SUCCESS;
}

Risultato

full: rejected 99
dequeued: 10
dequeued: 20
dequeued: 30
dequeued: 40
empty: nothing to dequeue

Dopo aver inserito `10`, `20` e `30`, la coda rifiuta `99`. Estrarre `10` libera la cella `0` per `40`. Nonostante la sua posizione nell’array, `40` esce dopo `20` e `30`. L’ultimo tentativo di estrazione trova la coda vuota.

Lezioni correlate

  • C · Lezione 86 · Avanzato · Versione: 3

Fonti