Développement 3.2
Files
Une file est une structure abstraite de données normalement limitée à deux opérations :
- enqueue
-
ajoute une donnée à la structure.
- dequeue
-
retire et renvoie la donnée la plus ancienne contenue dans la structure. Cette
opération n'est pas définie sur une file vide.
Les files sont mieux traitées en Java que les piles, et l'interface Queue<E> est une représentation adéquate de cette structure. Elle hérite de l'interface plus générale Collection<E>, ce qui fait que la liste des opérations à concrétiser est plutôt longue. Les réalisations de Queue<E> « faits main » préfèreront hériter de AbstractQueue<E> pour gagner du temps.
Parmi les classes qui honorent l'interface Queue<E>, on trouve notamment ArrayDeque<E>, basée sur un tableau, et LinkedList<E>, basée sur une liste chaînée.
-
Fusion. Il existe de nombreux algorithmes de tri, la plupart du temps destinés aux tableaux, mais l'un d'entre eux (parmi les plus performants) s'applique très bien aux files : il s'agit du tri fusion (merge sort).
Ce tri tire son nom d'une technique très simple : si on dispose de deux files déjà triées, on peut les fusionner en une seule file triée comme on le ferait avec deux paquets de cartes.
L'algorithme fonctionne en trois phases :
- séparation de la file en deux moitiés égales,
- tri de chaque moitié (par deux appels récursifs),
- fusion des deux moitiés.
Écrivez des méthodes scinder et fusionner représentant respectivement la première et la dernière phase puis une méthode trier rassemblant toutes les étapes.
Testez votre tri dans un programme qui prend une liste de réels sur la ligne de commande, puis affiche les mêmes valeurs dans l'ordre croissant (utilisez une boucle énumérative pour cet affichage). Les files manipulées devront appartenir à l'une des classes de l'API Java.
Remarque Pour trier, il faut nécessairement être capable de comparer deux éléments. Votre méthode de tri devra donc n'accepter que les files dont le type paramètre respecte Comparable<T>. Vous pouvez vous baser sur la signature de la méthode sort de la classe Collections qui fait un travail similaire.
-
Chaîne. Écrivez votre propre classe respectant Queue<E> et stockant ses éléments dans une liste chaînée. Regardez dans la documentation de la classe AbstractQueue<E> pour découvrir quelles méthodes vous devez concrétiser.
Modifiez le programme de l'exercice précédent pour qu'il utilise votre version des files.
-
Tableau. Faites la même chose qu'à l'exercice précédent, mais avec une classe qui stocke ses éléments dans un tableau.
-
Serpent. Écrivez une application qui permet de jouer au Snake sur une grille de 25x25 cases.
Pour observer les touches du clavier, employez un KeyListener. Pour faire avancer le serpent à intervalles réguliers, utilisez un Timer.
Remarque Idéalement, votre application devrait employer deux files. Trouvez pourquoi avant de vous lancer dans le codage !