Structure : la file¶

Principe¶

La file est une structure permettant, comme un tableau ou une pile, des éléments ayant tous le même type. Comme dans une pile, l’ordre dans lequel les éléments d’une file sont accessibles dépend de l’ordre dans lequel ils ont été ajouté. La spécificité d’une file est que l’élément accessible est toujours le plus ancien. C’est le principe d’une file d’attente à un guichet, ou la personne servie, celle qui se trouve en tête de file, est celle qui attend depuis le plus longtemps dans la file, tandis qu’un nouvel arrivant sera placé en queue de file.

Une file peut bien sûr être vide (ne contenir aucune valeur), ce qui doit pouvoir être vérifié, car cela n’aurait pas de sens de consulter ou retirer la valeur en tête d’une file vide. De la même manière, des contraintes techniques peuvent limiter le nombre d’éléments qu’une file peut contenir. On souhaiterait donc pouvoir tester si une file est pleine, c’est à dire s’il est impossible d’y ajouter une nouvelle valeur. Enfin, il faut disposer d’une opération permettant d’initialiser une nouvelle file ; la nouvelle file sera vide.

Indice

En anglais, « file » se traduit par « queue », mais on parle également souvent de FIFO pour « First In, First Out » (premier entré, premier sorti). La tête et la queue sont respectivement appelées « head » et « tail », et les opérations d’empilement et de dépilement sont généralement appelées « enqueue » et « dequeue », respectivement.

Spécification¶

Comme dans le cas de la pile, on spécifie ci-dessous une file destinée à contenir des valeurs de type chaîne de caractères. Le type des valeurs n’a évidemment aucune incidence sur la spécification ou l’implémentation. Il serait tout à fait possible de définir une file de n’importe quel autre type en remplaçant dans ce qui suit str par le nom de cet autre type.

######## Tfile : Spécification ########

def construit_file():
    """
    :sortie f: Tfile
    :post-cond: f est vide
    """

def file_vide(f):
    """
    :entrée f: Tfile
    :sortie v: bool
    :post-cond: p est True si et seulement si f est vide
    """

def file_pleine(f):
    """
    :entrée f: Tfile
    :sortie p: bool
    :post-cond: p est True si et seulement si f est pleine
    """

def ajoute_en_queue(f, e):
    """
    :entrée e: str
    :entrée/sortie f: Tfile
    :pré-cond: f n'est pas pleine
    :post-cond: e est ajoutée en queue de f
    """

def tete(f):
    """
    :entrée f: Tfile
    :sortie t: str
    :pré-cond: f n'est pas vide
    :post-cond: e est ajoutée en queue de f
    """

def retire_tete(f):
    """
    :entrée/sortie f: Tfile
    :pré-cond: f n'est pas vide
    :post-cond: l'élément stocké en tête de f est retiré
    """

Implémentation¶

L’implémentation proposée ici utilise une liste chaînée pour stocker les valeurs de la file. Il serait possible d’utiliser un tableau, cela est laissé en exercice [1].

[1]

Ceci n’est pas totalement trivial : afin d’éviter des opération coûteuses de décalage des éléments de la file dans le tableau, on doit travailler avec deux indices indiquant respectivement la tête et la queue de la file. La difficulté provient du fait que, au cours des évolutions de la file, ces indices peuvent « faire le tour » du tableau, qui doit alors être considéré comme un anneau.

Afin que la complexité des opérations soit optimale, on souhaite pouvoir accéder en temps constant à la fois à la tête (pour les opérations tête et retire_tête) et à la queue de la file (pour l’opération ajoute_en_queue). Il faudra donc garder un pointeur vers le premier maillon de la liste, mais également vers le dernier maillon. Enfin, lorsqu’on retire l’élément de tête, il faut pouvoir accéder rapidement à l’élément suivant : la liste chaînée sera donc orientée de la tête vers la queue (cf. figure ci-dessou).

Illustration de l’implémentation de Tfile par une liste chaînée

######## Tfile : Implémentation n°1 ########

from algo import *

class Tmaillon(Struct):
    valeur = str
    suivant = SAME

class Tfile(Struct):
    mtete = Tmaillon
    mqueue = Tmaillon

def construit_file():
    f = Tfile(mtete=None, mqueue=None)
    return f

def file_vide(f):
    v = (f.mtete == NULL)
    return v

def file_pleine(f):
    # cette implémentation ne limite pas le nombre
    # d'éléments que la file peut stocker
    p = False
    return p

def ajoute_en_queue(f, e):
    m = Tmaillon(valeur=e, suivant=None)
    if f.mqueue != None:
        f.mqueue.suivant = m
    else:
        f.mtete = m
    f.mqueue = m

def tete(f):
    t = f.mtete.valeur
    return t

def retire_tete(f):
    f.mtete = f.mtete.suivant
    if f.mtete == None:
        # on vient d'enlever le dernier maillon, donc:
        f.mqueue = None

Toutes les opérations sur la file s’exécutent en temps constant : elles ne dépendent pas du nombre d’éléments stocké dans la file. Cette implémentation est donc optimale en terme de complexité algorithmique.

Application¶

Une application possible d’une file est l’inversion de l’ordre des éléments d’une pile. En effet, il suffit de dépiler tous les éléments de la pile, puis de les ré-empiler dans l’ordre ou ils sont sortis. On utilisera donc une file comme stockage intermédiaire.

def inverse_pile(p):
    """
    :entrée/sortie p: Tpile
    :post-cond: inverse l'ordre des éléments de p
    """
    f = construit_file()
    while not pile_vide(p):
        e = sommet(p)
        depile(p)
        ajoute_en_queue(f, e)
    while not file_vide(f):
        e = tete(f)
        retire_tete(f)
        empile(p, e)