Structure de données : les files⚓︎
Introduction⚓︎
Lorsque que vous avez une série de données, il existe plusieurs méthodes pour parcourir cette série.
Exemple
Un DRH, d'une autre entreprise, reçoit, lui aussi, au fur et à mesure des dossiers de candidature à un poste spécifique à pourvoir de façon urgente. L'ensemble des dossiers est stocké en tas sur son bureau.
Le DRH traite les dossiers de candidature dans l’ordre d’arrivée. Il prend systématiquement le dossier posé directement sur le bureau. La première personne qui a candidaté voit son dossier traité en premier. Si on imagine le tas de dossiers, les nouveaux dossiers sont posés sur le tas et le DRH récupère d’abord les dossiers sous le tas.
Les files⚓︎
Une structure de file, est une structure de données qui correspond à cette description(cas de la colonne de dossiers, où l'on commence par traiter celui qui se trouve en dessous)
Le premier élément entré, est le premier élément sorti. On parle de FIFO (First In First Out). C’est la file d’attente au péage.
Dans une file, on peut écrire(ajouter un élément) d'un côté de la file et lire(retirer un élément) de l'autre côté.
Exemples
- Un serveur d'impression, reçoit à tour de rôle des documents à imprimer. Les documents sont dans une file d'attente. Le premier document envoyé sera le premier document imprimé.
- Une file d'attente à un guichet. La première personne arrivée sera la première servie.
Primitives associées à une file:⚓︎
- création d’une file, ne renvoie rien,
- vérifier si une file est vide, renvoie True ou False
- enfiler un élément, ne renvoie rien.
- défiler un élément (supprimer et récupérer un élément de la pile), renvoie l’élément supprimé
Différentes implémentations d'une file⚓︎
Utilisation d'une liste chaînée pour représenter une file.⚓︎
Remarque préliminaire
Dans une liste chaînée, on accède facilement au premier élément. Par contre, pour accéder au dernier élément, il faut parcourir toute la liste. L'utilité d'une file est, entre autre, d'accéder au premier élément ainsi qu'au dernier de manière efficace (sans devoir parcourir l'ensemble).
Pour y remédier, on peut transformer l'implémentation d'une liste chaînée en y ajoutant un second attribut qui permet d'accéder au dernier élément.
En résumé :
Une structure de file sera composée d'élément(comme ceux d'une liste chaînée).
Une structure de file pourra avoir une structure de liste chaînée mais avec deux attributs:
self.entree
: là où on ajoutera les éléments (enfiler()
)self.sortie
: lâ où on récupérera les éléments (défiler()
)
Pour la suite vous pourrez vous inspirer du module listes chaînées disponible ici, ou de votre version.
Réflexion préliminaire à la création d'un module file_liste.py
En utilisant la structure proposée ci-dessus :
- Comment vérifier qu'une file est vide ?
- Quelles opérations faut-il faire pour enfiler un élément ?
- Quelles opérations faut-il faire pour défiler un élément ?
- Conclusion ?
- Il faut prendre une convention, par exemple : si l'attribut
sortie
vautNone
. - Il faut ajouter un élément qui pointera sur l'ancienne entrée et modifier l'entrée pour qu'elle pointe sur ce nouvel élément.
- Il faut récupérer la valeur du dernier élément. Il faut aussi modifier la sortie pour qu'elle pointe sur l'élément précédent.
- Conclusion : Dans la structure d'une liste chaînée, on a accès à l'élément suivant pas au précédent.Il faut donc modifier la classe
Element()
pour pouvoir accéder à l'élément précédent.
Utilisation d'une liste doublement chaînée pour représenter une file.⚓︎
Une liste doublement chaînée est une liste chaînée qui est composée d'éléments qui possèdent trois attributs :
- valeur : valeur de l'élément
- suivant : pointeur vers l'élément suivant
- precedent : pointeur vers l'élément précédent
Exercice
Faire des schémas sur papier des étapes suivantes. On représentera les éléments avec leur 3 attributs. Le but est de réfléchir aux changements à effectuer sur la structure à chaque étape.
- f est une file vide.
- on enfile "a"
- on enfile "b"
- on enfile "c"
- on defile
- on defile
- on defile
- f est une file vide :
- on enfile "a" :
- on enfile "b" :
- on enfile "c" :
- on defile :
- on defile :
- on defile :
Exercice
- Dans un fichier
file_liste.py
, définir une classeElement()
et son constructeur qui respecte la structure précédente. - Compléter avec les accesseurs aux attributs.
Une proposition de solution
class Element():
def __init__(self, valeur, suivant = None,precedent = None):
self.valeur = valeur
self.suivant = suivant
self.precedent = precedent
def get_valeur(self):
return self.valeur
def get_suivant(self):
return self.suivant
def get_precedent(self):
return self.precedent
def set_suivant(self, elt):
self.suivant = elt
def set_precedent(self, elt):
self.precedent = elt
Maintenant on peut s'occuper de la création d'un module file_liste.py
"
Exercice : création d'un module file_liste.py
Il s'agit de compléter le fichier précédent
Une méthode de transformation en chaîne de caractères est disponible dans l'onglet compléments
- Définir une classe
File()
avec son constructeur. Voir la structure au niveau de la remarque préliminaire - Ajouter la méthode
est_vide()
Pour la suite réfléchir aux interactions supplémentaires entre les éléments.Il sera peut-être nécessaire d'ajouter des méthodes à la classeElement()
- Ajouter la méthode
enfiler()
. - Ajouter la méthode
défiler()
Voici une proposition de transformation en chaîne de caractère (correspond à la fonction str). Cette méthode ne fonctionne qu'une fois les méthodes enfiler()
, defiler()
et est_vide()
définies.
def __str__(self):
"""renvoie un chaîne de caractères pour afficher une file. La chaîne vide pour la file vide
Returns
-------
str
Exemples:
>>> f = File()
>>> print(f)
>>> f.enfiler("a")
>>> print(f)
<- a <-
>>> f.enfiler("b")
>>> f.enfiler("c")
>>> print(f)
<- a <- b <- c <-
"""
chaine = ""
file_temp = File()
while not self.est_vide():
elt = self.defiler()
chaine = chaine + " <- " + str(elt)
file_temp.enfiler((elt))
while not file_temp.est_vide():
self.enfiler(file_temp.defiler())
if not self.est_vide():
chaine = chaine +" <-"
return chaine
Voici une proposition de solution
Utilisation de piles pour représenter une file.⚓︎
Au lieu d'utiliser une liste doublement chaînée, on peut utiliser deux piles. C'est le principe de la pioche d'un jeu de cartes et de la défausse.
- Dans la pioche, on récupère toujours la carte du dessus. (on dépile la pioche)
- Dans la défausse, on pose toujours la carte au-dessus. (on empile la défausse)
Quand la pioche est vide, on retourne la défausse (ce qui revient à dépiler toute la défausse dans la pioche)
Si on considère la pioche comme la sortie et la défausse comme l'entrée on obtient notre structure de file.
Exercice
Remarque
La méthode précédente de transformation en chaîne de caractères peut être utilisée, mais elle ne fonctionnera qu'une fois les méthodes suivantes définies.
-
Dans un fichier
file_pile.py
, définir une classeFile()
et son constructeur qui respecte la structure précédente à savoir deux attributs qui seront tous les deux des piles vides.(Il est donc nécessaire d'importer un module qui définit la classe Pile()) -
Définir les primitives de la structure de file:
- Prédicat de vacuité :
est_vide()
- Ajout d'un élément :
enfiler()
- Récupération de la valeur d'un élément en le supprimant :
defiler()
- Prédicat de vacuité :
Pas tout de suite