TP : Pile

La pile est une structure de données qui permet de stocker des éléments de même nature (on dit encore que la pile est un conteneur).

On ne peut pas manipuler les élément d'un pile comme on veut : on ne peut enlever un élément que si celui-ci est au sommet de la pile (i.e. est le dernier à avoir été posé). On dit que la politique de stockage de la pile est de type LIFO (Last In First Out ou encore Dernier Entré Premier Sorti)

Description fonctionnelle

Pour information, je redonne la description fonctionnelle (spécification) du TAD de la pile :

TAD
PILE[G]
Types
  PILE[G] (G prédéfini)
Fonctions
  créer : PILE[G]
est_vide : PILE[G] -> booléen
ajouter : PILE[G] x G -> PILE[G]
enlever : PILE[G] -> PILE[G]
consulter : PILE[G] -> G
Axiomes
  A1 : consulter(ajouter(s,x))=x
A2 : enlever(ajouter(s,x))=s
A3 : est_vide(creer) = VRAI
A4 : est_vide(ajouter(s,x)) = FAUX
pour tout s, x
Préconditions
  enlever requiert est_vide=FAUX
consulter requiert est_vide= FAUX

Vous pouvez remarquer que cette spécification est indépendante de tout langage de programmation.

Description logique

Il existe de nombreuses possibilités (algorithmiques) pour réaliser une pile. En particulier, nous devons choisir une représentation en mémoire de la pile

La solution la plus simple consiste à représenter la pile comme un tableau d'éléments de taille déterminée. Un indice (que l'on appelera sommet) nous permettra de connaître la position du dernier élément empilé.

5 4 10 2 1 12        
|         |       |
0 SOMMET TAILLE_MAX

 

Si le tableau est indexé de 1 à TAILLE_MAX (fixé, je vous le rappelle), on aura :

  • Sommet = 0 si la pile est vide
  • sommet >0 et sommet < TAILLE_MAX+1 dès qu'il y aura au moins un élément.

Le fait que la pile a désormais une taille limite nous incite à modifier la description fonctionnelle en ajoutant une nouvelle fonction : est_pleine : PILE[G] -> booléen.

Voici quelques fonctions (simplifiée) de la description logique de la pile.

méthode Pile.créer ()
début

 

sommet <- 0
fin_méhode
 
méthode Pile.ajouter ( donnée : élément)
début

 

Si (est_pleine() = FAUX ) alors
  sommet <- sommet +1
tableau[sommet] <- élément
Finsi
fin_méhode
 
méthode Pile.consulter ( résultat : élément)
début

 

Si (est_vide() = FAUX ) alors
  élément <- tableau[sommet]
Finsi
fin_méhode
 
méthode Pile.est_vide ( résultat : état [booléen])
début

 

état <- FAUX
Si (sommet = 0) alors
  état <- VRAI
Finsi
fin_méhode


Description physique

La description logique nous a rapproché de l'implémentation. C'est ce que vous allez faire maintenant. Bien évidemment, il va vous falloir écrire un petit programme Delphi qui démontre les possibilités de la pile.

(1) Créer une nouvelle application.

(2) Réaliser la fiche suivante :

:Choisir un composant TMemo ou TListBox : ce composant permettra "d'afficher" toute la pile. Pour manipuler les éléments de TMemo, on utilise la propriété Lines. Pour manipuler ceux d'un composant TListBox, on utilise la propriété Items.

Exemples :

  • listBox.clear; efface tous les élément de l'objet de type TListBox
  • listBox.Items.add(une_chaine) ajoute un élément

Vous pouvez aussi ajouter des boutons qui donnent l'état de la pile.

(3) Écrire une nouvelle unité qui contiendra la classe TPile.

Le mot-clé array[ind1, ind2] of type_élément permet de définir un tableau d'éléments du type type_élément. Le plus petit indice du tableau est ind1 et le plus grand ind2. Dans un premier temps, nous nous contenterons de stocker des entiers.

(4) Réaliser la jonction entre la fiche dessinée au (2) et la classe définie au (3). Pour cela, on définira une variable globale pile de type TPile dans la fiche (cette variable sera correctement initialisée à la création de la fiche).

Un message d'erreur devra signaler toute opération illicite (MessageDlg):

  • ajouter un élément lorsque la pile est pleine
  • dépiler ou consulter lorsque la pile est vide.

L'implémentation se fera méthode par méthode. Chaque nouvelle méthode sera testée dans la mesure du possible avant de continuer.

(5) Tester correctement le programme dans son intégralité...

(6) Modifier le programme pour que la pile puisse stocker n'importe quel type de variable. Pour cela, il existe un type particulier dénommé Variant.