GoupillWiki

Outils pour utilisateurs

Outils du site

Piste :
nsi:terminales:structures:pile_abstraite

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_abstraite [2022/08/28 18:45] – supprimée - modification externe (Unknown date) 127.0.0.1nsi:terminales:structures:pile_abstraite [2022/09/20 11:13] (Version actuelle) – [Interface] goupillwiki
Ligne 1: Ligne 1:
 +====== Piles ======
  
 +{{ .:piles_et_files.fiche.pdf|Fiche à imprimer}}
 +
 +Une pile est une sorte de [[nsi:terminales:structures:liste_abstraite|liste]] mais pour laquelle on s'intéresse surtout à la façon de faire **entrer** et **sortir** les données.
 +
 +On pourra adopter la même notation que pour les listes. Par exemple, ''3:85:17:9'' est une pile dans laquelle on a ajouté, **dans l'ordre**, 3, 85, 17 et 9.
 +
 +===== LIFO =====
 +
 +{{ .:piles-1.png?nolink&200|}}
 +
 +Il faut penser à une pile d'assiettes.
 +
 +  * Quand on ajoute une assiette, on la met forcément sur le dessus.
 +  * Quand on retire une assiette, on retire forcément celle du dessus.
 +
 +Donc, quand on retire un élément, c'est toujours le dernier à avoir été ajouté.
 +
 +On parle de **LIFO = Last In First Out**, c'est à dire Dernier entré, premier sorti.
 +
 +> Retenez bien : Dans 3:85:17:9, 9 est le dernier inséré, c'est donc le dessus de la pile.
 +
 +===== Interface =====
 +
 +^ Méthode            ^ Description                                   ^
 +| CREER_PILE_VIDE()  | Renvoie une pile  de contenu vide             |
 +| EST_VIDE(P)        | Renvoie vrai si la pile est vide              |
 +| EMPILER(P, e)      | Ajoute l'élément e sur le dessus de la pile   |
 +| DEPILER(P)         | Enlève l'élément sur le dessus de la pile et le renvoie \\ //précondition :// pile non vide |
 +
 +=== Taille maximale ? ===
 +
 +Pour une pile c'est surtout le mode d'empilement et de dépilement qui importe. Il n'est pas indispensable que la taille de la pile puisse augmenter indéfiniment comme dans une Liste. Il est donc courant de créer une pile en prévoyant un espace mémoire maximal, si bien qu'il peut arriver que la pile soit pleine.
 +
 +Dans ce cas, on a dans l'interface :
 +
 +^ Méthode                  ^ Description                                                     ^
 +| CREER_PILE_VIDE(taille)  | Renvoie une pile  de contenu vide avec une taille max spécifiée |
 +| EST_PLEINE(P)            | Renvoie vrai si la pile est pleine                              |
 +| EMPILER(P, e)         | Ajoute l'élément e sur le dessus de la pile \\ //précondition :// pile non pleine |
 +
 +===== Exercices =====
 +
 +==== Exercice 1 ====
 +
 +Donner la pile P obtenue après exécution des lignes suivantes (dans les deux cas) :
 +
 +<WRAP group>
 +<WRAP half column>
 +<code lang-none linenums>
 +P = CREER_PILE_VIDE()
 +EMPILER(P, 'X')
 +EMPILER(P, 'B')
 +EMPILER(P, 'E')
 +DEPILER(P)
 +EMPILER(P, 'Y')
 +</code>
 +</WRAP>
 +<WRAP half column>
 +<code lang-none linenums>
 +Q = CREER_PILE_VIDE()
 +EMPILER(Q, 51)
 +EMPILER(Q, 3)
 +P = CREER_PILE_VIDE()
 +EMPILER(P, DEPILER(Q))
 +EMPILER(P, 17)
 +EMPILER(P, DEPILER(Q))
 +</code>
 +</WRAP>
 +</WRAP>
 +
 +==== Exercice 2 ====
 +
 +On veut connaître le nombre d'éléments contenu dans une pile en n'utilisant que les fonctions disponibles dans l'interface.
 +
 +L'astuce est, pour une pile P donnée, de la dépiler, constituant ainsi une nouvelle pile Q, en comptant les éléments. Il faut penser ensuite à reformer la pile P en remettant le contenu de Q dans P.
 +
 +Écrire une fonction ''%%hauteur_pile(P)%%'' qui renvoie le nombre d'éléments de ''%%P%%''.
 +
 +> Écrivez la fonction en syntaxe Python.