Dans cette partie nous allons analyser une nouvelle structure de données : les piles.
Les piles sont extrèmement utiles en informatique et vous les utilisez quotidiennement, parfois même sans vous en rendre compte :
La fonction annuler Ctrl-Z de votre traitement de textes par exemple est une pile : Quand vous tapez Ctrl-Z, vous annulez la dernière opération effectuée. Quand vous faites une nouvelle opération, celle-ci est mémorisée au sommet de la pile. Vous ne pouvez pas annuler l'avant dernière opération sauf à annuler la dernière.
Le bouton retour de votre navigateur internet fonctionne également à l'aide d'une pile. Les pages web consultées lors de votre navigation sur une page sont empilées et le bouton retour permet d'accéder à la dernière page présente sur la pile.
Certaines calculatrices fonctionnent à l'aide du'une pile pour stocker les arguments des opérations : c'est le cas de beaucoup de calculatrices de la marque HP, dont la première calculatrice scientifique ayant jamais été produite : la HP 35 de 1972.
Une pile est une liste particulière ou l'on accède uniquement au dernier élément que l'on nomme le sommet de la pile.
Le dernier élément entré est le premier à sortir.
Représentation
On représente en général cette structure sous forme verticale.
On peut prendre pour exemple une pile d'assiettes : La dernière assiette rangée sera la première que l'on ressortira. On parle parfois de pile LIFO (Last In First Out : dernier entré, premier sorti).
L'interface
Les opérations permises sur les piles sont plus simples que sur les listes. Voici les quelques primitives des piles :
Les primitives
creer : créer une pile vide
empiler un nouvel élément (ajouter un élément au sommet de la pile)
dépiler le dernier élément saisi
de consulter la valeur de l'élément au sommet de la pile sans le dépiler
de tester si la pile est vide
de connaître le nombre d'éléments dans la pile.
Exercice
On contruite une pile avec les instructions suivantes :
créer une pile vide nommée p
empiler "R" dans p
empiler "U" dans p
empiler "O" dans p
empiler "J" dans p
empiler "B" dans p
empiler "R" dans p
depiler p
depiler p
empiler "N" dans p
empiler "O" dans p
empiler "O" dans p
depiler p
empiler "B" dans p
Si après ces instruction, on depile tous les éléments de la pile, quel mot apparaît
L'implémentation
Pour l'implémentation en python c'est dans le TD que ça se passe :
