CodeUtility
Faciliter la vie des développeurs !
Structures de données en C/C++

La file circulaire (circular queue) en C et C++

Dans cette leçon, vous allez implémenter une file, selon la règle premier entré, premier sorti, avec un tableau circulaire en C et std::queue en C++.

Introduction

La file (queue) suit la règle premier entré, premier sorti (FIFO). Avec un tableau ordinaire, chaque retrait obligerait à décaler les éléments restants. La file circulaire (circular buffer) résout ce problème en faisant revenir les indices au début et en réutilisant les places libérées.

Points importants

  • Définissez les conditions qui doivent toujours être vraies (invariants) avant d'écrire les opérations.
  • Traitez les cas de structure vide, pleine et d'échec d'allocation mémoire.
  • Évaluez ensemble la complexité et la gestion mémoire de chaque opération.

Voir comment ça marche

Faites enqueue et dequeue pour voir que les éléments sortent dans l'ordre où ils sont arrivés.

Exemples de code C et C++

C
Exécuter →
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);
}
Résultat de l’exécution
7
C++
Exécuter →
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();
}
Résultat de l’exécution
7

Comparaison entre C et C++

La file en C garde la position de tête head et le nombre d'éléments size. La position d'un nouvel élément se calcule avec le reste de la division (head + size) % 4, l'indice revient donc automatiquement au début une fois la fin du tableau atteinte. En C++, std::queue est un adaptateur de conteneur (container adapter) qui fournit directement les opérations front, push et pop.

C

Les données (struct) et les opérations sont séparées, et la mémoire est allouée et libérée à la main.

C++

Les classes et les conteneurs protègent la cohérence des données et gèrent eux-mêmes leurs ressources.

Exercices d'approfondissement

Exécutez les deux versions, puis modifiez le code pour observer la différence de sécurité qu'apporte chaque langage.

  • Ajoutez des tests pour l'état vide et pour le moment où la capacité maximale est atteinte.
  • Écrivez la libération de la mémoire et vérifiez qu'il n'y a pas de fuite.
  • Comparez la complexité avec celle du conteneur équivalent de la bibliothèque standard.

S'entraîner avec un défi

Utilisez le contenu de cette leçon pour résoudre un vrai problème. Chaque défi s'exécute dans le navigateur, avec des tests instantanés et une revue par l'IA.

Tous les défis