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.
Remarque

Si pour les piles utiliser une classe ou un tableau ne change pas grand chose en terme de performance, pour une file il en va autrement. En effet, le fait de faire un insert au début de la liste python va réindexer tous les éléments, ce qui est une opération couteuse Vous pouvez faire le même exercice que pour la file : créer une classe avec des cellules et mesurer les temps d'éxécution.