Les files

Comme les piles, les files ont des points communs avec les listes. Différences majeures : dans une file on ajoute des éléments à une extrémité de la file et on supprime des éléments à l'autre extrémité. On prend souvent l'analogie de la file d'attente devant un magasin pour décrire une file de données.

Les files sont basées sur le principe FIFO (First In First Out : le premier qui est rentré sera le premier à sortir. Ici aussi, on retrouve souvent ce principe FIFO en informatique.

Voici les opérations que l'on peut réaliser sur une file :

  • on peut savoir si une file est vide
  • on peut ajouter un nouvel élément à la file (enfiler)
  • on peut récupérer l'élément situé en bout de file tout en le supprimant (défiler)
Exemple

Soit une file F composée des éléments suivants : 12, 14, 8, 7, 19 et 22 (le premier élément rentré dans la file est 22 ; le dernier élément rentré dans la file est 12). Pour chaque exemple ci-dessous on repart de la file d'origine :

  • si on enfile 42 la file F est maintenant composée des éléments suivants : 42, 12, 14, 8, 7, 19 et 22 (le premier élément rentré dans la file est 22 ; le dernier élément rentré dans la file est 42)
  • si on défile F, la file F est maintenant composée des éléments suivants : 12, 14, 8, 7, et 19 (le premier élément rentré dans la file est 19 ; le dernier élément rentré dans la file est 12)
  • si on défile F 6 fois de suite, la file est bien vide

Vous allez implémenter une file en utilisant un tableau, et en reprenant une structure objet du même type que pour la pile. Pour pouvoir mettre une valeur au début d'un tableau, on utilisera la méthode insert avec comme paramètre 0 (voir la documentation)

Pour aller plus loin

Il y a d'autres méthodes usuelles que l'on trouve souvent pour les files :

  • premier qui renvoie le premier élément de la file sans le défiler
  • l'attribut taille qui indique le nombre d'élément de la file.