:: Enseignements :: Master :: M1 :: 2015-2016 :: Java Avancé ::

Faites la queue

Le but de ce TD est d'implanter une file d'attente en utilisant un tableau de façon circulaire et de jouer un peu avec les types paramétrés.

Exercice 1 - Fifo

On souhaite écrire une structure de données first-in first-out (FIFO) utilisant un tableau circulaire qui aura, au moins au début, une taille fixée à la création.
Les deux opérations principales sont offer qui permet d'insérer un élement à la fin de la file et poll qui permet de retirer un élement en début de la file.
L'idée est d'utiliser deux index, un correspondant à la tête de la file pour retirer les élements et un index correspondant à la queue de la file pour ajouter des élements. Lorsque l'on insère un élement, on incrémentera la queue de la file, lorsque l'on retirera un élement, on incrémentera la tête de la file.
De plus, il est impossible de stocker null dans la file.

Cette représentation a un petit problème car si la tête et la queue correspondent au même index, il n'est pas facile de détecter si cela veux dire que la file est pleine ou vide.
Comment doit on faire pour détecter si la file est pleine ou vide ?
Cette question a plusieurs réponses :)
Ecrire une classe Fifo générique (avec une variable de type E) dans le package fr.umlv.queue prenant en paramètre le nombre maximal d'élements que peut stocker la structure de données. Pensez à vérifier les préconditions.
Ecrire la méthode offer qui ajoute un élement de type E dans la file. Pensez à vérifier les préconditions sachant que, de plus, on veut interdire le stockage de null.
Comment détecter que la file est pleine ?
Que faire si la file est pleine ?
Ecrire une méthode poll qui retire un élement de type E de la file. Penser à vérifier les préconditions.
Que faire si la file est vide ?
Ajouter une méthode d'affichage qui affiche les élements dans l'ordre dans lequel ils seraient sortis en utilisant poll.
Note: attention à bien faire la différence entre la file pleine et la file vide.
Note2: L'idée est d'avoir un index i qui va de 0 à size. dans ce cas, comment récupérer la case dans le tableau correspondant à i.
L'ensemble des élements devra être affiché entre crochets ('[' et ']') avec les élements séparés par des virgules.
Rappelez ce qu'est un memory leak en Java et assurez-vous que votre implantation n'a pas ce comportement indésirable.
Ajouter une méthode size et une méthode isEmpty.
Rappelez quel est le principe d'un itérateur.
Quel doit être le type de retour de la méthode iterator() ?
Implanter la méthode iterator() avec un index qui va de 0 à size.
Note: ici, pour simplifier le problème, on considèrera que l'itérateur ne peut pas supprimer des éléments pendant son parcours.
Rappeler à quoi sert l'interface Iterable.
Faire en sorte que votre file soit Iterable.

Vérifier avec le test unitaire suivant que votre implantation est bien conforme. FifoTest.java

Exercice 2 - ResizeableFifo

On souhaite maintenant que le tableau circulaire de la file puisse s'agrandir si jamais il n'y a plus assez de place.

Indiquer comment faut-il agrandir la file si celle-ci est pleine et que l'on veut doubler sa taille. Attention, il faut penser au cas où le début de la liste à un index qui est supérieur à l'index indiquant la fin de la file.
Implanter la solution retenue dans une nouvelle classe ResizeableFifo.
Note: il existe les méthodes Arrays.copyOf et System.arraycopy.
En fait, il existe déjà une interface pour les files dans le JDK appelée java.util.Queue.
Sachant qu'il existe une classe AbstractQueue qui fournit déjà des implantations par défaut de l'interface Queue indiquer
1. quelles sont les méthodes supplémentaires à implanter.
2. quelles sont les méthodes dont l'implantation doit être modifiée.
3. quelles sont les méthodes que l'on peut supprimer.
Faire en sorte que la classe ResizableFifo implante l'interface Queue.

Vérifier avec le test unitaire suivant que votre implantation est bien conforme. ResizeableFifoTest.java