Implémentations (Bac 🎯)⚓︎
Ce cours est mis à disposition selon les termes de la Licence Creative Commons Attribution - Pas d'Utilisation Commerciale - Partage dans les Mêmes Conditions 4.0 International.
Sources et crédits pour ce cours
Pour préparer ce cours, j'ai utilisé :
- le manuel NSI chez Ellipses de Balabonski, Conchon, Filliâtre, Nguyen
- le manuel NSI chez Hachette sous la direction de Michel Beaudouin Lafon
- la ressource Eduscol sur les types de données
- le cours de mon collègue Pierre Duclosson
- le cours de Gilles Lassus
- le cours de Franck Chambon
🔖 Synthèse de ce qu'il faut retenir pour le bac
Implémentation par une liste chaînée⚓︎
Exercice 3
On peut implémenter le type abstrait File par une liste chaînée mutable en reprenant l'implémentation objet du type Pile mais au lieu d'un unique attribut contenu pointant sur la première cellule de la liste assimilée au sommet de la pile, il faut deux attributs :
- pour l'opération
defiler: un attributdebutpointant sur la première cellule de la liste - pour l'opération
enfiler: un attributfinpointant sur la dernière cellule de la liste
⏱️ Ces deux attributs vont permettre de réaliser les opérations
enfileretdefileren temps constant en \(0(1)\), par l'ajout ou la suppression de liens entre cellules, mais attention 👎
subtilité de la gestion de deux attributs
Une file est vide si et seulement si les deux attributs debut et fin ne pointent pas vers une cellule et sont positionnés à None.
Il faut donc être vigilant à bien modifier ces deux attributs lorsqu'on passe d'une file vide à une file non vide et vice versa
- si l'opération
defilerdonne une file vide, l'attributdebutva prendre la valeurNoneet il faut penser à passer aussifinàNonesinon il va pointer encore sur la cellule qui a été défilée. - si l'opération
enfilers'applique à une file vide, l'attributdebutva pointer vers une nouvelle cellule, il faut penser à faire pointerfinvers cette même cellule sinon il pointe encore versNone.
Question 1
💻 Saisir ses réponses sur Capytale
Complétez l'interface de la classe File qui implémente le type abstrait File avec une liste chaînée.
class Cellule:
def __init__(self, elt, suivant):
self.element = elt
self.suivant = suivant
class File:
def __init__(self):
self.debut = None
self.fin = None
def file_vide(self):
return (self.debut is None) and (self.fin is None)
def defiler(self):
assert not self.file_vide(), "File Vide"
elt = self.debut.element
self.debut = self.debut.suivant
if self.debut is None:
self.fin = None
return elt
def enfiler(self, elt):
if self.file_vide():
self.fin = Cellule(elt, None)
self.debut = self.fin
else:
self.fin.suivant = Cellule(elt, None)
self.fin = self.fin.suivant
# interface étendue
def queue(self):
assert not self.file_vide()
file_queue = File()
file_queue.debut = self.debut.suivant
if self.debut.suivant is not None:
file_queue.fin = self.fin
else:
file_queue.fin = file_queue.debut
return file_queue
def affichage_aux(self):
if self.file_vide():
return 'None'
return f"{str(self.debut.element)} -> {self.queue().affichage_aux()}"
def __str__(self):
return "début : " + self.affichage_aux() + " : fin"
def test_file():
f = File()
for k in range(1, 6):
f.enfiler(k)
for k in range(1, 6):
assert f.defiler() == k
assert f.file_vide()
print("Tests réussis")
Implémentation par un tableau circulaire⚓︎
Exercice 4
Si on veut limiter la taille de la file, on peut implémenter le type abstrait File par un tableau statique de taille taille_max comme pour une Pile.
Comme on a besoin de deux accès en debut (pour défiler) et fin (pour enfiler) de file, une solution est de garder en mémoire deux index debutet fin et de les incrémenter si on défile ou enfile un élément. Lorsque l'index atteint la fin du tableau on revient au début comme si le tableau était circulaire. Les décalages d'index se font donc modulo taille_max.
⏱️ Les opérations
enfileretdefilersont de simples décalages d'index avec affectation de coût constant en \(O(1)\).
Exemple 2
Dans l'exemple ci-dessous, un tableau statique de 8 cases permet de contenir une file d'au plus 8 éléments.
- Initialement
debutetfinpointaient vers la case d'indextaille_max - 1du tableau, la file était vide. - Puis on a enfilé
e1etdebutetfinont incrémenté de 1 et pointé vers la case d'index 0. - Puis on a enfilé
e2,e3,e4,e5,e6: à chaque itérationfina incrémenté de 1 maisdebutn'a pas bougé. - Il reste une place dans la file.
- Si on défile
e1, alorsdebutincrémentera de 1 etfinne bougera pas.
Par commodité pour déterminer si la file est vide, on va maintenir un attribut taille initialisé à 0 : on l'incrémentera si on enfile et on le décrémentera si on défile.
Question 1
💻 Saisir ses réponses sur Capytale
Complétez l'interface de la classe File2 qui implémente le type abstrait File avec un tableau circulaire.
class File2:
def __init__(self, taille_max):
self.taille_max = taille_max
self.tab = [None for _ in range(self.taille_max)]
self.taille = 0
self.debut = self.taille_max - 1
self.fin = self.taille_max - 1
def file_vide(self):
return self.taille == 0
def defiler(self):
assert not self.file_vide(), "File Vide"
elt = self.tab[self.debut]
self.debut = (self.debut + 1) % self.taille_max
self.taille = self.taille - 1
return elt
def enfiler(self, elt):
assert self.taille < self.taille_max, "Dépassement de capacité"
self.fin = (self.fin + 1) % self.taille_max
if self.file_vide():
self.debut = self.fin
self.taille = self.taille + 1
self.tab[self.fin] = elt
# interface étendue
def __str__(self):
sortie = "debut : "
k = self.debut
while k != self.fin:
sortie = sortie + str(self.tab[k]) + ' - '
k = (k + 1) % self.taille_max
sortie = sortie + str(self.tab[k]) + ' - : fin'
return sortie
def test_file2():
f = File2(10)
for k in range(1, 6):
f.enfiler(k)
for k in range(1, 6):
assert f.defiler() == k
assert f.file_vide()
print("Tests réussis")
Implémentation par deux piles⚓︎
Exercice 5
Une autre implémentation du type abstrait File consiste à utiliser deux piles, entree et sortie. On ajoute les éléments sur la pile entree et on les retire de la pile sortie. Si la pile sortie est vide on y transfère les éléments de la pile entree.
Entre son entrée et sa sortie, un élément subit deux opérations de dépilement, chacune inverse l'ordre et donc au final l'ordre est conservé (penser que la composée de deux fonctions décroissantes est une fonction croissante ! ).
Dans l'exemple ci-dessous :
- on enfile successivement
'Alice', 'Bob', 'Charles'qui sont empilés dans la pileentree - quand on veut défiler pour la première fois (étape 4), comme la pile
sortieest vide on transfère d'abord la pileentreesur la pilesortiepar des dépilements successifs (logique LIFO) puis on dépile (logique LIFO) le sommet desortiequi est'Alice'. C'est bien le premier élément inséré dans la structure : la composition de deux fonctions LIFO équivaut à une fonction FIFO.
Question 1
💻 Saisir ses réponses sur Capytale
Complétez l'interface de la classe File3 qui implémente le type abstrait File avec deux piles.
class Cellule2:
def __init__(self, elt, suivant):
self.element = elt
self.suivant = suivant
class Pile:
def __init__(self):
self.contenu = None
def pile_vide(self):
return self.contenu is None
def depiler(self):
assert not self.pile_vide(), "Pile Vide"
sommet = self.contenu.element
self.contenu = self.contenu.suivant
return sommet
def empiler(self, elt):
if self.pile_vide():
self.contenu = Cellule2(elt, None)
else:
self.contenu = Cellule2(elt, self.contenu)
def queue(self):
assert not self.pile_vide()
pile_queue = Pile()
pile_queue.contenu = self.contenu.suivant
return pile_queue
def __str__(self):
if self.pile_vide():
return 'None'
return f"({str(self.contenu.element)},{str(self.queue())})"
class File3:
def __init__(self):
self.entree = Pile()
self.sortie = Pile()
def file_vide(self):
return self.entree.pile_vide() and self.sortie.pile_vide()
def defiler(self):
assert not self.file_vide(), "File Vide"
if self.sortie.pile_vide():
# si sortie vide retourne la pile entree sur la pile sortie
while not self.entree.pile_vide():
self.sortie.empiler(self.entree.depiler())
return self.sortie.depiler()
def enfiler(self, elt):
self.entree.empiler(elt)
# interface étendue
def __str__(self):
sortie = "debut : "
tmp = File3()
while not self.file_vide():
elt = self.defiler()
sortie = sortie + str(elt) + ' - '
tmp.enfiler(elt)
while not tmp.file_vide():
self.enfiler(tmp.defiler())
sortie = sortie.rstrip(' - ') + ': fin'
return sortie
def test_file3():
f = File3()
for k in range(1, 6):
f.enfiler(k)
for k in range(1, 6):
assert f.defiler() == k
assert f.file_vide()
print("Tests réussis")
Implémentation avec une deque⚓︎
Exercice 6
Le module collections de la bibliothèque standard de Python propose une implémentation d'une file à deux bouts deque qui permet de retirer ou d'ajouter un élément aux deux bouts en temps constant. Une deque vide est construite à partir d'un tableau dynamique Python vide :
from collections import deque
dq = deque([]) # une deque vide
Un tableau dynamique Python permet l'ajout et le retrait en temps constant à droite (fin du tableau) mais pas à gauche (début du tableau) car il faut alors décaler tous les éléments suivants vers la gauche ou la droite selon qu'on retire ou qu'on ajoute un élément à gauche.
Dans le tableau ci-dessous on compare l'efficacité des opérations d'ajout ou de retrait à gauche ou à droite pour un tableau dynamique Python (type list) ou une deque de taille \(n\).
| Opération | Tableau dynamique Python | deque du module collections |
Opération du type File |
|---|---|---|---|
| Ajout à gauche | tab.insert(0, elt) de coût \(O(n)\) |
deq.appendleft(elt) de coût \(O(1)\) |
aucune |
| Retrait à gauche | tab.pop(0) de coût \(O(n)\) |
deq.popleft() de coût \(O(1)\) |
defiler |
| Ajout à droite | tab.append(elt) de coût \(O(1)\) |
deq.append(elt) de coût \(O(1)\) |
enfiler |
| Retrait à droite | tab.pop() de coût \(O(1)\) |
deq.pop() de coût \(O(1)\) |
aucune |
Avec une deque on peut implémenter de façon efficace les opérations enfiler et defiler du type abstrait File et le code est simplifié par rapport aux trois implémentations précédentes. L'utilisation d'un tableau dynamique Python dégraderait les performances pour l'opération defiler.
Question 1
💻 Saisir ses réponses sur Capytale
Complétez l'interface de la classe File4 qui implémente le type abstrait File avec une deque.
from collections import deque
class File4:
def __init__(self):
self.contenu = deque([])
def file_vide(self):
return len(self.contenu) == 0
def defiler(self):
assert not self.file_vide(), "File Vide"
return self.contenu.popleft()
def enfiler(self, elt):
self.contenu.append(elt)
# interface étendue
def __str__(self):
sortie = "debut : "
tmp = File4()
while not self.file_vide():
elt = self.defiler()
sortie = sortie + str(elt) + ' - '
tmp.enfiler(elt)
while not tmp.file_vide():
self.enfiler(tmp.defiler())
sortie = sortie.rstrip(' - ') + ': fin'
return sortie
def test_file4():
f = File4()
for k in range(1, 6):
f.enfiler(k)
print(f)
for k in range(1, 6):
assert f.defiler() == k
assert f.file_vide()
print("Tests réussis")