GoupillWiki

Cette page est en lecture seule. Vous pouvez afficher le texte source, mais ne pourrez pas le modifier. Contactez votre administrateur si vous pensez qu'il s'agit d'une erreur.
====== Implémentation procédurale des piles - variante ======

===== Choix de structure =====

Je reprend la même structure que celle adoptée dans [[.structures:pile_implementation|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 :

<code python>
>>> CREER_PILE_VIDE(5)
{"data":[None, None, None, None, None], "n":0}
</code>

==== Exemple d'évolution ====

  * ''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}%%''

===== Fichier Python =====

<code python linenums>
"""
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 !")
</code>