Gestion dynamique d'une structure FIFO

La file d'attente (queue) respecte le principe FIFO (First In, First Out). Une implémentation basée sur une liste chainée simple offre une flexibilité de taille illimitée et des opérations d'insertion et de suppression en temps constant $O(1)$, à condition de maintenir des pointeurs vers l'entrée et la sortie de la structure.

1. Définition des types

Pour une architecture robuste, il est recommandé de séparer la structure du nœud élémentaire du gestionnaire de file. Ce dernier conserve les références aux extrémités de la chaine.

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

typedef int donnee_t;

typedef struct NoeudFile {
    donnee_t valeur;
    struct NoeudFile *suivant;
} NoeudFile_t;

typedef struct GestionnaireFile {
    NoeudFile_t *tete;
    NoeudFile_t *queue;
} GestionnaireFile_t;

2. Initialisation et allocation

La création d'une file vide initialise les pointeurs à NULL. Une fonction dédiée à l'allocation des nœuds centralise la vérification de la mémoire et évite la duplication de code.

GestionnaireFile_t* creer_file(void) {
    GestionnaireFile_t *g = (GestionnaireFile_t *)malloc(sizeof(GestionnaireFile_t));
    if (!g) {
        perror("Erreur d'allocation du gestionnaire");
        exit(EXIT_FAILURE);
    }
    g->tete = NULL;
    g->queue = NULL;
    return g;
}

NoeudFile_t* creer_noeud(donnee_t val) {
    NoeudFile_t *n = (NoeudFile_t *)malloc(sizeof(NoeudFile_t));
    if (!n) return NULL;
    n->valeur = val;
    n->suivant = NULL;
    return n;
}

3. Enfilement (Insertion)

L'ajout d'un élément se fait systématiquement à la fin de la chaine. Le pointeur queue permet d'accéder directement au dernier nœud sans itération, garantissant une complexité linéaire évitée.

bool enfiler(GestionnaireFile_t *g, donnee_t val) {
    NoeudFile_t *nouveau = creer_noeud(val);
    if (!nouveau) return false;
    
    if (g->queue == NULL) {
        g->tete = g->queue = nouveau;
    } else {
        g->queue->suivant = nouveau;
        g->queue = nouveau;
    }
    return true;
}

4. Vérification de l'état

Une fonction utilitaire reoturne un booléen indiquant si la sturcture contient des données. Cette vérification préliminaire est cruciale pour prévenir les accès mémoire invalides lors des extractions.

bool est_vide(const GestionnaireFile_t *g) {
    return g->tete == NULL;
}

5. Défilement (Extraction)

La suppression retire l'élément en tête de file. Le pointeur tete est avancé, et l'ancien nœud est libéré. Si la file devient vide après l'extraction, le pointeur queue est également réinitialisé pour maintenir la cohérence des métadonnées.

bool defiler(GestionnaireFile_t *g, donnee_t *sortie) {
    if (est_vide(g)) return false;
    
    NoeudFile_t *temp = g->tete;
    *sortie = temp->valeur;
    g->tete = temp->suivant;
    
    if (g->tete == NULL) {
        g->queue = NULL;
    }
    free(temp);
    return true;
}

6. Parcours séquentiel

La lecture des éléments stockés s'effectue par itération classique depuis la tête jusqu'à la fin de la chaine. Cette opération ne modifie pas l'état interne du gestionnaire.

void afficher_file(const GestionnaireFile_t *g) {
    NoeudFile_t *courant = g->tete;
    while (courant != NULL) {
        printf("[ %d ] -> ", courant->valeur);
        courant = courant->suivant;
    }
    printf("NULL\n");
}

7. Programme de validation

L'exemple ci-dessous illustre un cycle complet d'utilisation, incluant les opérations fondamentales et la libération systématique des ressources pour respecter les contraintes de gestion mémoire du langage C.

int main(void) {
    GestionnaireFile_t *sys = creer_file();
    
    enfiler(sys, 10);
    enfiler(sys, 20);
    enfiler(sys, 30);
    
    donnee_t recu;
    defiler(sys, &recu);
    
    printf("Element extrait: %d\n", recu);
    printf("Contenu de la file: ");
    afficher_file(sys);
    
    while (!est_vide(sys)) {
        defiler(sys, &recu);
    }
    free(sys);
    
    return 0;
}