GoupillWiki

Outils pour utilisateurs

Outils du site

Piste :
nsi:terminales:structures:pile_implementation

Différences

Ci-dessous, les différences entre deux révisions de la page.

Lien vers cette vue comparative

Les deux révisions précédentesRévision précédente
Prochaine révision		Révision précédente
nsi:terminales:structures:pile_implementation [2022/08/28 18:50] – supprimée - modification externe (Unknown date) 127.0.0.1nsi:terminales:structures:pile_implementation [2022/08/28 18:51] (Version actuelle) – ↷ Liens modifiés en raison d'un déplacement. goupillwiki
Ligne 1: Ligne 1:
 +====== 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 [[nsi:terminales:structures:liste_implementation|listes]].
 +
 +<WRAP box>À titre de comparaison, je vous propose deux autres implémentations. Une [[..:pile_implementation_variante|variante]] très semblables et une autre basée sur une [[pile_implementation_listechainee|liste chaînée]]</WRAP>
 +
 +==== 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 et ''P = [17, 25, 8, None, None, 2]''
 +
 +{{ .:piles-2.png?direct&600 |}}
 +
 +
 +<WRAP tip>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...</WRAP>
 +
 +===== Fichier Python =====
 +
 +<code python linenums>
 +"""
 +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 !")
 +</code>
 +
 +===== Exemples en d'autres langages =====
 +
 +Vous pouvez voir un exemple d'implémentation [[nsi:langages:go:solutions:pile|en Go]] ou -- beaucoup plus difficile -- [[nsi:langages:c:solutions:pile|en C]].