Prérequis : listes chaînées , programmation orientée objet
À l’issue de ce chapitre, vous saurez :
list de Python ;Piles et files sont des structures de données linéaires, permettant de gérer des séquences d’éléments.
Piles et files diffèrent par le jeu d’opérations disponibles et par la politique de mémorisation des éléments dans la séquence.
Les piles sont en mode LIFO (Last In First Out : dernier entré premier sorti). Leur usage caractéristique en informatique est la pile des contextes d’exécution.
Les files sont en mode FIFO (First In First Out : premier entré, premier sorti). Leur usage caractéristique concerne les files d’attente.
On définit ce type abstrait de données par ses opérations :
push ou empiler) ;pop ou depiler) ;ListeChaineeLa classe ListeChainee est tout à fait adaptée pour les piles car les opérations les
plus simples y sont l’ajout et la supression en tête de liste. Il suffit donc de poser
que le sommet de la pile est la tête de la liste chaînée.
On choisit d’implémenter la création d’une pile vide et l’accès au nombre d’éléments par
les méthodes spéciales __init__ et __len__. Pour empiler et depiler, on réutilise les
méthodes de la classe ListeChainee.
ListeChainee (suite)Remarque : on aurait pu aussi bien recopier le code des méthodes des listes chaînées pour obtenir une implémentation indépendante.
ListeChainee (suite) from listechainee import ListeChainee
class Pile:
def __init__(self):
self.pile = ListeChainee()
def __len__(self):
return len(self.pile)
def empiler(self, element):
self.pile.ajout_en_tete(element)
def depiler(self):
if len(self) == 0:
raise ValueError("depiler une pile vide")
return self.pile.supprime_en_tete()
On peut tester l’usage de la pile en empilant puis en dépilant des éléments.
ListeChainee (suite) p = Pile()
p.empiler(3)
p.empiler(5)
p.empiler(8)
print(p.depiler())
print(p.depiler())
print(p.depiler())
Activité : Redéfinir la classe Pile en utilisant seulement la classe Noeud mais sans
utiliser la classe ListeChainee.
ListeChainee (suite) class Noeud:
def __init__(self, element, suivant=None):
self.element = element
self.suivant = suivant
class Pile:
def __init__(self):
"""Crée une pile vide"""
pass
def __len__(self):
"""Donne la taille de la pile"""
pass
def empiler(self, element):
"""Ajoute un élément sur le sommet de la pile"""
pass
def depiler(self):
"""Enlève et renvoie l'élément situé sur le sommet de la pile"""
pass
list de PythonOn dispose sur les listes de la méthode append, qui ajoute à la fin, et de la méthode
pop qui enlève un élément à la fin. Ce qui est important pour les piles est d’ajouter et
de supprimer les éléments, à la même extrémité de la liste.
Remarque : On aurait aussi bien pu ajouter et supprimer au début avec les méthodes
insert(0, element) et pop(0).
list de Python (suite) class Pile:
def __init__(self):
self.pile = list()
def __len__(self):
return len(self.pile)
def empiler(self, element):
self.pile.append(element)
def depiler(self):
if len(self) == 0:
raise ValueError("depiler une pile vide")
return self.pile.pop()
On peut tester l’usage de la pile en empilant puis en dépilant des éléments.
list de Python (suite) p = Pile()
p.empiler(3)
p.empiler(5)
p.empiler(8)
print(p.depiler())
print(p.depiler())
print(p.depiler())
Pour transformer la fonction récursive suivante
def fact (n) :
return 1 if n == 0 else n * fact(n-1)
en fonction itérative, on décrémente n jusqu’à 0 en empilant ses valeurs successives,
puis on dépile les valeurs pour multiplier le résultat intermédiaire, jusqu’à ce que la
pile soit vide.
def fact (n):
contexte = Pile()
while not n == 0 :
contexte.empiler(n)
n = n - 1
r = 1
while len(contexte) > 0:
n = contexte.depiler()
r = n * r
return r
fact(10)
Les piles sont extrêmement utiles en informatique et vous les utilisez quotidiennement, parfois même sans vous en rendre compte :
depiler renvoie 3, le second renvoie 2. La pile ne contient plus que 1. La dernière valeur dépilée est 2.On définit le type abstrait de données par ses opérations :
enqueue) ;dequeue) ;ListeChaineeLa classe ListeChainee peut être adaptée pour les files car on a programmé toutes les
opérations d’ajout ou de suppression en tête ou en queue de liste chaînée.
Il faut cependant faire un choix. Si on choisit de défiler en tête (opération en temps constant) alors il faut enfiler en queue de liste chaînée (opération en temps linéaire).
ListeChainee (suite)On choisit d’implémenter la création d’une file vide et l’accès au nombre d’éléments par
les méthodes spéciales __init__ et __len__. Pour enfiler et defiler, on réutilise les
méthodes de la classe ListeChainee.
Remarque : on aurait pu aussi bien faire le choix opposé en enfilant en tête de liste (opération en temps constant) pour défiler en queue (opération en temps linéaire).
ListeChainee (suite) from listechainee import ListeChainee
class File:
def __init__(self):
self.file = ListeChainee()
def __len__(self):
return len(self.file)
def enfiler(self, element):
self.file.ajout_en_queue(element)
def defiler(self):
if len(self) == 0:
raise ValueError("defiler sur une file vide")
return self.file.supprime_en_tete()
On peut tester la file, pour observer si les éléments sont bien défilés, dans l’ordre où ils ont été enfilés.
ListeChainee (suite) f = File()
f.enfiler(3)
f.enfiler(5)
f.enfiler(8)
print(f.defiler())
print(f.defiler())
print(f.defiler())
L’implémentation des files proposée avec les listes chaînées n’est pas satisfaisante car l’ajout en queue n’est pas efficace. Ce problème peut être simplement résolu en gardant pour une file deux références, une vers le premier maillon et une vers le dernier.
ListeChainee (suite)Activité : Redéfinir la classe File, en utilisant seulement la classe Noeud, mais sans
utiliser la classe ListeChainee et en créant deux attributs pour chaque file, pour
garder la référence vers les premier et dernier maillon de la chaîne.
ListeChainee (suite) class Noeud:
def __init__(self, element, suivant=None):
self.element = element
self.suivant = suivant
class File:
def __init__(self):
"""Crée une file vide"""
self.premier = None
self.dernier = None
def __len__(self):
"""Donne la taille de la file"""
pass
def enfiler(self, element):
"""Ajoute un élément à la fin de la file"""
pass
def defiler(self):
"""Enlève et renvoie l'élément situé au début de la file"""
pass
ListeChainee (suite)Tester le bon fonctionnement de cette implémentation de la file, en vérifiant que les
deux opérations enfiler et defiler s’exécutent bien en temps constant.
f = File()
f.enfiler(3)
f.enfiler(5)
f.enfiler(8)
print(f)
print(f.defiler())
print(f.defiler())
print(f.defiler())
list de PythonOn dispose sur les listes de la méthode append, qui ajoute à la fin, et de la méthode
pop(0) qui enlève un élément au début de la liste.
Attention : En Python, l’ajout en fin de liste avec append est en temps constant, mais
le pop(0) est en temps linéaire. Pour une évaluation de la complexité des opérations
élémentaires de Python voir le site : Python.org - Time complexity
Remarque : On aurait aussi bien pu ajouter au début et supprimer à la fin, avec les
méthodes insert(0, element) et pop().
list de Python (suite) class File:
def __init__(self):
self.file = []
def __len__(self):
return len(self.file)
def enfiler(self, element):
self.file.append(element)
def defiler(self):
if len(self) == 0:
raise ValueError("defiler sur une file vide")
return self.file.pop(0)
On peut tester la file, pour observer si les éléments sont bien défilés, dans l’ordre où ils ont été enfilés.
list de Python (suite) f = File()
f.enfiler(3)
f.enfiler(5)
f.enfiler(8)
print(f.defiler())
print(f.defiler())
print(f.defiler())
Les file d’attentes simples sont utilisées en informatique, dès qu’une ressource en accès exclusif est partagée entre plusieurs utilisateurs.
Exemple : File d’attente d’impression. Chaque utilisateur soumet une tâche en l’enfilant dans la file d’impression. Le serveur d’imprimante, défile une tâche dès que l’imprimante est disponible.
Pour les piles et les files, on a vu successivement des implémentations du type abstrait, utilisant une classe de listes chainées, les listes de Python ou programmées directement sous forme de listes chaînées.
L’efficacité de ces différentes implémentations est à discuter en fonction de la complexité des opérations élémentaires utilisées.
Pour les piles, on a programmé les opérations efficacement, mais pour les files, on a dû faire un compromis entre les opérations, une seule des deux pouvant être efficace selon le choix effectué.
Pour une implémentation efficace des files, il suffit de garder les deux attributs premier
et dernier, comme proposé dans l’activité : enfiler et defiler sont alors en temps
constant. Python fournit aussi la classe deque du module collections
,
une file à deux extrémités dont les méthodes append et popleft sont en temps constant.
enfiler et defiler toutes deux en \(O(1)\), on conserve deux références (premier et dernier) ou on utilise la classe deque du module collections.