Stack java
Résolu/Fermé
yuri648
Messages postés
677
Date d'inscription
mardi 30 décembre 2008
Statut
Membre
Dernière intervention
20 mai 2015
-
5 janv. 2009 à 21:35
yuri648 Messages postés 677 Date d'inscription mardi 30 décembre 2008 Statut Membre Dernière intervention 20 mai 2015 - 6 janv. 2009 à 16:50
yuri648 Messages postés 677 Date d'inscription mardi 30 décembre 2008 Statut Membre Dernière intervention 20 mai 2015 - 6 janv. 2009 à 16:50
A voir également:
- Stack java
- Waptrick java football - Télécharger - Jeux vidéo
- Java apk - Télécharger - Langages
- Jeux java itel football - Télécharger - Jeux vidéo
- Jeux java itel 5360 ✓ - Forum Mobile
- Java jre - Télécharger - Langages
3 réponses
Marco la baraque
Messages postés
996
Date d'inscription
vendredi 9 mai 2008
Statut
Contributeur
Dernière intervention
5 novembre 2009
328
6 janv. 2009 à 01:49
6 janv. 2009 à 01:49
Bonsoir Yuri648,
Il est conseillé d'utiliser des instances de classes implémentant Deque pour gérer les files (FIFO) et les piles (LIFO).
Tu peux donc utiliser aussi bien des ArrayDeque que des LinkedList.
Cependant pour les files il est conseillé d'utiliser des ArrayDeque car l'implémentation des méthodes a une complexité en temps plus efficace que celles de la LinkedList. Pour la pile par contre, rien n'est précisé (personnellement j'utiliserais une LinkedList parce que si je l'implémentais moi-même ce serait plus efficace, mais le plus sûr serait de vérifier les algorithmes en regardant le code des 2 classes).
J'essayerai de regarder ça demain (je ne promets rien).
En tout cas, pour résumer, le mieux serait donc de faire :
Bon, en commentaire on va dire que dans l'interface Deque, il y a beaucoup de méthodes qui font la même chose (c'est assez bien résumé dans l'API), parce que :
- Deque étend elle-même d'autres interfaces (Queue notamment)
- certaines méthodes ont le même nom que d'anciennes méthodes d'autres classes (que la classe Stack par exemple, pour garder le même nom de méthode, certaines méthodes sont accessibles via plusieurs noms, comme push() et addFirst()).
Cordialement,
Il est conseillé d'utiliser des instances de classes implémentant Deque pour gérer les files (FIFO) et les piles (LIFO).
Tu peux donc utiliser aussi bien des ArrayDeque que des LinkedList.
Cependant pour les files il est conseillé d'utiliser des ArrayDeque car l'implémentation des méthodes a une complexité en temps plus efficace que celles de la LinkedList. Pour la pile par contre, rien n'est précisé (personnellement j'utiliserais une LinkedList parce que si je l'implémentais moi-même ce serait plus efficace, mais le plus sûr serait de vérifier les algorithmes en regardant le code des 2 classes).
J'essayerai de regarder ça demain (je ne promets rien).
En tout cas, pour résumer, le mieux serait donc de faire :
Deque<Deque> pile = new LinkedList<Deque>(); Queue<TaClasse> file1 = new ArrayDeque<TaClasse>(); file1.add(new TaClasse()); Queue<TaClasse> file2 = new ArrayDeque<TaClasse>(); file2.add(new TaClasse()); pile.push(file1); pile.push(file2);
Bon, en commentaire on va dire que dans l'interface Deque, il y a beaucoup de méthodes qui font la même chose (c'est assez bien résumé dans l'API), parce que :
- Deque étend elle-même d'autres interfaces (Queue notamment)
- certaines méthodes ont le même nom que d'anciennes méthodes d'autres classes (que la classe Stack par exemple, pour garder le même nom de méthode, certaines méthodes sont accessibles via plusieurs noms, comme push() et addFirst()).
Cordialement,
Marco la baraque
Messages postés
996
Date d'inscription
vendredi 9 mai 2008
Statut
Contributeur
Dernière intervention
5 novembre 2009
328
6 janv. 2009 à 16:11
6 janv. 2009 à 16:11
Bon,
Après avoir regardé de plus près le code de ArrayDeque et de LinkedList, j'avoue que ça me semble pareil en terme de complexité.
LinkedList est en fait une implémentation d'une circular double linked list, autrement dit on récupère en temps constant aussi bien la tête de liste que la queue de liste, et que pour chaque élément on peut récupérer l'élément précédent ou l'élément suivant. Donc en ce qui concerne une pile, on peut récupérer la tête de pile et temps constant (donc l'ajout et la suppression se font en temps constant, la recherche en O(n)). En ce qui concerne la file, c'est les mêmes complexités.
ArrayDeque et un simple tableau avec une tête et une queue qui sont des indices qui vont varier lors de l'ajout et de la suppression d'éléments. La présence de tête et de queue permet de gérer aussi bien des files que des piles, avec la même complexité : ajout en début et fin en temps constant (ou moyennant une allocation pour le début), la suppression en début et en fin en temps constant, la recherche en O(n).
D'après mes recherches, je ne saisis donc pas pourquoi ils indiquent dans la javadoc qu'il est préférable d'utiliser une ArrayDeque pour implémenter les FIFO. Apparemment les complexités sont les mêmes, mais l'allocation et la désallocation a d'après moi un coût plus important.
Personnellement (et contre l'avis des développeurs Sun, donc il ne faut pas m'écouter :)), j'utiliserais des LinkedList tout le temps. L'idéal (je me pencherai peut-être un jour sur ce problème) serait d'effectuer des tests de performance pour trouver empiriquement quelle structure est la mieux adaptée pour implémenter une file ou une pile.
Cordialement,
Après avoir regardé de plus près le code de ArrayDeque et de LinkedList, j'avoue que ça me semble pareil en terme de complexité.
LinkedList est en fait une implémentation d'une circular double linked list, autrement dit on récupère en temps constant aussi bien la tête de liste que la queue de liste, et que pour chaque élément on peut récupérer l'élément précédent ou l'élément suivant. Donc en ce qui concerne une pile, on peut récupérer la tête de pile et temps constant (donc l'ajout et la suppression se font en temps constant, la recherche en O(n)). En ce qui concerne la file, c'est les mêmes complexités.
ArrayDeque et un simple tableau avec une tête et une queue qui sont des indices qui vont varier lors de l'ajout et de la suppression d'éléments. La présence de tête et de queue permet de gérer aussi bien des files que des piles, avec la même complexité : ajout en début et fin en temps constant (ou moyennant une allocation pour le début), la suppression en début et en fin en temps constant, la recherche en O(n).
D'après mes recherches, je ne saisis donc pas pourquoi ils indiquent dans la javadoc qu'il est préférable d'utiliser une ArrayDeque pour implémenter les FIFO. Apparemment les complexités sont les mêmes, mais l'allocation et la désallocation a d'après moi un coût plus important.
Personnellement (et contre l'avis des développeurs Sun, donc il ne faut pas m'écouter :)), j'utiliserais des LinkedList tout le temps. L'idéal (je me pencherai peut-être un jour sur ce problème) serait d'effectuer des tests de performance pour trouver empiriquement quelle structure est la mieux adaptée pour implémenter une file ou une pile.
Cordialement,
yuri648
Messages postés
677
Date d'inscription
mardi 30 décembre 2008
Statut
Membre
Dernière intervention
20 mai 2015
7
6 janv. 2009 à 16:50
6 janv. 2009 à 16:50
merci bcp mon ami
