CKTIS / C
File FIFO avec tampon circulaire
Implémentez une file FIFO de capacité fixe dans un tableau avec deux indices et un compteur, pour réutiliser les cases libérées sans déplacer les éléments.
Version : ISO C23; implementation support may vary
Syntaxe
#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. */En FIFO, le premier élément inséré parmi ceux encore présents est retiré en premier. Un tampon circulaire respecte cet ordre dans un tableau de capacité fixe : après la dernière case, un indice revient à zéro sans déplacer les éléments. C’est une technique d’implémentation, pas un type de la bibliothèque standard du C. L’exemple n’utilise pas de nouveautés propres à C23 ; la prise en charge de C23 dépend de l’implémentation.
Dans cette convention, head indique le prochain élément à lire si la file n’est pas vide, tail la prochaine case à remplir si elle n’est pas pleine, et size le nombre d’éléments. Pour CAPACITY > 0, les indices appartiennent à [0, CAPACITY) et size à [0, CAPACITY]. Mathématiquement, tail vaut (head + size) mod CAPACITY. Les trois champs commencent à zéro. head == tail est vrai pour une file vide comme pour une file pleine ; size les distingue. Toutes les cases sont utilisables.
enqueue refuse l’écriture si size == CAPACITY, sans rien écraser. Sinon, elle écrit à l’indice tail, le fait avancer et augmente size. dequeue refuse la lecture si size == 0 ; sinon, elle copie la valeur à l’indice head dans *out, avance head et diminue size. Les deux fonctions renvoient 1 en cas de succès et 0 en cas de refus ; un refus ne change ni la file ni une éventuelle variable de sortie. Le retrait n’efface pas la case. (i + 1) % CAPACITY utilise le reste de la division entière pour ramener un indice valide de la dernière case à zéro. La capacité n’a pas besoin d’être une puissance de deux ; le diviseur doit être non nul.
Chaque opération prend un temps O(1) et le tableau occupe un espace O(CAPACITY). Passez un pointeur vers une file initialisée dont la durée de vie n’est pas terminée ; out doit désigner un objet int distinct et modifiable. L’implémentation ne synchronise pas les accès : si plusieurs threads accèdent à la file et qu’au moins un la modifie, une synchronisation externe est nécessaire.
Exemples
#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;
}
Résultat
full: rejected 99 dequeued: 10 dequeued: 20 dequeued: 30 dequeued: 40 empty: nothing to dequeue
Après l’insertion de `10`, `20` et `30`, la file refuse `99`. Retirer `10` libère la case `0` pour `40`. Malgré sa position dans le tableau, `40` sort après `20` et `30`. La dernière tentative de retrait trouve la file vide.
Leçons associées
- C · Leçon 86 · Avancé · Version : 3