Tableau, Liste, Piles, Files et Classes Java

Bonjour :zoubi:

En fait si on ne parle de pas de java au départ mais sur :

Les structures de données :

- tableau : taille fixe en java considéré comme un objet de type générique ou primaire

- liste : une suite finie de données de même type donc comme un tableau mais avec une définition récursive :

- soit vide
- soit la juxtaposition d’un premier élément et une autre liste :

- représentée par un tableau donc limité avec des indices pour le premier element et l'autre liste= listes contigues

- référencé par un pointeur juste après le premier élement = listes chainées

- piles et files : sont elles des listes particulières et donc utilisable avec ou sans tableau ? mais peut-être que je me trompe là

car seul les piles sont souvent présentées avec des listes (donc avec ou sans tableau) et les files avec juste un tableau, je n'ai pas encore essayé mais pourquoi ne pourraient elles pas avec une liste chainée ?

Mais comme en Java sur ce diagramme :

http://www.codejava.net/images/artic...20overview.png

les files sont appelés Queue ok. mais comme sur ce diagramme où l'on voit pas par contre que Stack hérite de Vector qui serait les piles. que LinkedList, associés au listes chainées, hérite de Deque et de List. par contre Queue est une classe seule (juste Collections ) mais celà voudrait dire qu'une file n'est pas une liste alors que c'est très souvent présenté comme une liste plus restrictive comme pour les piles.

J'avoue que je m'y perd. J'ai essayé d'être clair sur mes interrogations.

En tout cas merci si quelqu'un arrive à me clarifier les choses ;)

Ce qu'il faut bien comprendre quand tu regarde ce schéma, c'est qu'une grande partie sont seulement des constructions abstraites.

Si on prends l'exemple de ta classe Stack. Celle-ci hérite de Vector, pour ajouter le comportement d'une LIFO.

Citation:

---

Envoyé par Javadoc Stack

The Stack class represents a last-in-first-out (LIFO) stack of objects.

---

Il se trouve qu'il ne faut pas grand chose pour avoir le comportement d'une LIFO à partir de la classe Vector :

Citation:

---

Envoyé par Javadoc Stack

The Vector class implements a growable array of objects.

---

En fait, il suffit de manipuler correctement ton tableau pour avoir le comportement d'une LIFO.
D'ailleurs si tu regarde le code de la classe Stack, c'est seulement cela que tu verra :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42

public class Stack<E> extends Vector<E> {   public Stack() { }   public E push(E item) { addElement(item);   return item; }   public synchronized E pop() { E obj; int len = size();   obj = peek(); removeElementAt(len - 1);   return obj; }   public synchronized E peek() { int len = size();   if (len == 0) throw new EmptyStackException(); return elementAt(len - 1); }   public boolean empty() { return size() == 0; }   public synchronized int search(Object o) { int i = lastIndexOf(o);   if (i >= 0) { return size() - i; } return -1; } }

---

Donc la classe Stack est basé sur la classe Vector, car celle-ci fait déjà le plus gros du travail pour nous. Stack n'ajoute qu'une petite partie de comportement sur la manipulation.

Du coup, pourquoi la classe Vector hérite de la classe AbstractList ?

La classe Vector implémente l'interface List. Or Il se trouve que la classe abstrait AbstractList est là pour "facilité la vie" de toutes implémentations de l'interface List. (Car, il n'y a pas de code/comportement dans une interface).
Du coup, il y a la classe AbstractList !

Citation:

---

Envoyé par Javadoc AbstractList

This class provides a skeletal implementation of the {@link List} interface to minimize the effort required to implement this interface backed by a "random access" data store (such as an array).

---

En gros, c'est un facilitateur :

Code:

---

1 2 3 4

public boolean add(E e) { add(size(), e); return true; }

---

Même si il y a du code un peu complexe dans cette classe, l'idée est bien d'avoir un facilitateur pour un certains nombre de méthode qui ne dépends pas directement de l'implémentation de la liste.

Il y a certains principe de base dans cette structure.

• Les interfaces vont du plus simple au plus compliqué.
• En général, il est fournit une version "Abstraite" d'une interface.
• Et les héritages entre classes, ne se font que pour ajouter du comportement spécifique.

Note :
Pour ce qui est de la liste chainé LinkedList, celle-ci implémente Queue et Deque. Qui sont respectivement la pile (FIFO) et la pile accessible par les deux bouts.
Ce qu’implémente la liste chainé.

Cordialement,
Patrick Kolodziejczyk.

Source :
https://docs.oracle.com/javase/7/doc...tractList.html
https://docs.oracle.com/javase/7/doc...til/Stack.html
https://docs.oracle.com/javase/7/doc...il/Vector.html
http://docs.oracle.com/javase/7/docs...til/Queue.html
http://docs.oracle.com/javase/7/docs...til/Deque.html
http://docs.oracle.com/javase/7/docs...inkedList.html

Merci beaucoup

Juste que dans les cours "théoriques "ça parait être l'inverse :
les piles recrées sont aussi des listes et les files recrées sont souvent implémentées avec des tableaux
en plus d'avoir des lacunes telles en anglais qui me bloque à aller fouiller dans les fiches du site oracle

ce qui m'a amené à poster pour mieux comprendre

de plus souvent c'est peut-etre autre chose mais j'ai du mal à comprendre la différence entre:

Queue<AB<Integer>> q= new LinkedList<AB<Integer>>();
et
LinkedList<AB<Integer>> q= new LinkedList<AB<Integer>>();

Citation:

---

Queue<AB<Integer>> q= new LinkedList<AB<Integer>>();

---

Ici, tu définis une Queue q en utilisant les paramètres de l'interface Queue. LinkedList est l'implémentation utilisée (qui implémente Queue via l'interface Deque)
Donc avec q, tu ne pourras utiliser que les méthodes propres à l'interface

Citation:

---

LinkedList<AB<Integer>> q= new LinkedList<AB<Integer>>();

---

Ici, tu définis une LinkedList q utilisant l'implémentation LinkedList. Mais tu pourrais utiliser une autre implémentation héritant de LinkedList
Ici, tu auras accès à toutes les méthodes et propriétés publiques propres à LinkedList, à savoir... Aucune vu que toutes les méthodes publiques utilisables sont décrites dans les interfaces.


C'est plus "propre" de manière générale de travailler avec des interfaces plutôt que des implémentation parce que ça permet de rendre l'usage moins lié à une seule implémentation.
Imagine que tu as la méthode suivante dans une classe :
void doThings(LinkedList<AB<Integer>>)
Que tu utilises comme ceci

Code:

---

1 2 3

LinkedList<AB<Integer>> q= new LinkedList<AB<Integer>>(); doThings(q);

---

Et tu te rends compte que l'implémentation ArrayDeque est vraiment plus intéressante pour toi.... Ben tu ne pourras pas utiliser ta méthode sans changer ton implémentation et ta signature de méthode...
Si maintenant tu as la méthode
void doThings(Queue<AB<Integer>>)

tu n'as qu'a changer l'implémentation utilisée et ça marche !

Code:

---

1 2 3

Queue<AB<Integer>> q= new ArrayDeque<AB<Integer>>(); doThings(q);

---

A noter que Vector et Stack sont déconseillées.

Car elles implémentent des mécanismes de synchronisation qui sont légèrement pénalisants pour les performances et que pour la gestion de la concurrence on peut trouver des structures mieux optimisées. De plus, les "services" offerts par Stack ne font pas l'objet d'une interface et lie donc fortement les APIs à cette classe alors qu'il existe l'inteface Queue et Deque pour abstraire ces comportements.

"Ici, tu définis une LinkedList q utilisant l'implémentation LinkedList. Mais tu pourrais utiliser une autre implémentation héritant de LinkedList
Ici, tu auras accès à toutes les méthodes et propriétés publiques propres à LinkedList, à savoir... Aucune vu que toutes les méthodes publiques utilisables sont décrites dans les interfaces."

j'avoue ne pas bien comprendre. outre le fait que dans les collections java LinkedList semble être la dernière classe donc apart créé une classe fille y'a rien... mais
si LinkedList implémente toutes les méthodes de ses parents je ne pige pas cette phrase :

"Aucune vu que toutes les méthodes publiques utilisables sont décrites dans les interfaces." si elles sont décrites elles sont dans la classe Linkedlist de fait non ? comme si je l'avais créé moi même cette classe ?

après je crois comprendre le reste mais pas sur sur des cas pratiques et l'usage surement mais en tant que débutant on perçoit par les astuces et les obstacles

Citation:

---

Envoyé par nouilletonne

"Ici, tu définis une LinkedList q utilisant l'implémentation LinkedList. Mais tu pourrais utiliser une autre implémentation héritant de LinkedList
Ici, tu auras accès à toutes les méthodes et propriétés publiques propres à LinkedList, à savoir... Aucune vu que toutes les méthodes publiques utilisables sont décrites dans les interfaces."

j'avoue ne pas bien comprendre. outre le fait que dans les collections java LinkedList semble être la dernière classe donc apart créé une classe fille y'a rien...

---

Sauf si tu décides de créer une classe qui étend LinkedList. Celle-ci n'étant pas final, rien ne t'interdit de le faire pour lui rajouter des fonctionnalités (comme par exemple un système de timer qui ferai disparaître aléatoirement des éléments de la liste au fur et à mesure... C'est la première idée qui me soit venue, ne cherchez pas :p )

Citation:

---

si LinkedList implémente toutes les méthodes de ses parents je ne pige pas cette phrase :

"Aucune vu que toutes les méthodes publiques utilisables sont décrites dans les interfaces." si elles sont décrites elles sont dans la classe Linkedlist de fait non ? comme si je l'avais créé moi même cette classe ?

---

Si LinkedList implémente toutes les méthodes de ses parents, sa déclaration n'apporte pas d'éléments supplémentaire pour son utilisation. Du coup, tu peux la déclarer comme une Queue, ce qui te laisser libre ensuite de pouvoir modifier l'implémentation utilisée.
Tu sais que LinkedList est-une Queue, et que LinkedList n'apporte aucune fonctionnalité particulière par rapport à la définition d'une Queue -> autant utiliser la déclaration de l'interface.


Autre exemple
Imaginons que tu utilises une ArrayList, classe qui implémente List (qui est une Collection).
ArrayList a des fonctionnalités en plus que celles listées dans l'interface List, comme la méthode ensureCapacity(int), ou la méthode trimToSize()
Si tu n'as pas besoin de ces fonctionnalités dans l'usage de ton ArrayList, autant déclarer que tu utilises une List.
Allons plus loin, si tu n'as pas besoin des fonctionnalités spécifiques à List comme add(int), remove(int), indexOf(Object) et que tu n'as besoin que de iterator() et isEmpty(), alors autant la déclarer comme une Collection !

Je commence à comprendre

en fait en pratique on ne peut pas savoir apart analyser sérieusement par Uml et encore, que l'on peut avoir besoin d'une autre classe issue d'une interface plutôt qu'une autre et que délcarer par une classe final ou presque ferme la possibilité d'instancier une autre pourtant issue de la même interface. c'est celà ?

mais j'avoue que j'ai du mal aussi à manier naturellement les concepts extends et implément et peut-être même aussi
déclaration Type nom_objet_var = NEW pour instancié un objet

théoriquement je comprend mais c'est pas encore naturel non plus entre les Types Objets

j'ai même du mal (toujours de manière naturel) avec le terme "implémentation", "codage", "implanter"

et il y a surement d'autres concepts non naturels encore

Citation:

---

Envoyé par nouilletonne

en fait en pratique on ne peut pas savoir apart analyser sérieusement par Uml et encore, que l'on peut avoir besoin d'une autre classe issue d'une interface plutôt qu'une autre et que délcarer par une classe final ou presque ferme la possibilité d'instancier une autre pourtant issue de la même interface. c'est celà ?

---

Il y a trop de questions dans ta question :aie:

Le choix de passer par une interface ou une classe dépend du besoin fonctionnel. De manière générale, il faut essayer d'utiliser les éléments les plus abstraits possibles qui répondent à ton besoin (ça permet d'être plus souple dans les développements).


Pour le reste, j'ai envie de dire : ça viendra !
N'hésite pas à lire le code source de l'API Java.
Regarde par exemple la classe Collections qui contient des méthodes génériques pour manipuler les collections. Tous les paramètres sont soit des Collection (le cas de addAll par exemple), soit des List (pour shuffle par exemple, parce qu'une liste peut être ordonnée et triée, donc on peut aussi la mélanger. Une collection n'est pas triée donc on ne peut pas la mélanger : elle l'est de base !), soit des Map (parce qu'un Map est une interface qui décrit un système de stockage clé/valeur, mais qui n'est pas une Collection !). Du coup, on peut utiliser la méthode Collections.shuffle() sur des listes de type ArrayList, LinkedList ou Vector sans connaitre l'implémentation réelle de la liste manipulée. On s'en moque, on sait qu'on peut la mélanger !

ça peut vous paraitre idiot ce que je vais dire :
qu'entendez vous par consulter le code source de l'API de java : le site de doc oracle ou les fichiers et dos du path du jdk/jre (qui pour l'instant je n'irai jamais farfouiller )

Citation:

---

Envoyé par nouilletonne

ça peut vous paraitre idiot ce que je vais dire :
qu'entendez vous par consulter le code source de l'API de java : le site de doc oracle ou les fichiers et dos du path du jdk/jre (qui pour l'instant je n'irai jamais farfouiller )

---

L'ensemble des interfaces et classes que vous voulez comprendre sont écris en Java. Et les sources de ces classes et interfaces sont à la fois documenté et fournit.

La documentation d'une API Java est appelé Javadoc. Et celle du standard est disponible ici : http://docs.oracle.com/javase/7/docs/api/

De même, il est souvent plus simple de regarder l'implémentation pour savoir comment cela fonctionne. Et donc la logique de Sun à ce sujet était "On vous donne le code source aussi." Ainsi, si tu veux vérifier ce que fait tel ou tel méthode. Tu as juste à aller regarder le source de celui-ci. Par défaut, l'ensemble des JDK sont fournit avec un src.zip qui contient l'ensemble des sources de l'API standard correspondante.

C'est sources ont beaucoup d'utilité, elles peuvent être utilisé pour visualiser l'exécution du standard en mode debug. Ou pour apprendre comment celui-ci réalise certains algorithme. (Par exemple, la conversion de la base 10 à la base 16)

Il ne t'es pas nécessaire d'aller voir les sources Java pour comprendre le sujet de ce thread. Cependant, il est possible que savoir qu'il existe une javadoc pour pratiquement toutes les API fournit en Java. Et que certains fois, aller la lire est le mieux à faire.

Cordialement,
Patrick Kolodziejczyk.

donc ce n'était pas si idiot biensur que je vais voir maintenant les doc sur oracle (eh oui pas pensé que c'est de la javadoc comme pour moi mais un tout petit peu plus fournis pas beaucoup plus :p ) par contre je n'ai pas encore pensé aller voir le code source surtout au début comme si c'était inaccessible à mon niveau et de peur de mettre le bazar ;)

c'est marrant de voir le jdk et la jre comme un un outil comme wordpress j'aurais pas pensé ya encore peu voir java comme cela

pour revenir à mon sujet je pense qu'en fait entre les termes anglais et les principes en cours et qui sont déjà implanter dans le jdk évidement vu sur :
listes (piles(tableaux, vector),
files(tableaux)
arbres( avec pile et deque)

est destabilisant mais finalement seul les fonctionnalités sont utiles et que les cours étaient là pour les comprendre

si vous me confirmez que j'ai bien résumé je marquerai résolu :)

Oui, Java est un outil. A la base Java a été crée pour pouvoir déployer du code sur différentes machines sans à avoir à tout ré-écrire à chaque fois. (En particulier, les éléments de base.) Toutes l'API standard est donc là pour ça.

Je ne pense pas que vous ayez compris.

Si on prend les notions "théorique" :

Les listes sont implémenté en Java par : Tout ce qui implémente l'interface List
Sur la page de l'interface List, il y a une partie :

Citation:

---

Envoyé par All Known Implementing Classes:

AbstractList, AbstractSequentialList, ArrayList, AttributeList, CopyOnWriteArrayList, LinkedList, RoleList, RoleUnresolvedList, Stack, Vector

---

Les files sont implémenté en Java par : Tout ce qui implémente Queue (et Deque)

Citation:

---

Envoyé par All Known Implementing Classes:

AbstractQueue, ArrayBlockingQueue, ArrayDeque, ConcurrentLinkedDeque, ConcurrentLinkedQueue, DelayQueue, LinkedBlockingDeque, LinkedBlockingQueue, LinkedList, LinkedTransferQueue, PriorityBlockingQueue, PriorityQueue, SynchronousQueue

---

Les arbres n'ont pas d'implémentation standard fournit. Il y a les JTree qui sont utilisé pour l'affichage (Swing). Il y a aussi une "implémentation" pour le JDOM (parcours de fichier XML).
De ce que j'ai pu constaté, les structures en arbres sont très lié à ce qu'ils représente. Donc chacun fait à sa sauce...

Note que point de vue structure, il te maque au moins les Map (association Clé, Valeur)

Cordialement,
Patrick Kolodziejczyk.

Source :
http://docs.oracle.com/javase/7/docs...util/List.html
http://docs.oracle.com/javase/7/docs...til/Queue.html
https://docs.oracle.com/javase/tutor...ents/tree.html

Je connais l'histoire de java un peu quand même et l'avantage de la machine virtuelle : la Jre

Ce que je voulais dire c'est que lors d'appréhender les cours pour nous expliquer le principe des listes, des piles et des files et du même coup leur implantation "naturelle" en java
On recréé des classes listes, pile, files juste avec des types primitifs et de simples tableaux puis petit à petit on nous rajoute des classes java de plus en plus.

Ce qui m'a destabilisé au début, car je voulais ré-utiliser mes classes crées sans les classes java ce qui parfois ne faisait pas fonctionner mes programmes
car mes classes (mais plutot les miennes )ou les classes java n'avaient pas les fonctionnalités (méthodes ) voulues pour faire tourner
Résultat je me mélangeais les pinceaux.

Mais maintenant je recherche juste les fonctionnalités dans les collections dont j'ai besoin en rajoutant mes méthodes si il faut

Sinon je sais oui je n'ai pas encore regardé les Map mais c'est voulu préférant bien comprendre les étapes de mes cours entre autres les arbres. De plus les cours sont terminées et j'ai des boulots sur des sites en ce moment.
Je reviendrais sur java dans tres peu de temps ;) pour bien comprendre et utiliser les arbres et aborder les map

En tout cas merci à tous de m'avoir éclaircit les choses :)