Correction TP Généricité collection
Correction TP Généricité collection
Software Engineering, Object-Oriented Programming · notes
Fiche de révisionRésumé
Rédigée à partir de ce document, puis vérifiée avant publication.
Ce document traite de la pile générique en Java, en présentant sa définition, ses méthodes et des exemples pratiques. Les étudiants apprendront à créer une pile générique à l'aide de différentes structures de données, comme les listes chaînées et les tableaux, ainsi que des exercices pour renforcer leur compréhension.
La première approche pour implémenter une pile générique en Java consiste à utiliser une représentation chaînée. Voici l'interface et la classe de base pour une pile générique :
package PileGen;
public interface PileGen<T> {
public boolean estVide();
public T dernier();
public void depiler();
public void empiler(T o);
}
La classe Noeud représente un élément de la pile :
package PileGen;
public class Noeud<T> {
T info;
Noeud<T> suivant;
}
La classe PileListe implémente l'interface PileGen :
package PileGen;
class PileListe<T> implements PileGen<T> {
private Noeud<T> sommet;
public PileListe() {
sommet = null;
}
public boolean estVide() {
return (sommet == null);
}
public T dernier() {
return sommet.info;
}
public void empiler(T o) {
Noeud<T> n = new Noeud<T>();
n.info = o;
n.suivant = sommet;
sommet = n;
}
public void depiler() {
sommet = sommet.suivant;
}
}
Pour tester la pile, on peut utiliser la classe TestPile :
package PileGen;
class TestPile {
public static void main(String[] args) {
PileListe<Integer> p = new PileListe<Integer>();
for (int i = 0; i < 10; i++)
p.empiler(new Integer(i));
while (!p.estVide()) {
System.out.println(p.dernier());
p.depiler();
}
}
}
Une autre approche pour implémenter une pile générique est d'utiliser un tableau dynamique, comme ArrayList. Voici la classe PileTab :
package PileTab;
public class PileTab {
int pos;
int[] tab;
public PileTab() {
tab = new int[4];
this.pos = 0;
}
public void add(int e) {
if (this.pos == tab.length) {
System.out.println("Ajout impossible de " + e);
} else {
tab[this.pos] = e;
this.pos++;
}
}
public int remove() {
int elem = tab[this.pos - 1];
this.pos--;
return elem;
}
public boolean estVide() {
return this.pos == 0;
}
public int size() {
return this.pos;
}
public void affiche() {
for (int i = 0; i < this.pos; i++) {
System.out.println(this.tab[i]);
}
}
public int getSommet() {
return this.tab[pos - 1];
}
}
La classe TruePileGen utilise ArrayList pour une implémentation plus flexible :
package PileTab;
import java.util.ArrayList;
import java.util.Iterator;
public class TruePileGen<T> {
ArrayList<T> tab;
public TruePileGen() {
tab = new ArrayList<T>();
}
public void add(T e) {
tab.add(e);
}
public T remove() {
T elem = this.tab.get(this.tab.size() - 1);
this.tab.remove(this.tab.size() - 1);
return elem;
}
public boolean estVide() {
return this.tab.size() == 0;
}
public int size() {
return this.tab.size();
}
public void affiche() {
Iterator<T> ite = this.tab.iterator();
while (ite.hasNext()) System.out.println(ite.next().toString());
}
public T getSommet() {
return this.tab.get(this.tab.size() - 1);
}
}
Une autre implémentation de pile générique utilise LinkedList. Voici l'interface IPile :
public interface IPile<A> {
boolean estVide();
void empile(A a);
A depile();
int nbElements();
A sommet();
}
La classe CPile implémente cette interface :
import java.util.LinkedList;
public class CPile<A> implements IPile<A> {
LinkedList<A> l;
public CPile() {
l = new LinkedList<A>();
}
public boolean estVide() {
return l.size() == 0;
}
public void empile(A a) {
l.addFirst(a);
}
public A depile() {
return l.removeFirst();
}
public int nbElements() {
return l.size();
}
public A sommet() {
return l.peek();
}
}
Pour gérer des tâches, on peut définir une interface Tache et des classes pour les tâches élémentaires et complexes :
package TacheGen;
public interface Tache {
String getNom();
int getCout();
}
La classe TacheElementaire implémente cette interface :
package TacheGen;
public class TacheElementaire implements Tache {
String nom;
int cout;
public TacheElementaire(String nom, int cout) {
this.nom = nom;
this.cout = cout;
}
public String getNom() {
return nom;
}
public int getCout() {
return cout;
}
}
La classe TacheComplexe permet de gérer plusieurs tâches :
package TacheGen;
import java.util.ArrayList;
public class TacheComplexe implements Tache {
private ArrayList<Tache> tabSousTaches;
String nom;
public TacheComplexe(String nom) {
this.nom = nom;
tabSousTaches = new ArrayList<Tache>();
}
public String getNom() {
return this.nom;
}
public void ajouter(Tache t) {
tabSousTaches.add(t);
}
public void supprimer(Tache t) {
tabSousTaches.remove(t);
}
public int getCout() {
int res = 0;
for (Tache t : tabSousTaches) {
res += t.getCout();
}
return res;
}
}
Voici les points essentiels à retenir concernant les piles génériques en Java :
empiler, depiler, estVide et dernier.Une pile générique en Java est une structure de données qui permet de stocker des éléments de n'importe quel type, en utilisant des méthodes pour ajouter, retirer et vérifier si la pile est vide.
Pour créer une pile générique en Java, on peut définir une interface avec les méthodes nécessaires, puis implémenter cette interface dans une classe en utilisant des structures de données comme les listes chaînées ou les tableaux.
Une pile chaînée utilise des nœuds liés pour stocker les éléments, ce qui permet une croissance dynamique, tandis qu'une pile par tableau utilise un tableau fixe, ce qui peut limiter la taille de la pile.
Les piles génériques offrent une flexibilité accrue en permettant de stocker des éléments de différents types sans avoir à créer plusieurs classes de piles pour chaque type d'élément.
Pour tester une pile générique, on peut créer une classe de test qui empile et dépile des éléments, tout en vérifiant que les méthodes fonctionnent comme prévu.