Objectif : nous implantons en Java une structure de pile LIFO (Last In First Out) fondée sur l'utilisation d'un objet de classse LinkedList. Nous construisons une pile LIFO de chaînes de caractères.
Rappel des spécifications
d'une pile LIFO :
 |
Opérateurs de base sur une pile LIFO :
sommet pointe vers l'élément en haut de pile, fond sert de sentinelle à la pile si nécessaire. Dépiler ( [X0, X1,..., Xn,
Xn+1] ) -->
Empiler( [X0, X1,..., Xn ] , Xn+1
) -->
Premier( [X0, X1,..., Xn ] ) = Xn EstVide( [X0, X1,..., Xn ] ) = false
|
La classe LinkedList est une structure dynamique (non synchronizée)
qui ressemble à la classe Vector, mais qui est bien adaptée
à implanter les piles et les files. Notre pile LIFO doit contenir
des noms (chaînes de caractères).
Proposition de squelette de classe Java algorithmique :
Nous utilisons un objet de classe LinkedList pour représenter
une pile LIFO, elle sera passée comme paramètre dans
les méthodes qui travaillent sur cet objet :
| static boolean EstVide (LinkedList P) | tester si la pile P est vide |
| static void Empiler(LinkedList P, String x) | Empiler dans la pile P le nom x. |
| static String Depiler(LinkedList P) | Dépiler la pile P. |
| static String Premier(LinkedList P) | Renvoyer l'élément au sommet de la pile P. |
| static void initialiserPile(LinkedList P) | Remplir la pile P avec des noms. |
| static void VoirLifo(LinkedList P) | Afficher séquentiellement le contenu de P. |
Complétez la classe et ses méthodes :
 |
Remonter 
Voici ci-dessous les méthodes principalement utiles à la manipulation d'une telle liste:
Classe LinkedList :
| boolean add(Object elem) | Ajoute l'élément "elem" à la fin de la LinkedList et augmente sa taille de un. |
| void add(int index, Object elem) | Ajoute l'élément "elem" à la position spécifiée par index et augmente la taille de la LinkedList de un. |
| void clear( ) | Efface tous les éléments présents dans la LinkedList et met sa taille à zéro. |
| Object getFirst() | Renvoie le premier élément de la LinkedList (l'élément en tête de liste, rang=0). Il faudra le transtyper selon le type d'élément de la LinkedList. |
| Object getLast() | Renvoie le dernier élément de la LinkedList (l'élément en fin de liste, rang=size()-1). Il faudra le transtyper selon le type d'élément de la LinkedList. |
| Object get(int index) | Renvoie l'élément de rang index de la LinkedList. Il faudra le transtyper selon le type d'élément de la LinkedList. |
| int indexOf(Object elem) | Cherche le rang de la première occurence de l'élément "elem" dans le Vector. Renvoie une valeur comprise entre 0 et size()-1 si "elem" est trouvé, revoie -1 sinon. |
| void addFirst(Object elem) | Insère l'élément "elem" en tête de la LinkedList (rang=0). |
| void addLast(Object elem) | Ajoute l'élément "elem" à la fin de la LinkedList et augmente sa taille de un. |
| boolean isEmpty( ) | Teste si la LinkedList n'a pas d'éléments (renvoie true); renvoie false si elle contient au moins un élément. |
| Object remove(int index) | Efface l'élément de rang index de la LinkedList. La taille de la LinkedList diminue de un. |
| boolean remove(Object elem) | Efface la première occurence de l'élément elem de la LinkedList, la taille de la LinkedList diminue alors de un et renvoie true. Si elem n'est pas trouvé la méthode renvoie false et la LinkedList n'est pas touché. |
| Object removeFirst() | Efface et renvoie le premier élément (rang=0) de la LinkedList. Il faudra le transtyper selon le type d'élément de la LinkedList. |
| Object removeLast() | Efface et renvoie le dernier (rang=size()-1) élément de la LinkedList. Il faudra le transtyper selon le type d'élément de la LinkedList. |
| int size( ) | Renvoie la taille de la LinkedList (le nombres d'éléments contenus dans la LinkedList). |
Remonter