:: Enseignements :: ESIPE :: E4INFO :: 2012-2013 :: Java Avancé ::

Faites la queue

Le but de ce TD est d'implanter une queue 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 queue et poll qui permet de retirer un élement en début de la queue.
L'idée est d'utiliser deux index, un index correspondant à la tête de la queue pour retirer les élements et un index correspondant à la queue de la queue pour ajouter des élements. Lorsque l'on insère un élement, on incrémentera la queue de la queue, lorsque l'on retirera un élement, on incrémentera la tête de la queue.
Il y a juste un petit problème car si la tête est égale à la queue, cela peut vouloir dire, que soit la Queue est vide, soit elle est pleine. L'astuce consiste à utiliser une troisième variable qui stocke le nombre d'élements dans la Queue.

Ecrire une classe Fifo dans le package fr.umlv.queue prenant en paramètre le nombre maximal d'élements que peut stocker la structure de données. Penser à vérifier les préconditions.
Ajouter une méthode offer qui ajoute un élement de type Object dans la queue. Penser à vérifier les préconditions sachant que l'on veut interdire de pouvoir stocker null.
Ecrire une méthode poll qui retire un élement de type Object de la queue. Penser à vérifier les préconditions.
Rappeler ce qu'est un memory leak en Java et assurez-vous que votre implémentation n'a pas ce comportement indésirable.
Ajouter une méthode size et une méthode isEmpty
Ajouter une méthode d'affichage sachant que les éléments devront être affichés entre crochets ('[' et ']') et séparés par des virgules

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

Exercice 2 - ResizableFifo

On souhaite maintenant que la queue circulaire puisse s'agrandir si jamais il n'y a plus assez de place et que la queue fournisse un iterateur.

Indiquer comment il faut agrandir la queue si celle-ci est pleine et que l'on veut doubler sa taille.
Implanter la solution retenue dans une nouvelle classe ResizableFifo.
Rappeler quel est le principe d'un itérateur.
Implanter la méthode iterator() qui renvoie un Iterator<Object>
Rappeler à quoi sert l'interface Iterable.
Faire en sorte que votre queue implante Iterable.
En fait, il existe déjà une interface pour les queue 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 quelles sont les méthodes qu'il faut implanter en plus et celle dont l'implantation devra être modifiée.
Faire en sorte que la classe ResizableFifo implante l'interface Queue<Object>.

Exercice 3 - Generics, generics

On souhaite générifier la classe ResizableFifo.

Rappeler quel est l'intérêt de déclarer ResizableFifo comme un type paramétré.
Faire en sorte que la classe ResizableFifo implante l'interface Queue<E>.

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

Exercice 4 - [A la maison]

On souhaite utiliser la ResizableFifo créer ci-dessus pour faire un parcours en largeur d'un arbre (donc il n'y a pas de cycle).
On utilisera pour cela, la classe Tree fourni

Ecrire dans une classe Trees une méthode breadthFirstSearch prenant un objet Tree correspondant à la racine et renvoyant une liste de Tree correspondant à un parcours en largeur des noeuds de l'arbre.

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