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é.

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.