Thème 1

Pile & File

Les piles

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. 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).
Les opérations permises sur les piles sont plus simples que sur les listes : il est permis
  • d'empiler un nouvel élément (ajouter un élément au sommet de la pile)
  • de 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.
Il n'est pas possible d'accéder directement au n-ième élément d'une pile : Il faudrait dépiler les n-1 premiers éléments et de ce fait, détruire partiellement notre pile.
Exemples d'utilisation :
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 bopé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.
Créer une classe Pile qui contient les méthodes :
  • Un constructeur qui initialise une pile vide
  • Une méthode valeur() qui renvoie le sommet de la pile ou None si la pile est vide
  • Une méthode depile() qui dépile le dernier élément saisi renvoie la valeur dépilée ou None si la pile est vide
  • Une méthode empile(v) qui prend en paramètre une valeur v et empile cette valeur ne renvoie rien
  • Une méthode est_vide qui renvoie True si la pile est vide et False sinon
On utilisera un tableau pour représenter une pile ainsi que les méthodes append et pop