File - TD Cours et applications simples

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.

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

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 9 → 7 → 2 → 5 Avant / Front
• Avant / Front 5 ← 2 ← 7 ← 9 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.

1. nouvelleFile() -> File : on crée une nouvelle file vide. On pourra l'identifier à ().
   En anglais, cela pourrait donner newQueue().
2. estFileVide(f:File) -> bool : renvoie un booléen qui vaut True si la file p transmise est une file vide.
   En anglais, cela pourrait donner isEmpty().
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éalisera 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èrera 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().

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.