:: Enseignements :: Master :: M1 :: 2020-2021 :: 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 pour représenter un file d'attente (first-in first-out ou FIFO) utilisant un tableau circulaire qui aura, au moins au début du TP, une taille fixée à la création.
Les deux opérations principales sont offer qui permet d'insérer un élément à la fin de la file et poll qui permet de retirer un élément en début de la file.
L'idée est d'utiliser deux indices, un correspondant à la tête de la file pour retirer les éléments et un correspondant à la queue de la file pour ajouter des éléments. Lorsque l'on insérera un élément, on incrémentera la queue de la file, lorsque l'on retirera un élément, on incrémentera la tête de la file.
De plus, il est impossible de stocker null dans la file.

Cette représentation peut poser problème, car si la tête et la queue correspondent au même indice, 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 possibles :).
Écrire 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’éléments que peut stocker la structure de données. Pensez à vérifier les préconditions.
Écrire la méthode offer qui ajoute un élément de type E dans la file. Pensez à vérifier les préconditions sachant que, notamment, on veut interdire le stockage de null.
Comment détecter que la file est pleine ?
Que faire si la file est pleine ?
Écrire une méthode poll qui retire un élément 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 éléments dans l'ordre dans lequel ils seraient sortis en utilisant poll. L'ensemble des éléments devra être affiché entre crochets ('[' et ']') avec les éléments séparés par des virgules (suivies d'un espace).
Note : attention à bien faire la différence entre la file pleine et la file vide.
Note 2 : Il existe une classe StringJoiner qui est ici plus pratique à utiliser qu'un StringBuilder !
Indication : Vous avez le droit d'utiliser 2 compteurs.
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().
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.
On va garder un entier pour le constructeur qui au lieu d'indiquer la taille va indiquer la capacité initial de la file (la taille avant un possible agrandissement).

Indiquer comment 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 a un indice qui est supérieur à l'indice 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.