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

Faite 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ée first-in first-out (FIFO) utilisant un tableau circulaire qui aura au moins au début une taille fixé à 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 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 ou que soit elle est pleine. L'astuce consiste à utiliser une traisième variable qui stocke le nombre d'élement dans la Queue.

Ecrire une classe Fifo dans le package fr.umlv.queue prenant en paramètre le nombre maximale d'élements que peut stocker la structure de donnée. 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 de plus 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 élements devront être affichés entre crochets ('[' et ']') et séparer par des virgules

Verifier 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 à ce que la queue founisse 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 quelle est le principe d'un iterateur.
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 fourni déjà des implantation 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 modifier.
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>.

Verifier 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 classes 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.

Verifier avec le test unitaire que votre implantation est bien conforme. TreesTest.java.