.. index:: pile +++++++++++++++++++ Structure : la pile +++++++++++++++++++ Nous connaissons déjà les tableaux, qui permettent de stocker un nombre fixe de valeurs de même types. Dans ce chapitre, nous présentons la structure de *pile*, qui permet de stocker un nombre *variable* de valeurs de même type et d'y accéder selon un ordre précis. Cette structure sera également l'occasion de mettre en œuvre l'approche « type abstrait » présentée dans le chapitre précédent. Principe ======== Une pile sert à stocker des valeurs de même type. Son nom vient de la manière particulière dont elle permet d'accéder aux valeurs qui y sont stockées. Prenons l'analogie avec une pile d'assiettes. On ne peut poser (ou *empiler*) une nouvelle assiette que sur le dessus (ou *sommet*) de la pile, et on ne peut retirer (ou *dépiler*) que l'assiette qui se trouve au sommet de la pile. Par ailleurs, si on suppose que chaque assiette a un motif dessiné en son centre (sa « valeur »), on ne peut voir que le motif de l'assiette du sommet. Une pile peut bien sûr être vide (ne contenir aucune valeur), ce qui doit pouvoir être vérifié, car cela n'aurait pas de sens de consulter ou dépiler la valeur au sommet d'une pile vide. De la même manière, des contraintes techniques peuvent limiter le nombre d'éléments qu'une pile peut contenir. On souhaiterait donc pouvoir tester si une pile est pleine, c'est à dire s'il est impossible d'y empiler une nouvelle valeur. Enfin, il faut disposer d'une opération permettant d'initialiser une nouvelle pile ; la nouvelle pile sera vide. .. hint:: En anglais, « pile » se traduit par *« stack »*, mais on parle également parfois de *LIFO* pour *« Last In, First Out »* (dernier entré, premier sorti). Le sommet est appelé *« top »*, et les opérations d'empilement et de dépilement sont généralement appelées *« push »* et *« pop »*, respectivement. Spécification ============= On spécifie ci-dessous une pile destinée à contenir des valeurs de type *chaîne de caractères*. Le type des valeurs n'a évidemment aucune incidence sur la spécification ou l'implémentation. Il serait tout à fait possible de définir une pile de n'importe quel autre type en remplaçant dans ce qui suit ``str`` par le nom de cet autre type. .. parsed-literal:: ######## Tpile : Spécification ######## def construit_pile(): """ :sortie p: Tpile :post-cond: p est une pile vide """ def pile_vide(p): """ :entrée p: Tpile :sortie v: bool :post-cond: v est True si et seulement si p est vide """ def pile_pleine(p) """ :entrée p: Tpile :sortie pp: bool :post-cond: pp est True si et seulement si p est pleine """ def empile(p, e) """ :entrée e: str :entrée/sortie p: Tpile :pre-cond: p n'est pas pleine :post-cond: e est ajouté au sommet de p """ def sommet(p): """ :entrée p: Tpile :sortie s: str :pre-cond: p n'est pas vide :post-cond: s est l'élément stocké au sommet de p """ def depile(p): """ :entrée/sortie p: Tpile :pre-cond: p n'est pas vide :post-cond: l'élément stocké au sommet de p est retiré """ Implémentation ============== Le seul moyen dont nous disposons pour l'instant pour stocker plusieurs valeurs du même type est d'utiliser un tableau. Nous allons donc utiliser un champs de type tableau de chaînes pour implémenter notre type abstrait. La taille de ce tableau correspondra au nombre maximum d'éléments que notre pile pourra contenir ; cette valeur sera stockée comme une constante `MAX` (pour pouvoir être changée facilement). Enfin, une pile peut contenir à un moment donné moins d'éléments que sa contenance maximale : il faut donc un champs qui mémorise le nombre d'éléments stockés dans la pile, et donc le nombre de cases effectivement utilisés dans le tableau. Reste à décider quelles cases du tableau utiliser. Supposons que la pile contienne *n* éléments : on choisit de les stocker dans les *n* premières cases du tableau, du plus ancien au plus récent. En effet, lorsqu'on ajoute un élément à la pile, il sera ajouté dans la *n*\+1ème case, et il deviendra bien le plus récent. Inversement, lorsqu'on retire l'élément le plus récent, il reste *n*\-1 éléments, et la *n*\-1ème contient bien le prochain élément à sortir de la pile. Notons enfin que le nombre d'élément du tableau est l'indice du sommet *plus un*, car le tableau est indicé à partir de zéro. .. code-block:: python ######## Tpile : Implémentation n°1 ######## from algo import * from numpy import * MAX = 100 class Tpile(Struct): tab = ndarray # tableau de MAX éléments isommet = int # indice du sommet def construit_pile(): p = Tpile(tab=empty(MAX, "