Chapitre IV - Les files d’attente

Ce chapitre présente les files d’attente, une structure de données fondamentale en informatique. Il s’inscrit dans un cours sur les structures de données et algorithmes, en détaillant la définition, la spécification, l’implémentation et un exemple d’utilisation d’une file chaînée.

Définition et principes d’une file

Une file est une structure de données qui stocke les éléments selon le principe FIFO (First In First Out), c’est-à-dire Premier Entré Premier Sorti. Cela signifie que les éléments sont récupérés dans l’ordre exact de leur insertion.

La représentation chaînée d’une file est similaire à celle d’une liste simplement chaînée. Pour faciliter l’accès à la queue de la file, on mémorise explicitement un pointeur vers la cellule en queue, plutôt que de la rechercher par parcours comme dans une liste classique.

Ainsi, une file est définie comme un enregistrement contenant deux pointeurs : l’un vers la tête de la file (premier élément) et l’autre vers la queue (dernier élément).

L’insertion se fait à la queue, tandis que la suppression se fait à la tête. Le premier élément inséré occupe la tête de la file, et le dernier élément inséré a son pointeur suivant à NULL. Une file vide est caractérisée par des pointeurs tête et queue valant NULL.

Les opérations standard sur une file sont :

• création : creer_file
• consultation : vide_file (test de file vide) et premier_file (accès au premier élément)
• modification : enfiler (ajout d’un élément) et defiler (retrait d’un élément)

Spécification d’une file chaînée

Le fichier file.h définit les types et prototypes nécessaires à la manipulation d’une file chaînée :

typedef int element;

typedef struct cellule {
  element information;
  struct cellule *suivant;
} cellule;

typedef struct file {
  cellule *tete;
  cellule *queue;
} file;

void creer_file(file*);
int vide_file(file);
element premier_file(file);
void enfiler(file*, element);
void defiler(file*);

Chaque cellule contient une information de type element (ici un entier) et un pointeur vers la cellule suivante. La file est composée de deux pointeurs vers les cellules de tête et de queue.

Implémentation d’une file chaînée

Le fichier file.c implémente les fonctions déclarées dans file.h. Voici les principales fonctions :

#include "file.h"
#include <stdlib.h>

void creer_file(file *f) {
  f->tete = NULL;
  f->queue = NULL;
}

int vide_file(file f) {
  return (f.tete == NULL) && (f.queue == NULL);
}

element premier_file(file f) {
  return f.tete->information;
}

void enfiler(file *f, element e) {
  cellule *n;
  n = (cellule*)malloc(sizeof(cellule));
  n->information = e;
  n->suivant = NULL;

  if (vide_file(*f))
    f->tete = n;
  else
    f->queue->suivant = n;

  f->queue = n;
}

void defiler(file *f) {
  cellule *p = f->tete;

  if (p->suivant == NULL) {
    f->tete = NULL;
    f->queue = NULL;
    free(p);
  } else {
    f->tete = p->suivant;
    free(p);
  }
}

La fonction creer_file initialise une file vide. vide_file teste si la file est vide en vérifiant que les pointeurs tête et queue sont NULL. premier_file retourne l’élément en tête de la file.

La fonction enfiler ajoute un nouvel élément à la queue. Elle alloue une nouvelle cellule, y stocke l’élément, et met à jour les pointeurs. Si la file est vide, la tête pointe vers la nouvelle cellule. Sinon, la cellule précédemment en queue pointe vers la nouvelle.

La fonction defiler supprime l’élément en tête de la file. Si cet élément est le seul, la file devient vide (tête et queue à NULL). Sinon, la tête est avancée à la cellule suivante, et la cellule supprimée est libérée.

Exemple d’utilisation du module file.h

Le programme principal suivant teste le module file.h en créant deux files et en y insérant des entiers :

#include <stdio.h>
#include "file.h"

void main() {
  file f1, f2;
  int i;
  creer_file(&f1);
  creer_file(&f2);

  for (i = 0; i < 10; i++) {
    if (i % 2 == 0)
      enfiler(&f1, i);
    else
      enfiler(&f2, i);
  }

  printf("f1 : ");
  while (!vide_file(f1)) {
    printf("%d\t", premier_file(f1));
    defiler(&f1);
  }

  printf("\nf2 : ");
  while (!vide_file(f2)) {
    printf("%d\t", premier_file(f2));
    defiler(&f2);
  }
}

Ce programme crée deux files, f1 et f2. Il insère dans f1 les nombres pairs de 0 à 8, et dans f2 les nombres impairs de 1 à 9. Ensuite, il affiche et vide successivement chaque file.

Le résultat de l’exécution est :

f1 : 0  2  4  6  8
f2 : 1  3  5  7  9

Points clés

• Une file est une structure FIFO : premier élément inséré est le premier retiré.
• La représentation chaînée utilise deux pointeurs : tête et queue.
• Les opérations principales sont : création, test de vide, accès au premier élément, insertion (enfiler), suppression (defiler).
• L’insertion se fait à la queue, la suppression à la tête.
• Une file vide a ses pointeurs tête et queue à NULL.
• Le module file.h et son implémentation file.c fournissent un exemple complet de manipulation de files chaînées.
• Le programme test montre comment séparer les éléments pairs et impairs dans deux files distinctes.