Les files

Définition

File :
En informatique, une file (en anglais "queue") est une structure de données de type FIFO (anglais pour First In, First Out), c'est à dire fondée sur le principe « premier arrivé, premier sorti » . Les premiers éléments ajoutés à la file seront les premiers à être récupérés.
 
La manière la plus simple de comprendre le fonctionnement d'une file est d'imaginer une file d'attente à une caisse. Un traitement (le paiement de l'article) doit être appliqué à chacune des données (ici les clients). La structure se comporte de sorte que le premier client entré dans la file d'attente sera traité en premier lors de l'opération associée. Un client arrivant est enfilé, c'est à dire qu'il prend sa place dans la file d'attente. Il sera alors traité suivant son ordre d'arrivée. Une fois en tête de file, on dit qu'il est défilé pour être traité.
 
Schéma d'équivalence d'une structure FIFO et d'une file d'attente
 
Il peut être déduit de cet exemple qu'un caisser traitant une file de client aura besoin de quatre primitives ou fonctions de service associées à une structure de type file:
- enfiler (en anglais "enqueue"): ajouter un élément à la file
- défiler (en anglais "dequeue"): enlever un élément de la file
- la file est-elle vide?
- combien y'a-t-il d'éléments dans la file?

Structure d'une file

Une file est représentée en mémoire par une structure de donnée contenant un tableau dont les éléments sont du type souhaité. Le comportement de file FIFO est obtenu par l'ajout et le jeu sur deux indices: tete et queue, respectivement la position dans le tableau du premier élément appelé 'tête de file', et celle du dernier élément appelé 'queue de file'. A ces deux indices, est ajouté tailleMax, la taille maximale de la file.
Par convention, l'indice de la tete d'une file vide est -1.
 
Structure de File en Pseudo-Code :

  1. Structure De File:
  2. - tableau_de_Element
  3. - tailleMax
  4. - tete
  5. - queue
  6. Fin de structure

Primitives

La file est-elle vide ?

Nous avons rappelé en présentation de la structure de file que la convention voulait que la tête d'une file vide ait pour indice -1. C'est donc ce qu'il suffit de vérifier pour savoir si la file est vide.
 
Primitive 'FileVide' en Pseudo-Code :

  1. Fonction FileVide (File F):
  2. Si tete[F] = -1 alors
  3. retourner VRAI
  4. Sinon
  5. retourner FAUX
  6. FinSi
  7. FinFonction

Nombre d'éléments dans la file

Le nombre de personnes dans une file d'attente est le nombre de personne entre la première et la dernière. Dans une file, le dernier élément est repéré par queue[F] et le premier tete[F]. Le nombre de personne dans la file est alors tout simplement la soustraction des deux.
 
Primitive 'NbreElement' en Pseudo-Code :

  1. Fonction NbreElement (File F):
  2. taille = iQueue[F] - iTete[F]
  3. retourner taille
  4. FinFonction

Enfilage

Enfiler un élément dans une file revient simplement à l'ajouter à la fin de celle-ci. Une simple vérification toutefois: il faut que la file ne soit pas pleine!
 
Primitive 'Enfiler' en Pseudo-Code :

  1. Fonction Enfiler(File F, Element NouvElement):
  2. Si NbreElement[F] < tailleMax[F] alors
  3. # Ajout du nouvel élément #
  4. # en queue de la file #
  5. file[queue[F]] = nouvElement
  6. incrémente queue[F]
  7. Sinon
  8. Afficher "File pleine";
  9. FinSi
  10. FinFonction

Défilage

Le défilage consiste tout simplement à enlever le premier élément en tête de file, à condition bien-sûr que celle-ci ne soit pas vide.
 
Primitive 'Défiler' en Pseudo-Code :

  1. Fonction Defiler (File F): Element:
  2. Si (F non vide) alors
  3. Element = file[tete[F]]
  4. incrémente tete[F]
  5. Sinon
  6. Afficher "File vide"
  7. FinSi
  8. Retourner element
  9. FinFonction

Votre note : Aucun(e) Moyenne : 3.4 (36 votes)