Correction des TP capytale Piles/Files en Orienté Objet
Les piles
Une pile est une structure de donnée LIFO (Last In First Out) qui se comporte donc comme une pile d'assiettes : on peut empiler des éléments au dessus, et retirer seulement l'élément en haut de la pile.
En interne, on peut utiliser une liste python qui possède déjà les méthodes append pour ajouter à la fin et pop pour enlever le dernier élément, et qui peut donc se comporter comme une pile.
class Pile:
def __init__(self):
"""La pile initialisée est vide"""
self.contenu = []
def est_vide(self):
"""Renvoie un booléen qui indique si la pile est vide"""
return self.contenu == []
def empile(self, valeur):
"""Ajoute valeur en haut de la pile. Ne renvoie rien"""
self.contenu.append(valeur)
def depile(self):
"""Enlève l'élément du haut de la pile et le renvoie"""
return self.contenu.pop()
On peut ensuite créer et utiliser une pile avec ces méthodes :
p = Pile()
p.empile(12)
p.empile(20)
assert p.depile() == 20
assert not p.est_vide()
Les files
Implémentation n°1
Une file est une autre structure de donnée pour stocker des éléments, mais qui a un comportement FIFO (First In, First Out), c'est à dire comme une file d'attente : premier arrivé, premier servi.
On peut les implémenter comme les piles avec une liste python en utilisant le paramètre optionnel de la méthode pop qui permet de spécifier l'indice de l'élément à retirer. Donc pop(0) va retirer le premier élément au lieu du dernier.
class File:
def __init__(self):
"""La file initialisée est vide"""
self.contenu = []
def est_vide(self):
"""Renvoie un booléen qui indique si la file est vide"""
return self.contenu == []
def enfile(self, valeur):
"""Ajoute valeur à la fin de la file. Ne renvoie rien"""
self.contenu.append(valeur)
def defile(self):
"""Enlève le premier élément de la file et le renvoie"""
return self.contenu.pop(0)
Le problème de cette implémentation est que en python, pop(0) sur une liste va supprimer le premier élément puis décaler tous les autres : plus la liste est longue, plus cette opération prendra du temps.
La complexité de l'opération defile n'est donc plus constante (indépendante de la taille de la file) mais linéaire en cette taille.
Implémentation n°2
Pour améliorer la classe File, une astuce est d'utiliser en interne deux piles :
- Pour enfiler un élément, on l'ajoute toujours en haut de la pile n°1.
- Pour défiler un élément, on le retire toujours du haut de la pile n°2. Si celle-ci est vide, on transvase les éléments de la pile n°1 vers la pile n°2 un par un. Cette opération inverse l'ordre de tous les éléments de la file, donc on obtient en haut de la pile n°2 les prochains éléments à défiler.
Cela donne :
class File2:
def __init__(self):
"""Crée une file vide, avec deux piles vides"""
self.pile1 = Pile()
self.pile2 = Pile()
def est_vide(self):
"""La file est vide si les deux piles sont vides"""
return self.pile1.est_vide() and self.pile2.est_vide()
def enfile(self, valeur):
"""Enfilage sur la pile n°1"""
self.pile1.empile(valeur)
def defile(self):
"""Défilage depuis la pile n°2
avec transvasage avant si elle est vide"""
if self.pile2.est_vide():
while not self.pile1.est_vide():
temp = self.pile1.depile()
self.pile2.empile(temp)
return self.pile2.depile()
Complexité
La complexité de l'opération defile dépend de si on doit effectuer un transvasage. Si on n'a pas de chance, cela peut être très long, donc on n'a pas de garantie.
Ce qu'on peut dire par contre c'est que chaque élément est transvasé une seule fois de la pile n°1 vers la pile n°2. Donc le nombre d'opérations par élément ajouté dans la pile est constant.
Dans ce genre de cas en informatique, on parle de complexité amortie : peut-être qu'une opération sera longue, mais on peut garantir ce qu'il se passe en moyenne sur beaucoup d'opérations. (hors programme en NSI)
En pratique
C'est un bon exercice de le faire, mais en pratique il y a d'autres techniques un peu plus efficaces pour faire une file.
Si on a besoin d'une file en python on peut utiliser deque du module collections