Base de connaissancesCentre d’examen
FRFrançais
Choisir la langue13

CKTIS / C

File FIFO en C : tampon circulaire

Implémentez une file FIFO de capacité fixe et utilisez `head`, `tail` et `size` pour réutiliser les cases du tableau sans déplacer les éléments.

Version : ISO C23; implementation support may vary

Syntaxe

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;

Une file FIFO (first in, first out, premier entré, premier sorti) retire l’élément le plus ancien encore présent. FIFO définit l’ordre ; un tampon circulaire est une façon de le mettre en œuvre. Queue, enqueue et dequeue sont définis dans l’exemple et ne font pas partie de la bibliothèque standard du C.

Queue q = {0}; initialise une file vide. head est l’indice de l’élément le plus ancien si la file n’est pas vide ; tail est l’indice de la prochaine écriture si elle n’est pas pleine. Les deux indices vont de 0 à CAPACITY - 1. size compte les cases occupées, de 0 à CAPACITY. Mathématiquement, tail ≡ head + size (mod CAPACITY) : head == tail ne suffit donc pas à distinguer une file vide d’une file pleine ; c’est size qui les distingue.

S’il reste de la place, enqueue écrit à l’indice tail, avance tail et incrémente size. Si la file n’est pas vide, dequeue copie dans *out la valeur à l’indice head, avance head et décrémente size. Pour avancer, (index + 1) % CAPACITY utilise %, qui donne le reste de la division : après le dernier indice, on revient à 0. CAPACITY doit être strictement positive ; un diviseur nul avec % entraîne un comportement indéfini.

Les deux fonctions renvoient true en cas de succès et false si l’opération est refusée parce que la file est respectivement pleine ou vide. En cas de refus, la file reste inchangée, tout comme *out pour dequeue. q doit pointer vers une file initialisée encore en vie ; out doit pointer vers un objet int distinct, encore en vie et accessible en écriture. Chaque opération prend un temps O(1) et le tableau occupe un espace O(CAPACITY). Cette implémentation n’alloue pas de mémoire dynamiquement et ne synchronise pas les threads. L’exemple suppose un environnement hébergé et ne requiert aucune fonctionnalité propre à C23 ; la prise en charge du mode ISO C23 dépend de l’implémentation.

Exemples

#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;
}

Résultat

full
10
20
30
40
empty

Après trois écritures, `tail` revient à `0`. La tentative d’ajout de `99` affiche `full` sans écraser `10`. Après le retrait de `10`, l’ajout de `40` réutilise la case `0`, mais `40` sort après `20` et `30`. L’échec du retrait sur la file vide met fin à la boucle ; le programme affiche `empty`.

Leçons associées

  • C · Leçon 86 · Avancé · Version : 3

Sources