[JAVA] Implémentation des piles/files

Résolu/Fermé
Signaler
Messages postés
340
Date d'inscription
mardi 3 juillet 2012
Statut
Membre
Dernière intervention
23 février 2018
-
Messages postés
16436
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
26 novembre 2021
-
Bonjour,
je suis un cours de structure de données à la fac, et le prof nous a demandé d'implémenter la notion de piles et de files, avec leurs méthodes push, pop, enqueue, dequeue et peek. Il nous a vivement conseillé d'implémenter ces méthodes dans la classe LinkedList, que nous avons créé il y a quelques semaines. Il a précisé qu'une LinkedList peut être considérée simultanément comme une pile, une file ou une liste. Ce qui me pose problème, c'est comment définir ce que renvoie peek si on ne sait pas exactement si on est dans une pile ou une file ?

1 réponse

Messages postés
16436
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
26 novembre 2021
2 918
Bonjour,

"comment définir ce que renvoie peek si on ne sait pas exactement si on est dans une pile ou une file ?"
Attention : tu n'es ni dans une pile ni dans une file puisque ton implémentation est une liste... tu ne seras jamais autre chose qu'une liste.

Si tu dois implémenter plusieurs interfaces simultanément (pile, file) et quelles ont des méthodes communes (peek), celles-ci doivent faire la même chose tout le temps peu importe leur cas d'utilisation.

Il faut donc t'arranger pour que la tête de la file soit également le haut de la pile, afin que peek renvoie toujours la bonne info pour les deux interfaces.
Messages postés
340
Date d'inscription
mardi 3 juillet 2012
Statut
Membre
Dernière intervention
23 février 2018
48
Ok, merci pour ta réponse.
Le truc, c'est que non seulement je ne vois pas du tout comment faire ça, parce qu'entre renvoyer le premier élément d'une liste et son dernier, ça me semble compliqué de trouver une solution, mais surtout je ne vois plus du tout l'utilité de cette méthode. Le but de pouvoir utiliser la liste comme une pile ou comme une file, c'est justement qu'elle réagisse différemment selon comment on la considère, non ? Quel intérêt alors que la classe fasse la même chose dans les deux cas ?
Messages postés
16436
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
26 novembre 2021
2 918
Le but n'est pas que la liste réagisse différemment, une liste c'est une liste, point.
Par contre on lui rajoute des méthodes qui vont permettre de manipuler ses éléments soit en FIFO pour les méthodes de la file, soit en LIFO pour les méthodes de la pile.

La classe ne va pas faire la même chose dans les deux cas, pour les méthodes de file elle va insérer un élément d'un côté de la liste (début ou fin, peu importe) et le supprimer de l'autre côté, pour les méthodes de pile elle va insérer et supprimer les éléments du même côté.

Ton problème de devoir gérer les deux cas en même temps va juste t'imposer une contrainte supplémentaire, celle que le côté où l'on supprime l'élément de la file, soit le même que celui où l'on supprime l'élément de la pile, afin que peek aille toujours de ce côté là pour récupérer sa valeur.