Base di conoscenzaCentro esami
ITItaliano
Scegli la lingua13

CKTIS / C

Coda FIFO in C: buffer circolare

Implementa una coda FIFO a capacità fissa e usa `head`, `tail` e `size` per riutilizzare le posizioni dell’array senza spostare gli elementi.

Versione: ISO C23; implementation support may vary

Sintassi

Queue q = {0};
bool enqueue(Queue *q, int value);
bool dequeue(Queue *q, int *out);

/* Advance a valid index; CAPACITY must be positive. */
index = (index + 1) % CAPACITY;

Una coda FIFO (first in, first out, primo a entrare, primo a uscire) estrae l’elemento più vecchio ancora presente. FIFO definisce l’ordine; un buffer circolare è un modo per implementarlo. Queue, enqueue e dequeue sono definiti nell’esempio e non fanno parte della libreria standard del C.

Queue q = {0}; inizializza una coda vuota. head è l’indice dell’elemento più vecchio quando la coda non è vuota; tail è l’indice della prossima scrittura quando non è piena. Entrambi gli indici vanno da 0 a CAPACITY - 1. size conta le posizioni occupate, da 0 a CAPACITY. Matematicamente vale tail ≡ head + size (mod CAPACITY), quindi head == tail da solo non distingue una coda vuota da una piena; a distinguerle è size.

Se c’è spazio, enqueue scrive alla posizione tail, fa avanzare tail e incrementa size. Se la coda non è vuota, dequeue copia il valore alla posizione head in *out, fa avanzare head e decrementa size. Per avanzare si usa (index + 1) % CAPACITY: % restituisce il resto della divisione, quindi dopo l’ultimo indice si torna a 0. CAPACITY deve essere positiva; un divisore nullo per % causa un comportamento indefinito.

Entrambe le funzioni restituiscono true in caso di successo e false quando l’operazione viene rifiutata perché la coda è rispettivamente piena o vuota. Il rifiuto lascia invariata la coda e, per dequeue, anche *out. q deve puntare a una coda inizializzata la cui vita non è terminata; out deve puntare a un oggetto int separato, scrivibile e ancora in vita. Ogni operazione richiede tempo O(1) e l’array occupa spazio O(CAPACITY). Questa implementazione non alloca memoria dinamicamente e non sincronizza i thread. L’esempio presuppone un ambiente hosted e non richiede funzionalità specifiche di C23; il supporto della modalità ISO C23 varia a seconda dell’implementazione.

Esempi

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

enum { CAPACITY = 3 };

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

static size_t next_index(size_t index)
{
    return (index + 1) % CAPACITY;
}

static bool enqueue(Queue *q, int value)
{
    if (q->size == CAPACITY) {
        return false;
    }
    q->data[q->tail] = value;
    q->tail = next_index(q->tail);
    ++q->size;
    return true;
}

static bool dequeue(Queue *q, int *out)
{
    if (q->size == 0) {
        return false;
    }
    *out = q->data[q->head];
    q->head = next_index(q->head);
    --q->size;
    return true;
}

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");

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

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

Risultato

full
10
20
30
40
empty

Dopo tre scritture, `tail` torna a `0`. Il tentativo di inserire `99` stampa `full` senza sovrascrivere `10`. Una volta estratto `10`, l’inserimento di `40` riutilizza la posizione `0`, ma `40` esce dopo `20` e `30`. Il tentativo fallito di estrarre dalla coda vuota termina il ciclo; il programma stampa `empty`.

Lezioni correlate

  • C · Lezione 86 · Avanzato · Versione: 3

Fonti