Ceci est une ancienne révision du document !
Warning: Undefined array key 1 in /home/goupillf/wiki.goupill.fr/lib/plugins/codeprettify/syntax/code.php on line 172
Warning: Undefined array key 1 in /home/goupillf/wiki.goupill.fr/lib/plugins/codeprettify/syntax/code.php on line 149
Warning: Trying to access array offset on value of type null in /home/goupillf/wiki.goupill.fr/lib/plugins/codeprettify/syntax/code.php on line 149
Warning: Undefined array key 2 in /home/goupillf/wiki.goupill.fr/lib/plugins/codeprettify/syntax/code.php on line 214
Warning: Undefined array key 2 in /home/goupillf/wiki.goupill.fr/lib/plugins/codeprettify/syntax/code.php on line 214
Table des matières
Implémentation procédurale des piles
Choix de structure
Je propose d'opter pour une pile de taille maximale fixée d'avance, ce qui se pratique beaucoup. On peut donc utiliser un tableau – type list de Python – ce qui sera plus simple que pour les listes.
À titre de comparaison, je vous propose deux autres implémentations. Une variante très semblables et une autre basée sur une liste chaînée
Utilisation d'un tableau
On se fixera une taille maximale N, ce qui signifie que la pile P a toujours à sa disposition N cases mémoires. Pourtant, la pile n'utilise pas toujours ces N cases. À un moment donné, la pile ne contient que n éléments.
Il faut écrire quelque part le nombre de cases en cours d'utilisation, c'est à dire le nombre d'éléments de la pile.
Pour cela on décide de créer un tableau de N + 1 cases,
- N cases disponibles pour les items de la pile – pas forcément toutes utilisées,
- la N + 1 ème case –
P[N]– pour contenir le nombre de cases en cours d'utilisation
Exemple d'évolution
P = CREER_PILE_VIDE(5)→P = [None, None, None, None, None, 0]EMPILER(P, 17)→P = [17, None, None, None, None, 1]EMPILER(P, 25)→P = [17, 25, None, None, None, 2]EMPILER(P, 8)→P = [17, 25, 8, None, None, 3]DEPILER(P)→ renvoie 8 etP = [17, 25, 8, None, None, 2]
Dans le cas du dépilement, il n'est pas nécessaire d'effacer la valeur dépilée. En effet, puisque l'on a modifié P[5] de 3 à 2, maintenant les seuls éléments considérés comme appartenant à la pile sont les 2 premiers, 17 et 25. Bien que 8 soit toujours écrit en 3e position, il est ignoré.
Si l'idée vous crée trop de difficultés, vous pouvez effacer le 8 et le remplacer par None lors du dépilement…
Fichier Python
"""
piles.py
Module définissant l'interface des piles
"""
def CREER_PILE_VIDE(taille_max:int):
"""
taille_max: taille maximale de la pile
Renvoie une pile vide
exemples :
CREER_PILE_VIDE(5) -> [None, None, None, None, None, 0]
CREER_PILE_VIDE(3) -> [None, None, None, 0]
"""
def EST_VIDE(P):
"""
Renvoie True si la pile est vide, False sinon
"""
def EST_PLEINE(P):
"""
Renvoie True si la pile est pleine, False sinon
"""
def EMPILER(P, e):
"""
Ajoute l'élément e sur le dessus de la pile
précondition: pile non pleine
"""
def DEPILER(P):
"""
Enlève l'élément sur le dessus de la pile et le renvoie
précondition: pile non vide
"""
def TEXTE(P):
"""
Renvoie une représentation texte du contenu de la pile
On utilise la notation, par ex, 4:9:17:12, 12 étant ici le sommet de la pile
"""
# zone de test
if __name__ == '__main__':
# création de P = 4:9:17:12
P = CREER_PILE_VIDE(100)
EMPILER(P,4)
EMPILER(P,9)
EMPILER(P,17)
EMPILER(P,12)
# tests
assert EST_VIDE(P) == False
assert EST_PLEINE(P) == False
assert TEXTE(P) == "4:9:17:12"
assert DEPILER(P) == 12
assert TEXTE(P) == "4:9:17"
assert DEPILER(P) == 17
assert TEXTE(P) == "4:9"
DEPILER(P)
DEPILER(P)
assert EST_VIDE(P) == True
# si on arrive là, c'est que tous les test ont été passés avec succès
print("Succès !")