Précédent Remonter Suivant

Chapitre 5  Modèles et structures de données

Malgré leur appellation voisine, une "liste" et une "liste chaînée" sont des concepts très différents. Une liste est une abstraction mathématique ou un modèle de données. Une liste chaînée est une structure de données. En particulier, c'est la structure de données que nous utilisons habituellement en Pascal et dans d'autres langages similaires pour représenter les listes abstraites dans les programmes. Il existe d'autres langages pour lesquels il n'est pas nécessaire d'utiliser une structure de données pour représenter des listes abstraites. Par exemple, la liste (a1, a2, ... ,an) peut être représentée directement dans le langage Lisp, et d'une façon similaire dans le langage Prolog... Aho & Ullman [1]
Un modèle de données est une abstraction utilisée pour décrire des problèmes. Cette abstraction spécifie les valeurs qui peuvent être attribuées aux objets, et les opérations valides sur ces objets.

La structure de données, quant à elle, est une construction du langage de programmation, permettant de représenter un modèle de données.

Dans ce chapitre, nous allons illustrer la différence entre ces deux notions en parlant assez longuement de la liste (modèle de données), et des structures de données qui permettent habituellement de la représenter. Cela nous donnera aussi l'occasion d'introduire la notion d'interface, telle qu'elle est définie en Java. Nous verrons aussi plus rapidement quelques autres modèles de données classiques.

5.1  Les listes

La liste est un modèle de données qui permet de décrire une séquence d'objets contenant chacun une valeur d'un type donné. À la base, on peut définir le type L = liste de V à partir d'un type V donné, comme une suite finie d'éléments de V.

Les opérations basiques que l'on peut définir sur une telle liste sont :
vide : L ® Bool indique que la liste est vide
tete : L ® V donne la valeur de la tête de liste
succ : L ® L donne la suite de la liste
adjTete : L × V ® L ajoute une valeur en tête de liste

En plus de ces opérations de base, on peut souhaiter définir des opérations plus complexes -- qui s'expriment en termes de combinaison de ces opérations de base -- comme l'adjonction ou la suppression à un endroit quelconque, la recherche de l'existence d'une valeur dans la liste, voire l'adjonction et la suppression en queue ou le tri...

5.1.1  Représentation par un tableau

Le premier type de représentation auquel on pense est bien entendu le tableau, que nous avons déjà vu. Si nous représentons une liste par un tableau T[1 ... n], par exemple, nous pouvons réaliser les opérations de base comme suit :
vide : T[1 ... n] ® Bool
ì
í
î
vrai si    n = 0
faux sinon
tete : T[1 ... n>0] ® x Î V x = T[1]
succ : T[1 ... n>0] ® U[1 ... n-1] " i Î [1 ... n-1]    U[i] = T[i+1]
adjTete : T[1 ... n] × x Î V ® U[1 ... n+1]
ì
í
î
  U[1] = x
" i Î [2 ... n+1] U[i] = T[i-1]

5.1.2  Représentation par une liste chaînée

La liste chaînée est une structure de données que l'on retrouve fréquemment en informatique. Elle nécessite de représenter chaque élément de la liste par un couplet (val, succ), désignant respectivement la valeur au point courant et le "pointeur" sur le chaînon suivant. En Java, cela s'écrit très aisément puisque, comme nous l'avons vu, toutes les variables déclarées d'un type défini par une classe sont des références. Prenons par exemple le cas d'une liste d'entiers. La classe qui va représenter un "maillon de la chaîne" pourra s'écrire : 
public class ElementListInt {
    public int val;
    public ElementListInt succ;

    // Constructeur
    ElementListInt(int x) {
        val = x;
        succ = null;
    }
}
Nous pouvons maintenant définir la classe représentant la liste chaînée d'entiers. Vous remarquerez que je n'ai pas mis dans l'interface de cette classe les opérations tete et succ, que l'on peut effectuer directement par l'accès à tete.val et tete.succ, ces variables d'instance de ElementListInt ayant été déclarées publiques : 
public class ListInt {
    public ElementListInt tete;

    // Constructeur -- liste vide
    ListInt() {
        tete = null;
    }

    // Méthodes
    public boolean vide() { 
        return tete == null;
    }
    public void adjTete(int x) {
        // Créer le nouvel élément
        ElementListInt nouveau = new ElementListInt(x);
        // Le raccorder au reste
        nouveau.succ = tete;
        tete = nouveau;
    }
}
Notez la facilité de "chaînage" pour l'adjonction en tête : on crée le nouveau maillon, on lui attribue une valeur, et on l'accroche au reste de la chaîne.

5.1.3  Comparaison entre les deux représentations

On remarquera tout de suite que d'un point de vue pratique, l'adjonction en tête n'est pas une opération très efficace avec la représentation tableau, puisqu'elle nécessite un décalage vers la droite de toutes les valeurs du tableau. Il en serait de même de l'insertion ou de la suppression en une position quelconque.

Ces opérations sont bien plus immédiates avec la liste chaînée. En revanche, celle-ci nécessite plus de place en mémoire, puisque chaque élément de la liste requiert à la fois un emplacement mémoire pour la valeur et un autre emplacement pour le chaînage.

Il est très fréquent de devoir ainsi faire des choix entre temps de calcul et encombrement mémoire. D'autres facteurs peuvent intervenir, notamment le type et la fréquence des opérations que l'on veut effectuer. Si par exemple on a besoin de trier la liste régulièrement, la représentation par tableau présente l'avantage de permettre l'emploi d'algorithmes de tri plus efficaces. Si en revanche les opérations d'adjonction/suppression en un endroit quelconque sont fréquentes, la représentation par liste chaînée présente des avantages indéniables.

5.1.4  Application : l'interface ListeDeComptes

Il est temps de revenir à notre exemple de gestion bancaire. Nous avions décidé de représenter les comptes d'une agence bancaire par un tableau d'objets de type CompteBancaire. Mais à la réflexion, il est probablement dommage de se lier à ce type de représentation ; nous venons de voir que dans certains cas, d'autres types de représentation peuvent être plus appropriés.

Pour se détacher de la représentation, tout en garantissant un ensemble de services, nous allons recourir à un nouveau concept en Java : l'interface. De manière informelle, une interface peut être considérée comme une déclaration de classe -- on parlera en fait plutôt de signature de type -- sans comportement associé, c'est-à-dire sans code, ni variables d'instance. L'utilisation d'interfaces permet de spécifier un comportement -- on parle aussi de contrat -- que les objets d'un type donné doivent assurer, sans prendre aucune décision sur les structures de données à mettre en oeuvre pour représenter concrètement cette interface. On favorise ainsi l'abstraction de données, puisqu'on se situe au niveau du modèle de données.

Définissons donc l'interface ListeDeComptes, dont nous attendons le comportement suivant : Le mot clé interface introduit cette interface, dont la définition se met dans un fichier à part, comme pour les classes -- ici le fichier ListeDeComptes.java : 
// Interface ListeDeComptes - version 1.0

/**
 * Interface représentant une liste de comptes et les opérations
 * que l'on souhaite effectuer sur cette liste
 * @author Karl Tombre
 */

public interface ListeDeComptes {
    // Récupérer un compte à partir d'un nom donné
    public CompteBancaire trouverCompte(String nom);
    // Ajout d'un nouveau compte
    public void ajout(CompteBancaire c);
    // Suppression d'un compte connaissant le nom du client
    public void supprimer(CompteBancaire c);
    // Afficher l'état de tous les comptes
    public void afficherEtat();
    // Traitement quotidien de tous les comptes
    public void traitementQuotidien();
}
Vous noterez la syntaxe très proche de celle d'une classe, avec les deux différences fondamentales suivantes, dues au fait que nous sommes au niveau du modèle de données et non de sa représentation concrète : L'intérêt d'une telle interface, c'est qu'elle définit un type valide ; nous pouvons donc maintenant écrire notre programme de gestion bancaire en termes plus abstraits, puisque la variable monAgence peut maintenant être déclarée de type ListeDeComptes.

Cependant, une interface ne comporte aucune variable d'instance et aucun constructeur, on ne peut donc pas l'instancier. Il faut donc bien au moins une classe concrète qui implante l'interface ainsi spécifiée, si on veut disposer d'objets de ce type. Reprenons notre classe AgenceBancaire ; elle met déjà en oeuvre toutes les opérations de l'interface ListeDeComptes, sauf la suppression. Grâce au mot clé implements, nous allons déclarer que cette classe met en oeuvre l'interface : 
public class AgenceBancaire implements ListeDeComptes {
    ...
}
Mais si nous essayons de la compiler après avoir simplement ajouté cette déclaration, nous avons le message d'erreur suivant : 
javac  AgenceBancaire.java
AgenceBancaire.java:11: class AgenceBancaire must be declared abstract. 
It does not define void supprimer(CompteBancaire) from interface ListeDeComptes.
public class AgenceBancaire implements ListeDeComptes {
             ^
1 error
Que se passe-t-il ? En fait, en déclarant AgenceBancaire implements ListeDeComptes, nous nous sommes engagés à remplir le contrat exprimé par l'interface. Or nous n'avons pas pour l'instant dit comment réaliser la méthode supprimer ; le compilateur nous suggère donc de rendre la classe abstraite, supposant que nous voulons définir des sous-classes dans lesquelles cette méthode serait définie.

Il se trompe... Nous allons plutôt ajouter la méthode supprimer à la classe AgenceBancaire, dont la nouvelle version est donnée ci-après : 
// Classe AgenceBancaire - version 1.2

/**
 * Classe représentant une agence bancaire et les méthodes qui lui
 * sont associées.
 * @author Karl Tombre
 */

public class AgenceBancaire implements ListeDeComptes {
    private CompteBancaire[] tabComptes;  // le tableau des comptes
    private int capacitéCourante;         // la capacité du tableau
    private int nbComptes;                // le nombre effectif de comptes

    // Constructeur -- au moment de créer une agence, on crée un tableau
    // de capacité initiale 10, mais qui ne contient encore aucun compte
    AgenceBancaire() {
        tabComptes = new CompteBancaire[10];
        capacitéCourante = 10;
        nbComptes = 0;
    }

    // Méthode privée utilisée pour incrémenter la capacité
    private void augmenterCapacité() {
        // Incrémenter la capacité de 10
        capacitéCourante += 10;
        // Créer un nouveau tableau plus grand que l'ancien
        CompteBancaire[] tab = new CompteBancaire[capacitéCourante];
        // Recopier les comptes existants dans ce nouveau tableau
        for (int i = 0 ; i < nbComptes ; i++) {
            tab[i] = tabComptes[i];
        }
        // C'est le nouveau tableau qui devient le tableau des comptes
        // (l'ancien sera récupéré par le ramasse-miettes)
        tabComptes = tab;
    }

    // Les méthodes de l'interface
    // Ajout d'un nouveau compte
    public void ajout(CompteBancaire c) {
        if (nbComptes == capacitéCourante) { // on a atteint la capacité max
            augmenterCapacité();
        }
        // Maintenant je suis sûr que j'ai de la place
        // Ajouter le nouveau compte dans la première case vide
        // qui porte le numéro nbComptes !
        tabComptes[nbComptes] = c;
        // On prend note qu'il y a un compte de plus
        nbComptes++;
    }
    // Récupérer un compte à partir d'un nom donné
    public CompteBancaire trouverCompte(String nom) {
        boolean trouvé = false;  // rien trouvé pour l'instant
        int indice = 0;
        for (int i = 0 ; i < nbComptes ; i++) {
            if (nom.equalsIgnoreCase(tabComptes[i].nom())) {
                trouvé = true; // j'ai trouvé
                indice = i;    // mémoriser l'indice
                break;         // plus besoin de continuer la recherche
            }
        }
        if (trouvé) {
            return tabComptes[indice];
        }
        else {
            return null;  // si rien trouvé, je rend la référence nulle
        }
    }
    // Afficher l'état de tous les comptes
    public void afficherEtat() {
        // Il suffit d'afficher l'état de tous les comptes de l'agence
        for (int i = 0 ; i < nbComptes ; i++) { 
            tabComptes[i].afficherEtat();
        }
    }

    // Traitement quotidien de tous les comptes
    public void traitementQuotidien() {
        for (int i = 0 ; i < nbComptes ;i++) {
            tabComptes[i].traitementQuotidien();
        }
    }

    // Suppression d'un compte
    public void supprimer(CompteBancaire c) {
        boolean trouvé = false;  // rien trouvé pour l'instant
        int indice = 0;
        for (int i = 0 ; i < nbComptes ; i++) {
            if (tabComptes[i] == c) { // attention comparaison de références
                trouvé = true; // j'ai trouvé
                indice = i;    // mémoriser l'indice
                break;         // plus besoin de continuer la recherche
            }
        }
        if (trouvé) {
            // Décaler le reste du tableau vers la gauche
            // On "écrase" ainsi le compte à supprimer
            for (int i = indice+1 ; i < nbComptes ; i++) {
                tabComptes[i-1] = tabComptes[i];
            }
            // Mettre à jour le nombre de comptes
            nbComptes--;
        }
        else {
            // Message d'erreur si on n'a rien trouvé
            System.out.println("Je n'ai pas trouvé ce compte");
        }
    }
}
Notez bien la manière dont on "efface" le compte en décalant d'une position vers la gauche toutes les valeurs du tableau après la position du compte à supprimer. Notez aussi que nous fondons la recherche du compte à supprimer sur la comparaison des références (opérateur ==) et non sur la comparaison des contenus, ce qui nécessiterait une opération plus complexe.

Modifions maintenant notre programme de gestion bancaire de deux manières : 
// Classe Banque - version 4.2

/**
 * Classe contenant un programme de gestion bancaire, utilisant
 * un objet de type AgenceBancaire
 * @author Karl Tombre
 * @see    ListeDeComptes, CompteBancaire, Utils
 */

public class Banque {
    public static void main(String[] args) {
        ListeDeComptes monAgence = new AgenceBancaire();

        while (true) { // boucle infinie dont on sort par un break
            String monNom = Utils.lireChaine("Donnez le nom du client (rien=exit) : ");
            if (monNom.equals("")) {
                break;  // si on ne donne aucun nom on quitte la boucle
            }
            else {
                // Vérifier si le compte existe
                CompteBancaire monCompte = monAgence.trouverCompte(monNom);
                if (monCompte == null) {
                    // rien trouvé, on le crée
                    System.out.println("Ce compte n'existe pas, nous allons le créer");
                    String monAdresse = Utils.lireChaine("Adresse = ");
                    String type = 
                        Utils.lireChaine("Compte de [D]épôt (défaut) ou d'[E]pargne ? ");
                    char choixType = type.charAt(0);
                    // Créer le compte de type demandé
                    if (choixType == 'e' || choixType == 'E' || 
                        choixType == 'é' || choixType == 'É') {
                        monCompte = new CompteEpargne(monNom, monAdresse, 0.00015);
                    }
                    else {
                        monCompte = new CompteDepot(monNom, monAdresse, 0.00041);
                    }
                    // L'ajouter aux comptes de l'agence
                    monAgence.ajout(monCompte);
                }

                String choix = 
                    Utils.lireChaine("Votre choix : [D]ébit, [C]rédit, [S]upprimer ? ");
                boolean supprimer = false;  // pour savoir si on a supprimé

                // Récupérer la première lettre de la chaîne saisie
                char monChoix = choix.charAt(0);
                if (monChoix == 's' || monChoix == 'S') {
                    monAgence.supprimer(monCompte);
                    supprimer = true;
                }
                else if (monChoix == 'c' || monChoix == 'C') {
                    int montant = Utils.lireEntier("Montant à créditer = ");
                    monCompte.créditer(montant);
                }
                else if (monChoix == 'd' || monChoix == 'D') {
                    int montant = Utils.lireEntier("Montant à débiter = ");
                    monCompte.débiter(montant);
                }
                else {
                    System.out.println("Choix invalide");
                }
                if (!supprimer) {
                    // Si on n'a pas supprimé, afficher l'état du compte
                    monCompte.afficherEtat();
                }
                else {
                    // Sinon afficher l'état global de l'agence
                    System.out.println("Nouvel état des comptes de l'agence");
                    monAgence.afficherEtat();
                }
            }
        }
        // Quand on sort de la boucle, afficher l'état global de l'agence
        System.out.println("Voici le nouvel état des comptes de l'agence");
        monAgence.afficherEtat();
        System.out.println("-----------------------------------");
        System.out.println("On applique un traitement quotidien");
        System.out.println("-----------------------------------");
        monAgence.traitementQuotidien();
        monAgence.afficherEtat();
    }
}
Une trace d'exécution de ce nouveau programme montre la possibilité de supprimer un compte : 
Donnez le nom du client (rien=exit) : \emph{Karl}
Ce compte n'existe pas, nous allons le créer
Adresse = \emph{Sornéville}
Compte de [D]épôt (défaut) ou d'[E]pargne ? \emph{D}
Votre choix : [D]ébit, [C]rédit, [S]upprimer ? \emph{D}
Montant à débiter = \emph{10000}
Compte de dépôts
Compte numéro 1 ouvert au nom de Karl
Adresse du titulaire : Sornéville
Le solde actuel du compte est de -10000 euros.
************************************************
Donnez le nom du client (rien=exit) : \emph{Luigi}
Ce compte n'existe pas, nous allons le créer
Adresse = \emph{Rome}
Compte de [D]épôt (défaut) ou d'[E]pargne ? \emph{E}
Votre choix : [D]ébit, [C]rédit, [S]upprimer ? \emph{C}
Montant à créditer = \emph{100000}
Compte d'épargne
Compte numéro 2 ouvert au nom de Luigi
Adresse du titulaire : Rome
Le solde actuel du compte est de 100000 euros.
************************************************
Donnez le nom du client (rien=exit) : \emph{Jacques}
Ce compte n'existe pas, nous allons le créer
Adresse = \emph{Laxou}
Compte de [D]épôt (défaut) ou d'[E]pargne ? \emph{D}
Votre choix : [D]ébit, [C]rédit, [S]upprimer ? \emph{C}
Montant à créditer = \emph{23000}
Compte de dépôts
Compte numéro 3 ouvert au nom de Jacques
Adresse du titulaire : Laxou
Le solde actuel du compte est de 23000 euros.
************************************************
Donnez le nom du client (rien=exit) : \emph{Luigi}
Votre choix : [D]ébit, [C]rédit, [S]upprimer ? \emph{S}
Nouvel état des comptes de l'agence
Compte de dépôts
Compte numéro 1 ouvert au nom de Karl
Adresse du titulaire : Sornéville
Le solde actuel du compte est de -10000 euros.
************************************************
Compte de dépôts
Compte numéro 3 ouvert au nom de Jacques
Adresse du titulaire : Laxou
Le solde actuel du compte est de 23000 euros.
************************************************
Donnez le nom du client (rien=exit) : \emph{Luigi}
Ce compte n'existe pas, nous allons le créer
Adresse = \emph{Bari}
Compte de [D]épôt (défaut) ou d'[E]pargne ? \emph{E}
Votre choix : [D]ébit, [C]rédit, [S]upprimer ? \emph{C}
Montant à créditer = \emph{100000}
Compte d'épargne
Compte numéro 4 ouvert au nom de Luigi
Adresse du titulaire : Bari
Le solde actuel du compte est de 100000 euros.
************************************************
Donnez le nom du client (rien=exit) : 
Voici le nouvel état des comptes de l'agence
Compte de dépôts
Compte numéro 1 ouvert au nom de Karl
Adresse du titulaire : Sornéville
Le solde actuel du compte est de -10000 euros.
************************************************
Compte de dépôts
Compte numéro 3 ouvert au nom de Jacques
Adresse du titulaire : Laxou
Le solde actuel du compte est de 23000 euros.
************************************************
Compte d'épargne
Compte numéro 4 ouvert au nom de Luigi
Adresse du titulaire : Bari
Le solde actuel du compte est de 100000 euros.
************************************************
-----------------------------------
On applique un traitement quotidien
-----------------------------------
Compte de dépôts
Compte numéro 1 ouvert au nom de Karl
Adresse du titulaire : Sornéville
Le solde actuel du compte est de -10004 euros.
************************************************
Compte de dépôts
Compte numéro 3 ouvert au nom de Jacques
Adresse du titulaire : Laxou
Le solde actuel du compte est de 23000 euros.
************************************************
Compte d'épargne
Compte numéro 4 ouvert au nom de Luigi
Adresse du titulaire : Bari
Le solde actuel du compte est de 100014 euros.
************************************************
Nous allons maintenant illustrer l'intérêt d'avoir utilisé une interface, en définissant une autre classe qui met également en oeuvre l'interface ListeDeComptes, mais cette fois-ci au moyen d'une liste chaînée1.

Définissons tout d'abord la classe ChainonCompte, qui définit un "maillon" de la chaîne, sur le modèle de ce que nous avons fait pour ElementListInt : 
public class ChainonCompte {
    public CompteBancaire val;
    public ChainonCompte succ;

    // Constructeur à partir d'un compte bancaire
    ChainonCompte(CompteBancaire c) {
        val = c;
        succ = null;
    }
}
La classe qui met en oeuvre l'interface ListeDeComptes s'écrit ensuite assez aisément : 
// Classe AgenceBancaireBis - version 1.0

/**
 * Classe représentant une agence bancaire et les méthodes qui lui
 * sont associées, au moyen d'une liste chaînée
 * @author Karl Tombre
 */

public class AgenceBancaireBis implements ListeDeComptes {
    private ChainonCompte tete;           // la tête de liste

    // Constructeur -- au moment de créer une agence, on crée une liste vide
    AgenceBancaireBis() {
        tete = null;
    }

    // Les méthodes de l'interface
    // Ajout d'un nouveau compte
    public void ajout(CompteBancaire c) {
        // On va l'ajouter en tête, c'est le plus facile
        ChainonCompte n = new ChainonCompte(c);
        n.succ = tete;
        tete = n;
    }
    // Récupérer un compte à partir d'un nom donné
    public CompteBancaire trouverCompte(String nom) {
        ChainonCompte courant = tete;  // chaînon courant
        while ((courant != null) && (!nom.equalsIgnoreCase(courant.val.nom()))) {
            courant = courant.succ;  // aller au suivant
        }
        if (courant !=  null) { // on en a trouvé un
            return courant.val;
        }
        else {
            return null;  // si rien trouvé, je rend la référence nulle
        }
    }
    // Afficher l'état de tous les comptes
    public void afficherEtat() {
        // Il suffit d'afficher l'état de tous les comptes de l'agence
        ChainonCompte courant = tete;
        while (courant != null) {
            courant.val.afficherEtat();
            courant = courant.succ;
        }
    }

    // Traitement quotidien de tous les comptes
    public void traitementQuotidien() {
        ChainonCompte courant = tete;
        while (courant != null) {
            courant.val.traitementQuotidien();
            courant = courant.succ;
        }
    }

    // Suppression d'un compte
    public void supprimer(CompteBancaire c) {
        if ((tete != null) && (tete.val == c)) {
            // Cas particulier de la suppression en tête
            tete = tete.succ;
        }
        else {
            ChainonCompte courant = tete;  // chaînon courant
            ChainonCompte prev = null;     // celui qui précède le courant
            while ((courant != null) && (courant.val != c)) {
                prev = courant;  // mémoriser le chaînon d'où un vient
                courant = courant.succ;  // aller au suivant
            }
            if (courant != null) {
                // Si on a trouvé quelque chose
                prev.succ = courant.succ;   // on le court-circuite
            }
            else {
                // Message d'erreur si on n'a rien trouvé
                System.out.println("Je n'ai pas trouvé ce compte");
            }
        }
    }
}
NB : je vous conseille d'étudier attentivement la manière dont sont effectuées des opérations telles que la recherche ou la suppression. Elles sont caractéristiques des opérations sur les listes chaînées.

Le moment "magique" approche... Nous revenons maintenant au programme de gestion bancaire, et nous nous contentons de modifier la classe instanciée pour créer l'objet référencé par la variable monAgence : 
ListeDeComptes monAgence = new AgenceBancaireBis();
Et le programme fonctionne de la même manière, bien que la représentation interne des données soit tout à fait différente ! Nous voyons bien que nous avons gagné un niveau d'abstraction en utilisant l'interface au lieu d'utiliser directement la classe...

Mais avons-nous vraiment le même fonctionnement ? En fait, l'opération d'affichage des états nous donne les comptes dans l'ordre inverse de celui donné avec une instance de AgenceBancaire. Cela est dû au fait que l'adjonction d'un nouveau compte se fait en tête de liste dans la classe AgenceBancaireBis, alors qu'elle se fait en queue du tableau dans AgenceBancaire. Voici les dernières lignes de la trace d'exécution de la nouvelle version du programme : 
-----------------------------------
On applique un traitement quotidien
-----------------------------------
Compte de dépôts
Compte numéro 4 ouvert au nom de Luigi
Adresse du titulaire : Bari
Le solde actuel du compte est de 98765 euros.
************************************************
Compte d'épargne
Compte numéro 3 ouvert au nom de Jacques
Adresse du titulaire : Laxou
Le solde actuel du compte est de 123 euros.
************************************************
Compte de dépôts
Compte numéro 1 ouvert au nom de Karl
Adresse du titulaire : Sornéville
Le solde actuel du compte est de -12350 euros.
************************************************

5.2  Les piles

Une pile est une liste particulière, sur laquelle on ne permet l'adjonction et la suppression qu'en tête. Ainsi, c'est toujours le dernier ajouté qui sera le premier sorti (on parle parfois de LIFO : Last In First Out).

Les opérations de la pile sont souvent appelées empiler et dépiler, ou en anglais push et pop.

Ce modèle de données trouve beaucoup d'applications pratiques quand il s'agit par exemple de mémoriser des contextes en programmation structurée (notion de pile des appels) ou des opérandes en attente d'opérateur, etc. En particulier, le calcul arithmétique avec notation suffixée (dite aussi polonaise inversée) se gère aisément au moyen d'une pile.

On peut bien entendu représenter une pile avec toutes les structures de données qui permettent de représenter des listes ou des tableaux. Nous donnons ci-après une esquisse d'une classe PileEntiers permettant d'empiler et de dépiler des entiers. Nous avons choisi une représentation par un tableau surdimensionné, mais vous savez maintenant comment le transformer en un tableau extensible... Nous utilisons aussi un traitement d'exception pour le cas où on essaie de dépiler d'une pile déjà vide. Nous reviendrons plus tard sur cette notion d'exceptions et nous reprendrons cet exemple en le détaillant plus (§ 6.4.2). 
import java.util.*;

public class PileEntiers {
    private int[] tab;
    private int premierLibre;

    // Constructeur
    PileEntiers() {
        tab = new int[1000];   // surdimensionné
        premierLibre = 0;
    }

    public boolean pileVide() {
        return (premierLibre == 0);
    }
    public void empiler(int x) {
        tab[premierLibre] = x; 
        ++premierLibre; 
    }
    public int depiler() throws EmptyStackException {
        if (! pileVide()) {
            --premierLibre; 
            return tab[premierLibre]; 
        }
        else {
            throw new EmptyStackException();
        }
    }
}

5.3  Les arbres

Si la liste permet de représenter une séquence d'éléments, l'arbre offre des moyens d'organisation plus puissants. Chaque noeud d'un arbre "contient" une valeur, et "pointe" sur les fils du noeud. L'arbre binaire est l'archétype des arbres ; chaque noeud a deux fils, et c'est un modèle de données qui permet en particulier de représenter les ensembles de manière efficace. Nous y reviendrons au § 6.5.1 ; contentons-nous pour l'instant de donner la classe qui représente les noeuds des arbres binaires d'entiers : 
public class NoeudArbre {
    public int val;
    public NoeudArbre filsGauche;
    public NoeudArbre filsDroit;

    // Constructeur
    NoeudArbre(int x) {
        val = x;
        filsGauche = null;
        filsDroit = null;
    }
}
1
De même que pour le tableau extensible, un vrai programmeur Java préférerait recourir directement à la classe LinkedList, disponible dans la bibliothèque de base Java, et qui met en oeuvre une liste chaînée générique. Mais une fois de plus, il nous semble utile d'avoir fait soi-même ce genre de manipulation au moins une fois...
Précédent Remonter Suivant