La gestion des files d’attentes

En informatique, une file d’attente est un ensemble d’éléments qui sont maintenus dans une séquence et peuvent être modifiées par l’ajout ou la suppression d’éléments à l’une extrémité de son conteneur (le tableau). Il existe deux familles d’algorithme selon ce que l’on souhaite faire.

Une file est une structure de données fondée sur le principe « premier arrivé, premier sorti » (FIFO). Les files sont similaires à l’idée que les gens font la queue à la caisse d’un magasin.

Une pile est une structure de données fondée sur le principe « dernier arrivé, premier sorti » (LIFO). On peut facilement se représenter l’idée en imaginant une pile d’assiettes que l’on empile les unes sur les autres.

La gestion des files d’attente sont organisées à l’aide de primitive homologue. On utilisera par contre le vocabulaire le plus approprié selon le type choisi pour éviter une ambiguïté. Par exemple, pour ajouter un élément, on dira “empiler” ou “enfiler”. Il est également intéressant de savoir si le nombre d’éléments dans la structure. En effet, cela permet de savoir si la file est vide ou pleine.

La pile

Une pile peut être est gérée d’une façon similaire à la méthode que nous avons vue pour les ensembles. Nous pouvons utiliser la variable compteur comme étant l’endroit où nous allons insérer l’élément suivant.

STRUCTURE PILE:
   VARIABLE top: ENTIER
   VARIABLE N: ENTIER
   VARIABLE conteneur: TABLEAU DE N ENTIER
FIN STRUCTURE

FONCTION PUSH(p: PILE, v: ENTIER)
    P.conteneur[ P.top ] <- v
    P.top <- P.top + 1
FIN FONCTION

FONCTION POP(p: PILE)
    VARIABLE v: ENTIER

    v <- P.conteneur[ P.top-1 ]
    P.top <- P.top - 1

    RETOURNER v
FIN FONCTION

FONCTION IS_EMPTY(p: PILE)
    RETOURNER P.top == 0
FIN FONCTION

FONCTION IS_FULL(p: PILE)
    RETOURNER P.top == P.N
FIN FONCTION

La file

Une file est un peu plus complexe que l’autre méthode. En réalité, nous aurons besoins ici de deux variables pour savoir quelle est la case du début et quelle case est la fin de la file. Cette structure peut être placée dans ce qu’on appelle un buffer circulaire. Ce dernier est en vérité un tableau sur lequel nous utilisons l’opération modulo. En effet, lorsqu’on prend la dernière case du tableau +1 % N, nous retournons en réalité au début de ce dernier… Comme s’il s’agissait d’un tableau circulaire.

FONCTION PUSH(p: FILE, v: ENTIER)
    P.conteneur[ P.head ] <- v
    P.head <- (P.head + 1) % P.max
FIN FONCTION

FONCTION POP(p: FILE)
    VARIABLE v: ENTIER

    v <- P.conteneur[ P.tail ]
    P.tail <- (P.tail + 1) % P.max

    RETOURNER v
FIN FONCTION

FONCTION IS_EMPTY(p: FILE)
    RETOURNER p.head== p.tail
FIN FONCTION

FONCTION IS_FULL(p: FILE)
    RETOURNER (p.head+1) % p.N == p.tail
FIN FONCTION