Algorithmique et Structures de Données

Spécification abstraite

Répertorions les fonctionnalités d’une file FIFO (First In First Out) en soulignant les verbes d'actions et les noms, à partir d’une description semi-formalisée:

• C’est un modèle pour toute structure de données où l’on accumule des informations les unes après les autres, mais où l’on choisit d’effectuer un traitement selon l’ordre d’arrivée des éléments, comme dans une file d’attente.
• Exemples :toutes les files d’attente, supermarchés, cantines , distributeurs de pièces, etc...
• Il est possible dans une telle structure d’ajouter des éléments à la fin de la file, ou de retirer des éléments uniquement au début de la file.
• L’ordre des éléments est imposé par la file. Cet ordre est construit non sur la valeur des éléments de la liste, mais sur les places (rangs)de ces éléments dans la liste. Cet ordre n’est pas accessible à l’utilisateur, c’est un élément privé.
• La file possède deux places spéciales dénommées tête et fin qui identifient l’une son premier élément, l’autre le dernier élément entré.
• Le nombre d’éléments d’une file FIFO " F " est appelé longueur de la file ; si la file est vide nous dirons que sa longueur est nulle (longueur = 0 ).
• On doit pouvoir effectuer sur une file FIFO au minimum (non exhaustif) les actions suivantes : voir si la file est vide, ajouter un élément, retirer un élément, observer le premier élément sans le prendre, etc...

Spécification opérationnelle concrète

• La file est représentée en mémoire dans un tableau.
• La tête de la file est un pointeur sur la case du tableau contenant le début de la file. Les variations de la valeur de la tête se font au gré des ajouts et des retraits.
• La fin ne bouge pas, c’est le point d’entrée de la file.
• Le tableau est plus grand que la file (il y a donc dans cette interprétation une contrainte sur la longueur ; notons max cette valeur maximale de longueur de la file).
• L’opérateur ajouter : ajoute dans le tableau dans la case pointée par fin un élément et tête augmente d’une unité.
• L’opérateur retirer : renvoie l’élément pointé par tête et diminue tête d’une unité.
• L’opérateur premier fournit une copie de l’élément pointé par tête (la file reste intacte).
• L’opérateur Est_vide teste si la file est vide (vrai si elle est vide, faux sinon).

On peut ajouter après la dernière cellule pointée par l'élément fin comme le montre la figure ci-dessous :

dans ce cas retirer un élément en tête impliquera un décalage des données vers la gauche.


On peut aussi choisir d'ajouter à partir de la première cellule comme le montre la figure ci-dessous :

dans ce cas ajouter un élément en fin impliquera un décalage des données vers la droite.