Je reprend la même structure que celle adoptée dans Implémentation pile. Là encore, à la création de la pile, on spécifie une taille N qui sera la taille maximale de la pile.
Pour stocker la pile, on créera un tableau fixe de N items et une variable indiquant le nombre d'items contenus dans la pile.
Attention : contrairement à la solution vue en classe, on ne mettra pas tout dans un même tableau de taille N + 1. On adoptera la structure suivante :
>>> CREER_PILE_VIDE(5)
{"data":[None, None, None, None, None], "n":0}
P = CREER_PILE_VIDE(5) → P = {"data":[None, None, None, None, None], "n":0}EMPILER(P, 17) → P = {"data":[17, None, None, None, None], "n":1}EMPILER(P, 25) → P = {"data":[17, 25, None, None, None], "n":2}EMPILER(P, 8) → P = {"data":[17, 25, 8, None, None], "n":3}DEPILER(P) → renvoie 8 et P = {"data":[17, 25, 8, None, None], "n":2}
"""
pile_variante.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) -> {"data":[None, None, None, None, None], "n":0}
CREER_PILE_VIDE(3) -> {"data":[None, None, None], "n":0}
"""
return {"data":[None]*taille_max, "n":0}
def EST_VIDE(P):
"""
Renvoie True si la pile est vide, False sinon
"""
return P["n"] == 0
def EST_PLEINE(P):
"""
Renvoie True si la pile est pleine, False sinon
"""
return P["n"] = len(P["data"])
def EMPILER(P, e):
"""
Ajoute l'élément e sur le dessus de la pile
précondition: pile non pleine
"""
assert not EST_PLEINE(P)
n = P["n"]
P["data"][n] = e
P["n"] += 1
def DEPILER(P):
"""
Enlève l'élément sur le dessus de la pile et le renvoie
précondition: pile non vide
"""
assert not EST_VIDE(P)
P["n"] -= 1
n = P["n"]
return P["data"][n]
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
"""
n = P["n"]
data = P["data"][:n]
# conversion text
str_data = [str(item) for item in data]
# jonction
return ":".join(str_data)
# 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 !")