Objectif : nous implantons en Java une structure de file FIFO (First In First Out) fondée sur l'utilisation d'un objet de classse LinkedList. Nous construisons une file FIFO de chaînes de caractères.
Rappel des spécifications d'une pile LIFO :
Opérateurs de base sur une file FIFO :
sommet pointe vers l'élément en tête de file, queue pointe vers l'élément en fin de file.
retirer ( ] Xn, Xn-1,..., X1, X0] ) --> file = ] Xn, Xn-1,..., X1 ] , X0
ajoutler( ] Xn, Xn-1,..., X1, X0] , Xn+1 ) -->file = ] Xn+1, Xn, Xn-1,..., X1, X0 ]
Premier( ] Xn, Xn-1,..., X1, X0] ) = X0
EstVide( ] Xn, Xn-1,..., X1, X0]
) = false
EstVide( ] ] ) = true
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 file FIFO 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 file FIFO, elle sera passée comme paramètre dans
les méthodes qui travaillent sur cet objet :
| static boolean EstVide (LinkedList F) | tester si la file F est vide |
| static void ajouter(LinkedList F, String x) | Ajouter en queue de file F le nom x. |
| static String retirer(LinkedList F) | Retirer le nom en tête de file F. |
| static String Premier(LinkedList F) | Renvoyer le nom en tête de file F. |
| static void initialiserFile(LinkedList F) | Remplir la file F avec des noms. |
| static void VoirFifo(LinkedList F) | Afficher séquentiellement le contenu de la file F. |
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