Au coeur de la science !
Vous êtes libre de partager, reproduire, imprimer, distribuer et communiquer cet article, à condition de ne pas le vendre et d'en citer la source.
URL source: http://axiomcafe.fr/les-files

Les files

sam, 15/05/2010 - 16:49 par Dom [1]
Type:
  • Article spécialisé [2]
Sujet:
  • Programmation [3]
  • |
  • Informatique [4]

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

Structure FIFO pour une File en C      (cliquer pour ouvrir)

  1. typedef struct file
  2. {
  3. Element *pTabElement; // Pointeur vers le tableau des éléments
  4. int iTailleMax; // Taille maximale de la File
  5. int iTete; // Indice de la tête de file : -1 si File vide
  6. int iQueue; // Indice de la queue de file
  7. }
  8. File;

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

Implémentation en C de la primitive 'FileVide'    (cliquer pour ouvrir)

  1. int FileVide (File* f)
  2. {
  3. if (f->iTete == -1) // Si tete[F]=-1 :
  4. return 1; // c'est que la file est vide
  5. else
  6. return 0;
  7. }

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

Implémentation en C de la primitive 'NbreElement' (cliquer pour ouvrir)

  1. int NbreElement (File* f)
  2. {
  3. int taille;
  4. /* vérification séparée du cas 'FileVide' */
  5. if (f->iTete == -1) // Si la tête vaut -1
  6. return 0; // alors la liste est vide
  7. taille = f->iQueue - f->iTete; // taille = position du dernier - position du 1er
  8. return taille;
  9. }

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

Implémentation en C de la primitive 'Enfiler'    (cliquer pour ouvrir)

  1. int Enfiler (File* f, Element* pNouvElement)
  2. {
  3. if (NbreElement(f) < f->iTailleMax) // si la file n'est pas pleine...
  4. {
  5. f->pTabElement[f->iQueue] = pNouvElement; // Ajout du nouvel élément en queue
  6. if(p->iTete == -1) // Si la vide est vide:
  7. p->iTete = 0; // Déplacement de la tete
  8. f->iQueue = (f->iQueue+1)%p->iTailleMax; // Déplacement de la queue de file
  9. return 1; // SUCCES
  10. } else // Sinon
  11. return 0; // ECHEC (cause: file pleine)
  12. }

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

Implémentation en C de la primitive 'Defiler' (cliquer pour ouvrir)

  1. Element* Defiler (File* f)
  2. {
  3. Element* pTempElement;
  4.  
  5. if (FileVide[f]) // Si la file est vide:
  6. return NULL; // ECHEC (cause: file vide)
  7.  
  8. pTempElement = f->pTabElement[f->iTete]]; // Récupération de l'élément
  9. p->iTete = (p->iTete+1)%p->iTaille; // Décalage de la tête
  10. if(p->iTete == p->iQueue) // Si la file devient vide:
  11. {
  12. p->iTete = -1; // Application de la convention
  13. p->iQueue = 0; // Réinitialisation de la file
  14. }
  15. return pTempElement; // Renvoit de l'élément défilé
  16. }

Signaler un bug ou une erreur

Si vous apercevez un bug ou souhaitez voir une addition sur la page courante, n'hésitez pas à nous envoyer un message.
Si vous souhaitez une réponse, merci d'indiquer également votre adresse mail.

Envoyer [5]

Liens:
[1] http://axiomcafe.fr/dom
[2] http://axiomcafe.fr/term/article-specialise
[3] http://axiomcafe.fr/term/programmation
[4] http://axiomcafe.fr/term/informatique
[5] http://axiomcafe.fr/les-files


AxiomCafe, au coeur de la science: site de vulgarisation scientifique concis, clair et amusant !
Pour toute information, contacter : admin@axiomcafe.fr