Données File

Identification

Infoforall

16 - type abstrait File FIFO


Nous avons vu la LISTE et la PILE, nous allons voir la FILE.

Documents de cours : open document ou pdf

Résumé : Version HTML ou fond blanc ou ou PDF (couleur ou gris)

1 - La File en tant que type abstrait de données

Nous allons voir ici qu'on peut travailler sur des données organisées de façon purement théorique, répondant à des contraintes théoriques, sans se soucier de la façon dont elles vont être concrétement programmées en interne par votre programme.

File, comme file d'attente en gros : on rajoute les éléments d'un côté mais on les extrait de l'autre.

Définition du type abstrait de données FILE

Principe général d'organisation de la FILE : FIFO

Une File est un type abstrait de données ayant les propriétés suivantes :

  • il s'agit d'une séquence finie et ordonnée de données
  • on s'impose strictement de n'agir que sur les deux extrémités. On insère d'un côté et on supprime et lit de l'autre
    • insérer un élément du côté de l'entrée (l'arrière de la file) se nomme l'enfilement
    • supprimer l'élément du côté de la sortie (l'avant de la file) se nomme le défilement

Un exemple de FILE : la colonne d'un puissance 4. Lorsqu'on lâche un jeton, il va se placer le plus près possible de la sortie (en bas) sans pouvoir dépasser les jetons déjà présents. Lorsqu'on va vouloir sortir les jetons, ils vont donc sortir dans le même ordre que l'ordre d'insertion.

Une file naturelle : la colonne d'un puissance 4
FILE : on doit d'abord supprimer le jeton A avant de pouvoir accéder au jeton B. Si on rajoute un nouveau jeton, il va se placer en position E (Image dans le domaine public).

On désigne également la pile sous l'acronyme FIFO pour First In First Out (à savoir), ou en français : Premier arrivé, premier parti..

FIFO

Exemple

Trois façons de voir graphiquement une file où les éléments ont été insérés dans l'ordre chronologique suivant 5, 2, 7, 9.

    Deux versions où on pousse mentalement les éléments

  • Arrière / Back 9725 Avant / Front
  • Avant / Front 5279 Arrière / Back
  • Mais en réalité, nous allons plutôt la représenter ainsi, car c'est très proche de l'idée même d'une file-colonne dans laquelle on fait tomber un objet :

    9 Arrière / Back

    7

    2

    5 Avant / Front

Fonctions d'interface pour une FILE

Les fonction d'interface définissent l'interaction basique qu'un utilisateur doit pouvoir effectuer avec les données si elles sont du type abstrait considéré.

On les nomme également fonctions primitives ou opérations fondamentales ou même primitives tout court.

Voici la description des fonctions d'interface fondamentales que les algorithmes vont pouvoir effectuer sur le type File.

Principe de l'interface d'une file
  1. nouvelleFile() -> File : on crée une nouvelle file vide. On pourra l'identifier à (). En anglais, cela pourrait donner newQueue.
  2. estVide(f:File) -> bool : renvoie un booléen qui vaut True si la file p transmise est une file vide. En anglais, cela pourrait donner isNil ou isNull.
  3. enfiler(elt:Elt, f:File) -> File : on renvoie une file en rajoutant l'élément elt en entrée dans f. En anglais, ça se nomme enqueue. On considère qu'une bonne implémentation réalise ceci à coût constant (θ(1)).
  4. defiler(f:File) -> File  : on supprime l'élément en position de sortir et renvoie la nouvelle file f. En anglais, ça se nomme dequeue. La fonction n'est définie que si la file n'est pas vide. On considère qu'une bonne implémentation réalise ceci à coût constant (θ(1)).
  5. lireAvant(p:File) -> Elt : on renvoie l'élément en sortie(sans le supprimer ici). La fonction n'est définie que si la file n'est pas vide normalement. En anglais, ça se nomme front

01° Fournir les contenus successifs de la pile f1 après exécution de chacune des instructions de l'algorithme suivant :

    f1nouvelleFile()

    f1enfiler(5, f1)

    f1enfiler(7, f1)

    xlireAvant(f1)

    f1enfiler(x, f1)

    f1enfiler(4, f)

    f1defiler(f1)

...CORRECTION...

La forme de la représentation n'a que peu d'importance. On peut la faire en ligne ou en colonne. Cela ne change rien aux données.

S'agissant de file, je prendrai ici la représentation verticale, mais on pourrait aussi bien le faire en représentation horizontale.

    f1nouvelleFile()

    La variable f1 est une file vide.

    f1enfiler(5, f1)

    5 Avant et Arrière

    f1enfiler(7, f1)

    7 Arrière / Back

    5 Avant / Front

    xlireAvant(p1)

    7 Arrière / Back

    5 Avant / Front

    Aucun changement mais la variable x est affectée à la valeur 5.

    p1enfiler(x, p1)

    5 Arrière / Back

    7

    5 Avant / Front

    p1enfiler(4, p1)

    4

    5

    7

    5

    p1defiler(p1)

    4

    5

    7

Attention, le 5 aura totalement disparu car on ne l'a pas stocké ailleurs.

02° On veut stocker séquentiellement 1, 2, 3 dans une file. Donner l'algorithme à utiliser et fournir la représentation finale de la file. Que va renvoyer la fonction lireAvant ? La file est-elle modifiée après cette lecture ?

...CORRECTION...

    f2nouvelleFile()

    f2eniler(1, f2)

    f1enfiler(2, f2)

    f2enfiler(3, f2)

    xlireAvant(f2)

Ceci donne :

3

2

1

La variable x va alors contenir la valeur 1.

D'après la description de la fonction lireAvant, il n'y a pas modification de la file : il s'agit juste de lecture.

Type mutable

Pour les implémentations qui utilisent une structure mutable, on trouve souvent les fonctions defiler et lireAvant regroupées dans une seule et même fonction qui va modifier la file sur place et qui renvoie l'élément de sortie avant qu'on vient de supprimer.

De même, la fonction enfiler ne renvoie rien : elle modifie sur place le tableau par effet de bord.

Les prototypes de ces fonctions d'interface sont alors :

  • enfiler(x:Elt, f:File) -> None : on rajoute un élément à l'arrière de la file en modifiant la file en place. On ne renvoie donc rien.
  • defiler(f:File) -> Elt : on supprime l'avant en modifiant la file en place et on renvoie l'élément qu'on vient de sortir de la file.

03° Fournir les contenus successifs de la pile mutable f3 après exécution de chacune des instructions de l'algorithme suivant :

Attention, pensez à bien appliquer le nouveau prototype des fonctions : elles ne réagissent pas de la même façon que celles des questions 1 et 2 puisque nous travaillons avec une version mutable de pile.

    f3nouvelleFile()

    enfiler(5, f3)

    enfiler(7, f3)

    xdefiler(f3)

    enfiler(x, f3)

    enfiler(4, f3)

    defiler(f3)

...CORRECTION...

La forme de la représentation n'a que peu d'importance. On peut la faire en ligne ou en colonne. Cela ne change rien aux données.

S'agissant de pile, je prendrai ici la représentation verticale, mais on pourrait aussi bien le faire en représentation horizontale.

    f3nouvelleFile()

    La variable f3 est une file vide.

    enfiler(5, f3)

    5

    enfiler(7, f3)

    7

    5

    xdefiler(f3)

    7

    Cette fois, la fonction supprime l'avant et le renvoie, ce qui permet de le stocker dans la variable x qui est affectée à la valeur 5.

    enfiler(x, f3)

    5

    7

    enfiler(4, f3)

    4

    5

    7

    defiler(f3)

    4

    5

Attention, ici on dépile mais on ne stocke pas le 7 : il a donc juste disparu à jamais.

Fonctions d'interface optionnelles

Les fonctions précédentes permettent de créer celles qui sont présentées ici. Selon les applications, nous en auront besoin ou pas, contrairement aux premières qui sont nécessaires pour manipuler les files.

  • taille(f:File) -> int : on renvoie le nombre d'éléments dans la File. Cela peut être pratique pour éviter de dépasser la taile limite queue overflow en anglais).
  • vider(f:File) -> File : on vide la file. Pour une file non-mutable, on renvoie donc une file vide. Cela peut être utile pour signaler qu'on se sépare d'éléments pourtant non traités (et qui ne le seront jamais). En anglais, ça se nomme clear.

Nous allons devoir utiliser certaines de ces fonctions pour résoudre l'exercice suivant.

04° Imaginer un algorithme permettant de gérer trois guichets f1, f2 et f3 d'un péage routier. Les clients font la queue physiquement et à partir d'un endroit un afficheur doit leur dire de se diriger vers un guichet particulier 1, 2 ou 3 en fonction de la file d'attente aux trois guichets. On prendre une file d'attente maximum de 4 clients.

File de voitures et 3 files d'attente
Point important mais plein de subtilité

Comme pour la PILE, si vous avez à lire, modifier ou insérer régulièrement des éléments ailleurs qu'aux endroits prévus dans le cadre d'une FILE, c'est que vous utilisez le mauvais type abstrait.

S'il s'agit d'un détournement très occasionnel de la FILE, cela ne pose pas problème. Si c'est régulier, passez à la LISTE.

2 - Choix d'utilisation d'une file

05° Nous présentons ici plusieurs problèmes. Pour chacun des problèmes, dire si l'utilisation d'une file est adaptée, ou pas. Si la file n'est pas adaptée, expliquer le problème qu'on va rencontrer en résolvant le problème avec ce type de gestion.

A - Annulation des actions dans un logiciel.

On stocke les actions avec un enfilement. On utilise un défilement pour savoir ce qu'on doit annuler.

B - Réception et gestion des requêtes HTTP sur un serveur

La réception sera gérer par un enfilement. La gestion se fait progressivement avec un défilement.

C - Réception et gestion des demandes d'impression sur une imprimante partagée

La réception sera gérée par un enfilement. La gestion se fait progressivement avec un défilement.

D - Inversion des éléments d'un tableau

On stocke les éléments avec un enfilement en commençant par l'index 0. Une fois tout le tableau lu, on défile pour créer le nouveau tableau en commençant par l'index 0.

E - Classement des produits les plus vendus

On désire obtenir tous les mois une mise à jour des produits les plus vendus dans un magasin.

F - Gestion des clients arrivant dans un magasin

On place un client dans la file lorsqu'il rentre dans la boutique. On défile pour savoir qui servir.

G - Stockage des fonctions lors des appels

On stocke en mémoire les fonctions avec un enfilement lorsque le programme en a besoin. On défile lorsqu'elles répondent.

H - Questions et réponses d'un prof lors d'un cours

Les questions sont stockées avec un enfilement. La réponse à la question se fait progressivement avec un défilement.

I - Gestion des stocks

On enfile un produit lorsqu'il rentre en magasin. On doit le supprimer lorsqu'il sort.

3 - Types et structures linéaires

Choix de votre structure linéaire

Nous avons donc vu trois types abstraits linéaires :

  1. La LISTE qui permet de lire, d'insérer et supprimer n'importe quel élément à l'intérieur de la liste.
    • Si on ne doit gérer que l'ajout et la suppression de tête, on peut partir sur une implémentation tuple (tete, queue) mais les coûts sont linéaires dès qu'on veut intervenir ailleurs qu'en tête
    • Si on veut souvent lire ou modifier une valeur à l'intérieur de la liste, on partira sur un type abstrait TABLEAU et une implémentation capable d'avoir un comportement similaire à cette structure. On a alors un coût constant en lecture et modification d'un élément.
    • Si on veut souvent insérer ou supprimer des éléments, on partira sur un type abstrait LISTE CHAINEE et une implémentation capable d'avoir un comportement similaire à cette structure. On peut alors avoir dans certains cas particuliers un coût constant en insertion et en suppression d'un élément. Par contre, on gagne clairement sur le tableau si on doit régulièrement insérer de très grands ensembles de données d'un seul coup.
  2. Si on part sur une logique LIFO, on choisira une PILE.
  3. Si on part sur une logique FIFO, on choisira une FILE.

4 - FAQ

Pas de question pour le moment

Activité publiée le 04 10 2020
Dernière modification : 25 10 2020
Auteur : ows. h.