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 un tableau dynamique Python⚓︎
Exercice 3
Si on représente une pile par un tableau dynamique de Python (type list), en considérant le dernier élément du tableau comme le sommet de la pile,
certaines méthodes du type list implémentent les opérations empiler et depiler du type abstrait Pile :
| Méthode de tableau dynamique | Opération du type abstrait Pile |
|---|---|
| append | empiler |
| pop | depiler |
Une implémentation fonctionnelle du type abstrait Pile avec un tableau dynamique Python est donc immédiate. Il s'agit d'une pile mutable.
Question 1
💻 Saisir ses réponses sur Capytale
Complétez le code de la fonction longueur qui étend l'interface de base du type Pile, en utilisant uniquement les fonctions de l'interface : creer_pile, pile_vide, depiler, empiler.
# Interface du type abstrait Pile
def creer_pile():
return []
def pile_vide(pile):
return pile == []
def depiler(pile):
sommet = pile.pop()
return sommet
def empiler(pile, elt):
pile.append(elt)
# interface étendue
def longueur(pile):
autre = creer_pile()
k = 0
while not pile_vide(pile):
empiler(autre, depiler(pile))
k = k + 1
while not pile_vide(autre):
empiler(pile, depiler(autre))
return k
def valeur_sommet(pile):
sommet = depiler(pile)
empiler(pile, sommet)
return sommet
def str_pile(pile):
tmp = creer_pile()
while not pile_vide(pile):
empiler(tmp, depiler(pile))
sortie = 'None'
while not pile_vide(tmp):
sommet = depiler(tmp)
sortie = f'({sommet},{sortie})'
empiler(pile, sommet)
return sortie
def test_pile():
pile = creer_pile()
for k in [8, 4, 3]:
empiler(pile, k)
assert str_pile(pile) == '(3,(4,(8,None)))'
for k in [3, 4, 8]:
sommet = depiler(pile)
assert sommet == k
assert pile_vide(pile) == True
print("tests réussis")
Implémentation par un tableau de taille fixée⚓︎
Exercice 4
On peut implémenter le type abstrait Pile en utilisant un tableau statique de taille fixée taille_max pour stocker les éléments. On maintient à jour un attribut taille pour repérer l'index de la case contenant l'élément au sommet de la pile. Les cases suivantes sont initialisées avec une valeur particulière comme None pour indiquer qu'elles sont vides. L'implémentation est similaire à celle du type Liste vue en TP.
Il s'agit d'une pile mutable.
Question 1
💻 Saisir ses réponses sur Capytale
Complétez l'interface de la classe Pile qui implémente le type abstrait Pile avec un tableau statique dont la taille est fixée lors de la construction de l'objet.
class Pile:
def __init__(self, taille_max):
self.taille_max = taille_max
self.taille = 0
self.tab = [None for _ in range(self.taille_max)]
def pile_vide(self):
return self.taille == 0
def depiler(self):
assert not self.pile_vide(), "Pile Vide"
sommet = self.tab[self.taille - 1]
self.taille = self.taille - 1
return sommet
def empiler(self, elt):
assert self.taille < self.taille_max, "Dépassement de capacité"
self.taille = self.taille + 1
self.tab[self.taille - 1] = elt
def __str__(self):
tmp = Pile(self.taille_max)
while not self.pile_vide():
tmp.empiler(self.depiler())
sortie = 'None'
while not tmp.pile_vide():
sommet = tmp.depiler()
sortie = f'({sommet},{sortie})'
self.empiler(sommet)
return sortie
def test_pile():
stack = Pile(5)
for k in [8, 4, 3]:
stack.empiler(k)
assert str(stack) == '(3,(4,(8,None)))'
for k in [3, 4, 8]:
sommet = stack.depiler()
assert sommet == k
assert stack.pile_vide() == True
print("tests réussis")
Implémentation par une liste chaînée⚓︎
Exercice 5
On peut remarquer que si on implémente le type abstrait Pile par une liste chaînée dont la tête correspondrait au sommet de la pile alors l'interface du type Pile est incluse dans celle du type Liste (seule l'opération queue ne figure pas dans l'interface d'une Pile) :
| Opération du type abstrait Liste | Opération du type abstrait Pile |
|---|---|
| creer_liste | creer_pile |
| liste_vide | pile_vide |
| inserer | empiler |
| tete | depiler |
💡 Il y a une petite différence entre
tetequi renvoie l'élément en tête de liste etempilerqui retire l'élément au sommet de la pile en plus de le renvoyer.💡 On peut choisir une implémentation de pile immuable avec l'implémentation d'une liste chaînée par des tuples ou de pile mutable avec l'implémentation par une classe que nous présentons ici.
Il est donc naturel d'implémenter le type abstrait Pile par une liste chaînée. Avec le paradigme objet (POO), on écrit une classe Pile avec un seul attribut contenu qui contient un lien vers la première cellule de la liste chaînée contenant les éléments.
Question 1
💻 Saisir ses réponses sur Capytale
Complétez l'interface de la classe Pile_chaine qui implémente le type abstrait Pile avec une liste chaînée.
class Cellule:
def __init__(self, elt, suivant=None):
self.element = elt
self.suivant = suivant
class Pile_chaine:
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 = Cellule(elt, None)
else:
self.contenu = Cellule(elt, self.contenu)
# on peut juste écrire
#self.contenu = Cellule(elt, self.contenu)
def queue(self):
assert not self.pile_vide()
pile_queue = Pile_chaine()
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())})"
def test_pile3():
stack = Pile_chaine()
for k in [8, 4, 3]:
stack.empiler(k)
assert str(stack) == '(3,(4,(8,None)))'
for k in [3, 4, 8]:
sommet = stack.depiler()
assert sommet == k
assert stack.pile_vide() == True
print("tests réussis")