Ce TP a pour but de vous faire travailler les implémentations de file, avec une proposition d'application.

Commencez par exécuter la cellule suivante :

I. Rappels

Rappel : les piles

Pour rappel, les piles, ou Last In First Out, sont une structure de données semblable à une pile d'assiettes, avec les opérations suivantes :

• empiler (un élément sur la pile)
• dépiler (un élément de la pile)
• optionellement : regarder l'élément du haut de la pile, connaitre la taille de la pile ...

En python, cela correspond au type list, avec ses méthode L.append(x) et L.pop().

Les files

Les files, ou FIFO, First In First Out, sont une structure de données semblable à une file d'attente, avec les opérations suivantes :

• enfiler (ajouter un élément au début de la file)
• défiler (enlever l'élément de la fin de la file)
• optionellement : regarder l'élément de la fin de la file, connaitre la taille de la pile ...

On va s'intérésser à trois implémentations possibles des files.

II. Implémentation naïve

On va commencer par faire une implémentation dite naïve des files, en utilisant des listes. On va ajouter les éléments à la fin de la liste et les enlever au début.

def file_vide():
    """créé et renvoie une file vide"""
    #à compléter

def enfiler(file, x):
    """enfile l'élément 'x' à la file 'file' """
    #à compléter

def defiler(file):
    """defile et renvoie un élément de la file"""
    #à compléter

III. Application

On propose l'application suivante : on a une imprimante, et un certain nombre de terminaux (téléphones, ordinateurs) connectés à cet imprimante.

Pour simplifier, on suppose qu'une impression met une seconde. Par contre, les demandes d'impression par les terminaux peuvent arriver à n'importe quelle fréquence !

file = #à compléter
def prochain_document():
    #à compléter

def demande_impression(document):
    #à compléter

await lancer_imprimante()

IV. Implémentation efficace des files

Tant qu'on a 10 documents à imprimer, peu importe si notre file est efficace ou non. Mais maintenant, imaginons que vous gérer l'ensemble des tâches d'un ordinateur... Il y en a possiblement des milliers, à gérer chaque miliseconde ! Dans ce cas, on a besoin d'implémentations plus efficaces.

On va ici en proposer deux.

1. La double pile

def transfert(pile, resultat):
    """Transfere les élémentes de "pile" à "résultat" """
    #à compléter

On va maintenant utiliser cette propriété pour implémenter une file. L'idée est d'avoir une pile "d'entrée" et une pile de "sortie". Notre "file" sera donc constituée de deux piles !

Essayez : enfilez quelques éléments, puis défilez, et observez le transfert d'une pile à l'autre.

L'idée ici, est d'ajouter tous les éléments dans la pile d'entrée, avec un simple append. Mais lorsqu'on veut sortir un élément, on ne peux pas utiliser pop sur la même pile, sinon on sortirait les éléments à l'envers, et on aurait, justement, une pile (et pas une file !).

On va donc placer, en inversé, toute la pile d'entrée dans la pile de sortie. Les éléments de cette dernière seront alors dans le bon ordre pour être pop directement !

Attention, pour que l'ordre soit préservé, il faut respecter une règle : on ne transfère la pile d'entrée dans la pile de sortie que si la pile de sortie est vide.

On va utiliser une liste de deux listes pour implémenter notre file en python : file = [[3, 4, 5], [2, 1]].

2. La liste circulaire

L'autre manière classique d'implémenter une file, est d'utiliser une "liste circulaire".

L'idée est d'avoir deux pointeurs (des indices de listes), pour le début et la fin, qui se déplacent quand on ajoute ou retire des éléments. Nos éléments sont stockés dans une liste python de taille fixe, et quand on arrive au bout, on revient au début.

Voici une petite animation du fonctionnement :

Il est important, pour cette implémentation, que la file ne "déborde" pas : si le pointeur début rattrape le pointeur fin, on doit renvoyer une erreur. Dans le cadre de ce TP, vous pourrez supposer que ce cas n'arrive jamais.

En python, on va prendre un type de file qui est un triplet (liste de 3 éléments) [liste, debut, fin].

Dans le dessin, liste est la série de 7 carrés. Ces carrés (les éléments de la liste) peuvent être soit pleins (et contenir un nombre), soit vides (les carrés blanc, que vous pouvez remplir par exemple par None).

debut et fin sont des indices de cette liste, représentés dans le dessin par les flèches correspondantes.

Entrez le code donné en cours pour accéder à la solution :