====== 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]].