Séance 1 — ADT et interfaces Java

Listes, piles, files et deques : un contrat, plusieurs réalisations

Séance 1 de Structures de données et algorithmes avancés : listes, piles, files et deques : un contrat, plusieurs réalisations.

Auteur

Dr. El Hadji Bassirou TOURÉ · DMI/FST/UCAD

Navigation conceptuelle

Amont. Java orienté objet (classes, interfaces, génériques) et l’environnement de travail du TP-1 (Docker, Gradle, JUnit).

Aval. La Séance 2 démontre les coûts annoncés ici (\(\mathcal{O}\), \(\Omega\), \(\Theta\)) ; la Séance 3 range les paires d’une table de hachage dans des nœuds chaînés, la Séance 4 range le tas binaire dans un tableau qui double, et la Séance 5 parcourt les graphes avec la file ArrayDeque du JDK.

Objectifs

Distinguer un type abstrait de données (ADT) d’une structure de données, et l’écrire en interface Java générique.
Réaliser l’ADT List par un tableau redimensionnable et par des nœuds chaînés, et compter les décalages, les copies et les références suivies de chaque opération.
Établir le coût amorti du doublement : moins de 2 copies par ajout, sur toute suite d’ajouts.
Parcourir une liste par un itérateur (Iterable, Iterator, boucle for-each).
Vérifier un parenthésage et évaluer une expression postfixe à l’aide d’une pile.
Réaliser une file et un deque sur un tableau circulaire, sans aucun décalage.
Choisir l’ADT d’après le besoin, puis la structure d’après les opérations fréquentes.

Tous les programmes de ce document sont en Java 17 ; ils ont été compilés par javac --release 17 -Xlint:all, sans avertissement, et exécutés avec OpenJDK 21 sur Linux x86_64 ; chaque sortie reproduite est celle de cette exécution. Les classes du cours sont les interfaces Liste, Pile, File et Deque, et leurs réalisations ListeTableau, ListeChainee, PileTableau, FileCirculaire et ArrayDeque ; leurs compteurs publics (copies, decalages, parcourus) servent à observer ce que coûte chaque opération.

Le contrat : type abstrait de données

Un programme qui manipule une structure de données finit souvent par dépendre de la manière dont elle est construite : il parcourt le tableau lui-même, il lit le champ taille, il suppose que l’élément de rang 0 est en case 0. Le jour où ce tableau doit devenir une liste chaînée, parce que les insertions en tête sont devenues fréquentes, il faut reprendre chaque ligne du code client. Le cours commence donc par le geste qui évite cette dépendance : séparer ce qu’une structure promet de la manière dont elle tient sa promesse. Tout le reste du cours repose sur ce geste : pour les tables de hachage, les arbres ou les graphes, la question sera toujours de savoir quel contrat est demandé, et quelle réalisation le tient au meilleur coût.

Au point Wave de Colobane, chacun sait comment fonctionne la file d’attente : le premier arrivé est servi le premier, et un nouveau client se place à la fin. Personne n’a besoin de savoir si les clients attendent debout dans un couloir, assis sur des chaises numérotées ou inscrits sur un cahier : la règle permet de se servir de la file sans connaître sa disposition. Un type abstrait de données est exactement cela.

Type abstrait de données et structure de données

Un type abstrait de données (ADT, abstract data type) est un ensemble de valeurs muni d’opérations, spécifiées par leur comportement : ce qu’elles produisent et ce qu’elles modifient, non la manière dont elles sont programmées. Une structure de données est une réalisation concrète d’un ADT : une disposition des éléments en mémoire, et les algorithmes qui réalisent chaque opération du contrat.

Un même ADT admet plusieurs structures de données. Le contrat ne change pas, mais le coût des opérations change beaucoup d’une structure à l’autre : c’est la matière de ce cours. La figure suivante montre les deux réalisations de l’ADT List étudiées dans cette séance.

En Java : l’interface générique

Java exprime le contrat par une interface : une liste d’en-têtes de méthodes, sans aucun corps. Le paramètre de type <T>, un générique, rend le contrat indépendant du type des éléments : il se fixe à l’usage, Liste<String> pour des noms, Liste<Integer> pour des montants. Les commentaires font partie du contrat : ils disent ce que produit chaque opération.

public interface Liste<T> extends Iterable<T> {
    void ajouter(T x);         // en fin
    void ajouter(int i, T x);  // au rang i
    T get(int i);              // l'element de rang i
    T supprimer(int i);        // retire le rang i
    int taille();
    boolean estVide();
}

La déclaration extends Iterable<T> ajoute au contrat la méthode iterator(), qui permet le parcours par la boucle for-each (section 3.3). Le client suivant n’utilise que l’interface : la méthode inscrire reçoit une Liste<String>, sans savoir laquelle des deux réalisations lui est passée, et les deux appels produisent la même sortie.

static void inscrire(Liste<String> l) {
    l.ajouter("Dior");     // en fin
    l.ajouter(0, "Kine");  // au rang 0
    System.out.println(l.get(0) + " " + l.get(1) + " " + l.taille());
}
// dans main :
inscrire(new ListeTableau<>());
inscrire(new ListeChainee<>());

Sortie \(\rightarrow\)

Kine Dior 2
Kine Dior 2

Le compilateur vérifie le contrat à la place du programmeur. Une Liste<String> rend des String sans conversion, et toute tentative d’y ranger autre chose est refusée avant l’exécution :

public class ExErreur {
    public static void main(String[] args) {
        Liste<String> noms = new ListeTableau<>();
        noms.ajouter("Daba");
        String x = noms.get(0);  // aucun cast : le type est connu
        noms.ajouter(42);        // refuse par le compilateur
        System.out.println(x);
    }
}

Compilation \(\rightarrow\)

ExErreur.java:6: error: incompatible types: int cannot be converted to String
        noms.ajouter(42);        // refuse par le compilateur
                     ^
1 error

Une confusion fréquente

ArrayList et LinkedList ne sont pas deux ADT : ce sont deux réalisations du même ADT, décrit par l’interface java.util.List. Dire « j’utilise une ArrayList » annonce un choix technique ; dire « j’ai besoin d’une liste » annonce un besoin. On déclare le besoin (List<String> noms) et l’on ne nomme la classe qu’à la création de l’objet (new ArrayList<>()) : changer de réalisation ne touche alors qu’une ligne (Bloch, Effective Java, item 64).

Le critère qui sépare le contrat de l’implémentation est l’observation : une clause du contrat se constate par les opérations publiques (dequeue() rend l’élément entré le premier), une clause d’implémentation ne se constate pas (les éléments sont rangés dans un tableau de 8 cases). Une seule chose échappe à ce critère : le temps. Le doublement d’un tableau ne se voit par aucune opération, mais il se remarque par la durée de certains ajouts ; le coût n’est pas dans le contrat, et c’est pourquoi il faut l’analyser (Séance 2).

List sur un tableau contigu

La première réalisation range les éléments dans des cases consécutives d’un tableau : l’élément de rang \(i\) est en case \(i\). L’adresse d’une case se calcule (base du tableau \(+\;i\times\) taille d’une case), et get(i) y accède en un pas, quel que soit \(i\). En Java, un tableau d’objets contient des références : chaque case désigne un objet rangé ailleurs en mémoire. La classe ListeTableau garde deux champs :

private Object[] donnees;  // cases 0 a taille - 1
private int taille;        // nombre d'elements

Le tableau est de type Object[], parce que Java ne sait pas créer un tableau de type générique T[] ; la conversion (T) se fait à la lecture, et l’annotation @SuppressWarnings("unchecked") indique au compilateur que cette conversion est voulue (le contrat garantit que seules des valeurs de type T y sont rangées). Les cases \(\texttt{taille}\) à \(\texttt{donnees.length}-1\) sont libres : la capacité du tableau dépasse en général le nombre d’éléments.

@SuppressWarnings("unchecked")
public T get(int i) {
    verifier(i, taille);
    return (T) donnees[i];  // acces direct
}

public void ajouter(T x) {
    ajouter(taille, x);     // en fin
}

public void ajouter(int i, T x) {
    verifier(i, taille + 1);
    if (taille == donnees.length) agrandir();
    for (int k = taille; k > i; k--) {
        donnees[k] = donnees[k - 1];
        decalages++;
    }
    donnees[i] = x;
    taille++;
}

Insérer au rang \(i\) oblige à libérer la case \(i\) : les éléments des rangs \(i\) à \(\texttt{taille}-1\) reculent d’une case, en commençant par le dernier, pour ne rien écraser. Ces décalages sont au nombre de \(\texttt{taille}-i\) : aucun pour un ajout en fin, \(\texttt{taille}\) pour un ajout en tête. Quand le tableau est plein, agrandir() est appelé d’abord.

Exemple pas à pas : deux insertions et un agrandissement

Le programme suivant reprend ajouter(i, x) sur un tableau de 4 cases qui contient Yacine, Adama et Fallou (taille \(=3\)), avec un tableau de String au lieu de Object. La première insertion trouve une case libre ; la seconde trouve le tableau plein.

static void ajouter(int i, String x) {
    if (taille == donnees.length) agrandir();
    for (int k = taille; k > i; k--) {
        donnees[k] = donnees[k - 1];
    }
    donnees[i] = x;
    taille++;
}
// dans main :
ajouter(1, "Oumou");
ajouter(0, "Malick");
System.out.println(Arrays.toString(donnees));

Étape	Lignes	Instruction	Effet	Écrit
1	2, 10	`ajouter(1, "Oumou") ; taille == donnees.length ?`	`ajouter(1, "Oumou")` sur la liste Yacine, Adama, Fallou : `taille` \(=3\), capacité 4, la case 3 est libre ; pas d’agrandissement.
2	3–4	`k = 3 : donnees[3] = donnees[2]`	\(k=3\) : `donnees[3] = donnees[2]` ; Fallou passe de la case 2 à la case 3.
3	3–4	`k = 2 : donnees[2] = donnees[1]`	\(k=2\) : `donnees[2] = donnees[1]` ; Adama passe de la case 1 à la case 2.
4	3, 6–7	`donnees[1] = "Oumou" ; taille++`	\(k=1\) : la boucle s’arrête ; Oumou est écrit en case 1 et `taille` passe à 4 : le tableau est plein. Deux décalages.
5	2, 11	`ajouter(0, "Malick") ; agrandir() : 4 copies`	`ajouter(0, "Malick")` : `taille` \(=\) `donnees.length` \(=4\) : `agrandir()` alloue 8 cases et y recopie les 4 éléments.
6	3–4	`k = 4 : donnees[4] = donnees[3]`	\(k=4\) : Fallou passe de la case 3 à la case 4.
7	3–4	`k = 3 : donnees[3] = donnees[2]`	\(k=3\) : Adama passe de la case 2 à la case 3.
8	3–4	`k = 2 : donnees[2] = donnees[1]`	\(k=2\) : Oumou passe de la case 1 à la case 2.
9	3–4	`k = 1 : donnees[1] = donnees[0]`	\(k=1\) : Yacine passe de la case 0 à la case 1.
10	3, 6–7	`donnees[0] = "Malick" ; taille++`	\(k=0\) : la boucle s’arrête ; Malick est écrit en case 0, `taille` \(=5\). Quatre décalages pour une insertion en tête.
11	12	`println(Arrays.toString(donnees))`	Deux insertions : 6 décalages et 4 copies. Insérer au rang \(i\) décale les \(\texttt{taille}-i\) éléments qui suivent.	`[Malick, Yacine, Oumou, Adama, Fallou, null, null, null]`

Les états ci-dessous sont ceux des étapes 2, 5 et 10. À l’étape 2, Fallou vient d’être recopié de la case 2 vers la case 3 (case lue en orange, case écrite en rouge) : la case 2 contient encore Fallou, elle sera écrasée par Adama à l’étape suivante. À l’étape 5, agrandir() a recopié les 4 éléments dans un tableau de 8 cases ; à l’étape 10, Malick est écrit en case 0, libérée par le quatrième décalage.

Étape 2 : un décalage

Étape 5 : agrandir()

Étape 10 : Malick en case 0

Sortie \(\rightarrow\)

[Malick, Yacine, Oumou, Adama, Fallou, null, null, null]

Agrandir et supprimer

private void agrandir() {
    Object[] neuf = new Object[2 * donnees.length];
    for (int k = 0; k < taille; k++) {
        neuf[k] = donnees[k];  // recopie complete
        copies++;
    }
    donnees = neuf;
    agrandissements++;
}

@SuppressWarnings("unchecked")
public T supprimer(int i) {
    verifier(i, taille);
    T x = (T) donnees[i];
    for (int k = i; k < taille - 1; k++) {
        donnees[k] = donnees[k + 1];
        decalages++;
    }
    taille--;
    donnees[taille] = null;  // case liberee
    return x;
}

agrandir() alloue un tableau deux fois plus grand et y recopie les taille éléments : l’ajout qui le déclenche coûte taille copies. supprimer(i) fait le mouvement inverse de l’insertion : les éléments qui suivent le rang \(i\) avancent d’une case, et la dernière case occupée est remise à null. Sans cette écriture, le tableau garderait une référence vers un objet retiré de la liste, et le ramasse-miettes ne pourrait pas le récupérer.

Le coût amorti du doublement

Un ajout en fin coûte soit une écriture, soit, quand le tableau est plein, une écriture et la copie de tout le tableau. Le programme suivant mesure les copies faites par \(n\) ajouts successifs dans une ListeTableau de capacité 4, et le plus grand nombre de copies déclenchées par un seul ajout (pire).

ListeTableau<Integer> t = new ListeTableau<>();  // capacite 4
long pire = 0;                                   // copies d'un seul ajout
for (int n = 1; n <= (1 << 20) + 1; n++) {
    long avant = t.copies;
    t.ajouter(n);
    pire = Math.max(pire, t.copies - avant);
    if (n == 1024 || n == 1025 || n == 1 << 20 || n == (1 << 20) + 1) {
        System.out.printf(Locale.ROOT, "%7d ajouts : %2d agrandissements, "
            + "%7d copies (%.3f par ajout), pire %7d%n",
            n, t.agrandissements, t.copies, (double) t.copies / n, pire);
    }
}

Sortie \(\rightarrow\)

   1024 ajouts :  8 agrandissements,    1020 copies (0.996 par ajout), pire     512
   1025 ajouts :  9 agrandissements,    2044 copies (1.994 par ajout), pire    1024
1048576 ajouts : 18 agrandissements, 1048572 copies (1.000 par ajout), pire  524288
1048577 ajouts : 19 agrandissements, 2097148 copies (2.000 par ajout), pire 1048576

Juste avant un agrandissement, après 1 024 ajouts, les copies totalisent 1 020, moins d’une par ajout ; un ajout plus tard, le tableau de 1 024 cases est recopié, et le total passe à 2 044, soit \(2n-6\) pour \(n=1\,025\). Avec \(2^{20}+1\) ajouts, la valeur affichée 2,000 est un arrondi : \(2\,097\,148/1\,048\,577\approx1{,}999\,994\). Un seul ajout peut coûter \(n-1\) copies, mais la moyenne sur toute la suite reste sous 2.

Coût amorti

Le coût amorti d’une opération est le coût total d’une suite de \(n\) opérations, divisé par \(n\), dans le pire cas sur toutes les suites possibles (CLRS, § 16.4 ; Sedgewick et Wayne, § 1.4). Il ne fait pas d’hypothèse sur les données : c’est une moyenne sur la suite, pas sur des tirages au hasard.

La borne se démontre en sommant les copies. Après \(n\geq5\) ajouts, la capacité est passée par \(4, 8, \dots, 2^{j}\), où \(2^j\) est la plus petite puissance de 2 au moins égale à \(n\), si bien que \(2^{j-1}<n\), c’est-à-dire \(2^{j-1}\leq n-1\). Chaque agrandissement recopie tout l’ancien tableau, donc \[\text{copies} \;=\; 4+8+\dots+2^{j-1} \;=\; 2^{j}-4 \;\leq\; 2(n-1)-4 \;=\; 2n-6 ,\] avec égalité juste après chaque agrandissement (\(n=5, 9, 17, \dots, 1\,025\)). Les copies d’un ajout ne dépassent jamais 2 en moyenne, et les écritures des éléments eux-mêmes ajoutent 1 par ajout : au plus 3 écritures par ajout. La figure suivante montre le rapport copies\(/n\) pour chaque \(n\) de 4 à 8 192 : une dent de scie qui remonte presque à 2 juste après chaque doublement, puis redescend vers 1.

Le facteur 2 n’est pas indispensable : tout facteur \(r>1\) donne une suite géométrique et un coût amorti constant, de l’ordre de \(r/(r-1)\) copies par ajout. java.util.ArrayList agrandit de moitié (oldCapacity >> 1 dans le code source d’OpenJDK 17, soit \(r=1{,}5\) et au plus 3 copies par ajout), avec moins de cases vides. Ajouter un nombre fixe \(c\) de cases ne convient pas : les agrandissements arrivent tous les \(c\) ajouts et recopient \(c, 2c, 3c, \dots\) éléments, soit environ \(n^2/(2c)\) copies au total, et un coût par ajout qui croît avec \(n\).

List sur des nœuds chaînés

La seconde réalisation abandonne la contiguïté. Chaque élément est rangé dans un nœud, un petit objet qui contient la valeur et une référence vers le nœud suivant ; le dernier nœud a pour suivant null. Les nœuds sont dispersés en mémoire, et seul l’enchaînement des références donne l’ordre des éléments. La classe ListeChainee garde la référence du premier nœud (tete) et celle du dernier (queue).

private static class Noeud<T> {
    T valeur;
    Noeud<T> suivant;    // null : dernier noeud

    Noeud(T valeur, Noeud<T> suivant) {
        this.valeur = valeur;
        this.suivant = suivant;
    }
}

private Noeud<T> tete;   // null si vide
private Noeud<T> queue;  // dernier noeud
private int taille;

private Noeud<T> noeud(int i) {
    Noeud<T> x = tete;
    for (int k = 0; k < i; k++) {
        x = x.suivant;  // i references suivies
        parcourus++;
    }
    return x;
}

public T get(int i) {
    verifier(i, taille);
    return noeud(i).valeur;
}

La classe Noeud est imbriquée et statique : elle n’est visible que de ListeChainee et ne garde aucune référence vers la liste qui la contient. Atteindre le rang \(i\) oblige à partir de la tête et à suivre \(i\) références : get(i) coûte un nombre de pas proportionnel à \(i\), ce que compte le champ parcourus.

Insérer et supprimer

public void ajouter(int i, T x) {
    verifier(i, taille + 1);
    if (i == 0) {
        tete = new Noeud<>(x, tete);
        if (queue == null) queue = tete;
    } else if (i == taille) {
        queue.suivant = new Noeud<>(x, null);
        queue = queue.suivant;
    } else {
        Noeud<T> prec = noeud(i - 1);
        prec.suivant = new Noeud<>(x, prec.suivant);
    }
    taille++;
}

L’insertion distingue trois cas. En tête, le nouveau nœud reçoit l’ancienne tête comme suivant, puis devient la tête : deux références écrites, sans parcours. En fin, la référence queue donne le dernier nœud sans parcours. Au rang \(i\), il faut atteindre le nœud de rang \(i-1\) en suivant \(i-1\) références, puis le rebrancher : le nouveau nœud reçoit l’ancien suivant de prec, et prec désigne le nouveau nœud. L’ordre de ces deux écritures compte : écrire d’abord prec.suivant ferait perdre la référence de la suite de la liste. La suppression contourne le nœud retiré :

public T supprimer(int i) {
    verifier(i, taille);
    Noeud<T> retire;
    if (i == 0) {
        retire = tete;
        tete = tete.suivant;
    } else {
        Noeud<T> prec = noeud(i - 1);
        retire = prec.suivant;
        prec.suivant = retire.suivant;  // le noeud est contourne
        if (retire == queue) queue = prec;
    }
    if (tete == null) queue = null;
    taille--;
    return retire.valeur;
}

Exemple pas à pas : une insertion en tête, une insertion au rang 2

Le programme suivant reprend l’insertion avec des nœuds de String, sur la chaîne Sidy, Soda, Gora ; cette version réduite ne gère pas la référence queue.

static void ajouter(int i, String x) {
    if (i == 0) {
        tete = new Noeud(x, tete);
        return;
    }
    Noeud prec = tete;
    for (int k = 1; k < i; k++) {
        prec = prec.suivant;
    }
    prec.suivant = new Noeud(x, prec.suivant);
}
// dans main :
ajouter(0, "Mame");
ajouter(2, "Lat");
System.out.println(tete.suivant.suivant.valeur);

Étape	Lignes	Instruction	Effet	Écrit
1	2, 13	`ajouter(0, "Mame") ; i == 0 ?`	Sidy, Soda, Gora (nœuds de `String`, sans référence `queue`) : \(i=0\), insertion en tête.
2	3–4	`tete = new Noeud("Mame", tete)`	Le nœud reçoit l’ancienne tête comme suivant, puis `tete` le désigne.
3	2, 6, 14	`ajouter(2, "Lat") ; prec = tete`	`ajouter(2, "Lat")` : \(i\neq0\) ; `prec` part de la tête, Mame, au rang 0.
4	7–8	`k = 1 : prec = prec.suivant`	\(k=1\) : `prec` suit une référence et atteint Sidy, au rang 1.
5	7	`k = 2 : k < i ?`	\(k=2\) : \(2<2\) est faux : `prec` est le nœud de rang \(i-1=1\).
6	10	`prec.suivant = new Noeud("Lat", prec.suivant)`	Lat reçoit Soda comme suivant, puis `prec.suivant` désigne Lat.
7	15	`println(tete.suivant.suivant.valeur)`	`tete.suivant.suivant` suit deux références et atteint Lat, au rang 2 ; l’insertion au rang 2 n’en a suivi qu’une (\(i-1\)).	`Lat`

À l’étape 2, le nouveau nœud Mame et la référence tete sont en rouge : aucun autre nœud n’a été touché. À l’étape 6, deux références ont été écrites : celle de Lat vers Soda, puis celle de Sidy vers Lat. Le nœud Soda n’a pas bougé ; la figure place Lat entre Sidy et Soda parce qu’elle suit l’ordre des références.

Étape 2 : insertion en tête

Étape 6 : Lat au rang 2

Sortie \(\rightarrow\)

Lat

Parcourir une liste : `Iterable` et `Iterator`

Une boucle for (int k = 0; k < l.taille(); k++) qui appelle l.get(k) sur une liste chaînée repart de la tête à chaque tour : \(0+1+\dots+(n-1)=n(n-1)/2\) références suivies pour un parcours. Un itérateur garde au contraire sa position entre deux appels. L’interface java.lang.Iterable<T> demande une seule méthode, iterator(), qui rend un objet java.util.Iterator<T> muni de hasNext() et de next() ; la boucle for-each est traduite par le compilateur en appels de ces méthodes.

public Iterator<T> iterator() {
    return new Iterator<T>() {
        private Noeud<T> courant = tete;

        public boolean hasNext() {
            return courant != null;
        }

        public T next() {
            if (courant == null) {
                throw new NoSuchElementException();
            }
            T x = courant.valeur;
            courant = courant.suivant;
            return x;
        }
    };
}

Liste<String> l = new ListeChainee<>();
l.ajouter("Daba");
l.ajouter("Mbene");
l.ajouter("Kine");
for (String s : l) {
    System.out.print(s + " ");
}
System.out.println();
Iterator<String> it = l.iterator();  // le for-each
while (it.hasNext()) {
    System.out.print(it.next().length() + " ");
}
System.out.println();

Sortie \(\rightarrow\)

Daba Mbene Kine 
4 5 4

L’itérateur est une classe anonyme qui garde le nœud courant : chaque appel de next() rend sa valeur et avance d’une référence, et un parcours complet suit \(n\) références. Les deux boucles du programme sont équivalentes : la seconde écrit à la main ce que le compilateur produit pour la première. ListeTableau réalise aussi Iterable avec un indice i à la place du nœud.

Les deux réalisations mesurées

Le programme suivant fait \(n\) insertions en tête, puis lit chaque rang par get(k), sur les deux réalisations.

for (int n : new int[] {1000, 4000}) {
    ListeTableau<Integer> t = new ListeTableau<>();
    ListeChainee<Integer> c = new ListeChainee<>();
    for (int k = 0; k < n; k++) {
        t.ajouter(0, k);  // insertion en tete
        c.ajouter(0, k);
    }
    for (int k = 0; k < n; k++) {
        t.get(k);         // chaque rang
        c.get(k);
    }
    System.out.println(n + " : tableau " + t.decalages + " decalages, "
        + t.copies + " copies ; chainee " + c.parcourus + " references");
}

Sortie \(\rightarrow\)

1000 : tableau 499500 decalages, 1020 copies ; chainee 499500 references
4000 : tableau 7998000 decalages, 4092 copies ; chainee 7998000 references

Les deux réalisations ont des coûts opposés. L’insertion en tête décale tout le tableau : \(0+1+\dots+(n-1)=n(n-1)/2\) décalages, soit 499 500 pour \(n=1\,000\), et 16 fois plus pour un \(n\) 4 fois plus grand ; la liste chaînée n’en fait aucun. La lecture de chaque rang suit \(n(n-1)/2\) références dans la liste chaînée, et aucune dans le tableau. Les copies des agrandissements restent sous \(2n\) (1 020 pour \(n=1\,000\), 4 092 pour \(n=4\,000\)).

opération	tableau redimensionnable	nœuds chaînés
`get(i)`	1 accès	\(i\) références suivies
`ajouter(x)`, en fin	1 écriture, moins de 2 copies amorties	2 références écrites (grâce à `queue`)
`ajouter(0, x)`, en tête	\(n\) décalages	2 références écrites
`supprimer(0)`	\(n-1\) décalages	1 référence écrite
mémoire	\(n\) à \(2n\) cases (ajouts seuls)	\(n\) nœuds : valeur et référence

Ce que coûte un nœud

La liste chaînée n’est pas gratuite en mémoire : chaque nœud est un objet, avec son en-tête, sa référence vers la valeur et sa référence vers le suivant. Le tableau redimensionnable ne range qu’une référence par case, mais garde jusqu’à la moitié de ses cases vides juste après un doublement. Ni l’un ni l’autre n’est meilleur dans l’absolu : le choix dépend des opérations fréquentes.

Stack : le dernier arrivé sort le premier

Une pile obéit à une seule règle : le dernier élément empilé est le premier dépilé (LIFO, last in, first out). À la mairie de Rufisque, le dernier dossier posé sur la pile est le premier traité. Aucune opération n’atteint le milieu de la pile : cette pauvreté du contrat est une force, car elle autorise une réalisation où chaque opération coûte un pas.

public interface Pile<T> {
    void push(T x);  // empile
    T pop();         // depile le sommet
    T peek();        // lit le sommet
    boolean estVide();
    int taille();
}

private Object[] donnees = new Object[16];
private int taille = 0;

public void push(T x) {
    if (taille == donnees.length) agrandir();
    donnees[taille] = x;  // au sommet
    taille++;
}

@SuppressWarnings("unchecked")
public T pop() {
    if (estVide()) throw new NoSuchElementException();
    taille--;
    T sommet = (T) donnees[taille];
    donnees[taille] = null;
    return sommet;
}

PileTableau place le sommet à la case \(\texttt{taille}-1\) : push écrit après le dernier élément, pop lit et vide la dernière case, sans aucun décalage. Placer le sommet en case 0 donnerait le même contrat et les mêmes résultats, mais chaque opération décalerait toute la pile. Une pile vide lève NoSuchElementException au pop, l’exception qu’utilisent aussi les collections du JDK.

Application : vérifier un parenthésage

Un éditeur de code signale (4*[5+1)] comme incorrect : les crochets et les parenthèses s’y croisent. Le raisonnement est celui d’une pile : chaque symbole ouvrant est mis en attente ; chaque symbole fermant doit correspondre au dernier ouvrant en attente, qui est retiré.

static boolean estEquilibree(String e) {
    Pile<Character> pile = new PileTableau<>();
    for (char c : e.toCharArray()) {
        if (c == '(' || c == '[' || c == '{') {
            pile.push(c);
        } else if (c == ')' || c == ']' || c == '}') {
            if (pile.estVide()) return false;
            char ouvrante = pile.pop();
            if (!correspond(ouvrante, c)) return false;
        }
    }
    return pile.estVide();
}
// dans main :
System.out.println(estEquilibree("{2*[500+(3*250)]}"));

Étape	Lignes	Instruction	Effet	Écrit
1	2, 15	`estEquilibree("{2[500+(3250)]}") ; pile vide`	L’expression a 17 caractères ; la pile des ouvrantes en attente est vide.
2	3–5	`c = '{' : pile.push('{')`	Caractère 0, `{` : ouvrante, empilée ; 1 en attente.
3	3–5	`c = '[' : pile.push('[')`	Caractère 3, `[` : ouvrante, empilée (2 ignorés) ; 2 en attente.
4	3–5	`c = '(' : pile.push('(')`	Caractère 8, `(` : ouvrante, empilée (4 ignorés) ; 3 en attente.
5	3, 6–9	`c = ')' : pop() rend '(', correspond`	Caractère 14, `)` : `pop()` rend `(`, qui correspond (5 ignorés).
6	3, 6–9	`c = ']' : pop() rend '[', correspond`	Caractère 15, `]` : `pop()` rend `[`, qui correspond.
7	3, 6–9	`c = '}' : pop() rend '{', correspond`	Caractère 16, `}` : `pop()` rend `{`, qui correspond.
8	12	`return pile.estVide()`	Fin de l’expression : aucune ouvrante en attente, la méthode rend `true`.
9	15	`println(...)`	Équilibrée : au plus 3 ouvrantes en attente, la profondeur d’imbrication.	`true`

Les caractères qui ne sont ni ouvrants ni fermants ne passent que par le test de la ligne 4, puis celui de la ligne 6 : ils ne touchent pas la pile. Les deux états ci-dessous sont ceux des étapes 4 et 5 : après la troisième ouvrante, la pile contient {, [, ( ; la première fermante, ), dépile (, qui lui correspond (en pointillé, l’élément dépilé).

Étape 4 : trois ouvrantes en attente

Étape 5 : ) dépile (

Sortie \(\rightarrow\)

true

La méthode rejette une expression de trois façons, une par instruction return false ou par le retour final : une fermante qui arrive sur une pile vide (ligne 7), une fermante qui ne correspond pas à l’ouvrante dépilée (ligne 9), une ouvrante restée en attente à la fin (ligne 12). L’oubli du test final est l’erreur la plus fréquente : la méthode accepte alors toute expression à laquelle il manque des fermantes, comme [(7+2)*3. La hauteur maximale de la pile est la profondeur d’imbrication de l’expression.

Application : évaluer une expression postfixe

En notation postfixe, l’opérateur suit ses deux opérandes : 3 4 + vaut 7, et \((1+2)\times3\) s’écrit 1 2 + 3 *. Aucune parenthèse n’est nécessaire : l’ordre des jetons fixe l’ordre des calculs. L’évaluation se fait en un parcours, avec une pile d’opérandes : un nombre est empilé ; un opérateur dépile deux valeurs, calcule, et empile le résultat. À la fin, le résultat est le seul élément restant.

public static int evaluer(String expression) {
    Pile<Integer> pile = new PileTableau<>();
    for (String jeton : expression.trim().split("\\s+")) {
        if (estOperateur(jeton)) {
            if (pile.taille() < 2) {
                throw new IllegalArgumentException("operandes manquants");
            }
            int b = pile.pop();  // ATTENTION a l'ordre
            int a = pile.pop();
            pile.push(appliquer(jeton, a, b));
        } else {
            pile.push(Integer.parseInt(jeton));
        }
    }
    int resultat = pile.pop();
    if (!pile.estVide()) {
        throw new IllegalArgumentException("expression mal formee");
    }
    return resultat;
}

La méthode du cours vérifie aussi la forme de l’expression : un opérateur qui trouve moins de deux opérandes, ou des opérandes restés en attente à la fin, lèvent IllegalArgumentException. L’exemple pas à pas qui suit utilise une version réduite, sans ces vérifications, sur une expression de prix : le montant rendu sur un billet de 5 000 FCFA pour 3 kg de riz à 450 FCFA et 2 litres d’huile à 1 200 FCFA, soit \(5\,000-(450\times3+1\,200\times2)\).

static int evaluer(String e) {
    Pile<Integer> pile = new PileTableau<>();
    for (String jeton : e.split(" ")) {
        if (estOperateur(jeton)) {
            int b = pile.pop();
            int a = pile.pop();
            pile.push(appliquer(jeton, a, b));
        } else {
            pile.push(Integer.parseInt(jeton));
        }
    }
    return pile.pop();
}
// dans main :
System.out.println(evaluer("5000 450 3 * 1200 2 * + -"));

Étape	Lignes	Instruction	Effet	Écrit
1	2, 15	`evaluer("5000 450 3 * 1200 2 * + -") ; pile vide`	Riz, 3 kg à 450 ; huile, 2 l à 1 200 ; billet de 5 000 FCFA : 9 jetons.
2	3–4, 8–9	`jeton 5000 : push(5000)`	`5000` : un nombre, empilé ; 1 opérande en attente.
3	3–4, 8–9	`jeton 450 : push(450)`	`450` : un nombre, empilé ; 2 opérandes en attente.
4	3–4, 8–9	`jeton 3 : push(3)`	`3` : un nombre, empilé ; 3 opérandes en attente.
5	3–7	`jeton * : b = 3, a = 450, push(1350)`	`*` : `b` \(=3\), `a` \(=450\) ; \(450\times3=1350\) est empilé.
6	3–4, 8–9	`jeton 1200 : push(1200)`	`1200` : un nombre, empilé ; 3 opérandes en attente.
7	3–4, 8–9	`jeton 2 : push(2)`	`2` : un nombre, empilé ; 4 opérandes en attente.
8	3–7	`jeton * : b = 2, a = 1200, push(2400)`	`*` : `b` \(=2\), `a` \(=1200\) ; \(1200\times2=2400\) est empilé.
9	3–7	`jeton + : b = 2400, a = 1350, push(3750)`	`+` : `b` \(=2400\), `a` \(=1350\) ; \(1350+2400=3750\) est empilé.
10	3–7	`jeton - : b = 3750, a = 5000, push(1250)`	`-` : `b` \(=3750\), `a` \(=5000\) ; \(5000-3750=1250\) est empilé.
11	12	`return pile.pop()`	Le seul élément restant est le résultat : 1 250 FCFA de monnaie.
12	15	`println(evaluer(...))`	Au plus 4 opérandes en attente ; un seul parcours, aucune parenthèse.	`1250`

Étape 5 : \(450\times3\)

Étape 8 : \(1\,200\times2\)

Étape 10 : \(5\,000-3\,750\)

Sortie \(\rightarrow\)

À l’étape 5, l’opérateur * dépile 3 puis 450 et empile 1 350 ; à l’étape 8, il dépile 2 puis 1 200 et empile 2 400. La pile atteint sa hauteur maximale, 4, à l’étape 7 : quatre opérandes sont en attente, parce que le prix de l’huile doit être calculé avant d’être ajouté à celui du riz. À l’étape 10, - calcule \(5\,000-3\,750\) : a, dépilé en second, est l’opérande de gauche.

L’ordre des opérandes

Le premier pop rend le second opérande : b doit le recevoir. Le programme suivant échange les deux dépilements :

int a = pile.pop();  // les deux depilements echanges
int b = pile.pop();
// dans main :
for (String e : new String[] {"1200 450 -", "1200 450 +", "6000 4 /"}) {
    int juste = Postfixe.evaluer(e);
    int faux = evaluerInverse(e);
    System.out.println(e + " : " + juste + " ; echanges : " + faux);
}

Sortie \(\rightarrow\)

1200 450 - : 750 ; echanges : -750
1200 450 + : 1650 ; echanges : 1650
6000 4 / : 1500 ; echanges : 0

L’erreur est invisible avec + et *, qui sont commutatifs : un jeu de tests qui ne contient que des additions ne la détecte pas. Avec -, le signe change ; avec /, la division entière de Java calcule \(4/6\,000=0\). Un test de l’évaluateur contient donc au moins une soustraction et une division.

Queue : le premier arrivé sort le premier

Une file sert ses éléments dans l’ordre d’arrivée (FIFO, first in, first out) : enqueue ajoute en fin, dequeue retire en tête.

public interface File<T> {
    void enqueue(T x);  // ajoute en fin
    T dequeue();        // retire la tete
    T peek();           // lit la tete
    boolean estVide();
    int taille();
}

La réalisation qui place la tête en case 0 d’un tableau respecte le contrat, mais chaque dequeue décale tous les éléments restants (section 7). Le tableau circulaire évite tout décalage : il ne déplace plus les éléments, mais l’indice de la tête. Deux variables décrivent la file : tete, l’indice du prochain élément à servir, et taille, le nombre d’éléments. La fin se calcule : \[\texttt{fin} \;=\; (\texttt{tete}+\texttt{taille}) \bmod m,\] où \(m\) est la capacité du tableau. Le modulo fait repasser la fin, puis la tête, en case 0 quand elles atteignent le bord : le tableau se comporte comme un anneau.

private Object[] donnees;
private int tete = 0;    // prochain a servir
private int taille = 0;  // nombre d'elements

public void enqueue(T x) {
    if (taille == donnees.length) agrandir();
    int fin = (tete + taille) % donnees.length;
    donnees[fin] = x;
    taille++;
}

@SuppressWarnings("unchecked")
public T dequeue() {
    if (estVide()) throw new NoSuchElementException();
    T premier = (T) donnees[tete];
    donnees[tete] = null;
    tete = (tete + 1) % donnees.length;
    taille--;
    return premier;
}

Exemple pas à pas : un guichet de six cases

Au point Wave de Colobane, Sokhna et Assane attendent dans les cases 4 et 5 d’une file de 6 cases (tete \(=4\), taille \(=2\)). Thierno et Abdou arrivent, puis deux clients sont servis. La version réduite du programme écrit la fin en une instruction, comme ArrayDeque au TP.

static void enqueue(String x) {
    donnees[(tete + taille) % donnees.length] = x;
    taille++;
}
static String dequeue() {
    String premier = donnees[tete];
    donnees[tete] = null;
    tete = (tete + 1) % donnees.length;
    taille--;
    return premier;
}
// dans main :
enqueue("Thierno");
enqueue("Abdou");
System.out.println(dequeue() + " " + dequeue());

Étape	Lignes	Instruction	Effet	Écrit
1	2–3, 13	`enqueue("Thierno") : case (4 + 2) % 6 = 0`	Sokhna et Assane en cases 4, 5 ; Thierno en case \((4+2) \bmod 6=0\).
2	2–3, 14	`enqueue("Abdou") : case (4 + 3) % 6 = 1`	Abdou en case \((4+3) \bmod 6=1\) : cases 4, 5, 0, 1, sans déplacement.
3	6, 15	`dequeue() : premier = donnees[4]`	`premier` reçoit la case 4 : Sokhna, arrivée la première.
4	7	`donnees[4] = null`	La case 4 est vidée : plus de référence vers Sokhna.
5	8–10	`tete = (4 + 1) % 6 ; taille-- ; return`	`tete` avance en case 5, `taille` \(=3\) : aucun élément n’a bougé.
6	6–10, 15	`dequeue() : Assane ; tete = (5 + 1) % 6`	Assane sort, case 5 vidée ; `tete` \(=(5+1) \bmod 6=0\) : la tête boucle.
7	15	`println(dequeue() + " " + dequeue())`	Sokhna puis Assane, l’ordre d’arrivée : une case et un indice par opération.	`Sokhna Assane`

Étape 1 : la fin repasse en case 0

Étape 6 : la tête repasse en case 0

Sortie \(\rightarrow\)

Sokhna Assane

À l’étape 1, Thierno est écrit en case \((4+2) \bmod 6=0\) : la file occupe les cases 4, 5 et 0, dans cet ordre logique. À l’étape 6, la tête avance de la case 5 à la case \((5+1) \bmod 6=0\). Chaque opération a écrit une case et changé un indice : aucun client n’a été déplacé.

Agrandir dans l’ordre logique

Quand la file est pleine, agrandir() alloue deux fois plus de cases. Elle ne peut pas recopier les cases dans l’ordre où elles sont rangées : la file a pu boucler, et l’élément de la case 0 n’est pas forcément le premier. Elle recopie donc les éléments dans l’ordre logique, en partant de tete : l’élément de rang \(k\) est en case \((\texttt{tete}+k) \bmod m\), et il est rangé en case \(k\) du nouveau tableau, dont la tête redevient 0.

static void agrandir() {
    String[] neuf = new String[2 * donnees.length];
    for (int k = 0; k < taille; k++) {
        neuf[k] = donnees[(tete + k) % donnees.length];
    }
    donnees = neuf;
    tete = 0;
}
// dans main :
enqueue("Codou");
System.out.println(Arrays.toString(donnees));

Étape	Lignes	Instruction	Effet	Écrit
1	1–2, 10	`enqueue("Codou") : file pleine, agrandir()`	`enqueue("Codou")` sur une file pleine : tête en case 2, ordre d’arrivée Arame, Ndiaga, Demba, Samba ; `agrandir()` alloue 8 cases.
2	3–4	`k = 0 : neuf[0] = donnees[2]`	\(k=0\) : la case \((2+0) \bmod 4=2\), Arame, est recopiée en case 0 du nouveau tableau.
3	3–4	`k = 1 : neuf[1] = donnees[3]`	\(k=1\) : la case \((2+1) \bmod 4=3\), Ndiaga, est recopiée en case 1.
4	3–4	`k = 2 : neuf[2] = donnees[0]`	\(k=2\) : la case \((2+2) \bmod 4=0\), Demba, est recopiée en case 2.
5	3–4	`k = 3 : neuf[3] = donnees[1]`	\(k=3\) : la case \((2+3) \bmod 4=1\), Samba, est recopiée en case 3.
6	6–7	`donnees = neuf ; tete = 0`	Le nouveau tableau remplace l’ancien et `tete` redevient 0 : l’ordre logique coïncide avec l’ordre des cases.
7	10	`donnees[(0 + 4) % 8] = "Codou"`	`enqueue` reprend : la fin vaut \((0+4) \bmod 8=4\), Codou y est écrit, `taille` \(=5\).
8	11	`println(Arrays.toString(donnees))`	4 copies, dans l’ordre logique : une copie dans l’ordre physique (`System.arraycopy(donnees, 0, neuf, 0, taille)`) aurait mis Demba en tête de file.	`[Arame, Ndiaga, Demba, Samba, Codou, null, null, null]`

Étape 4 : la case 0 recopiée en case 2

Étape 6 : le tableau remis à plat

Sortie \(\rightarrow\)

[Arame, Ndiaga, Demba, Samba, Codou, null, null, null]

Recopier dans l’ordre physique

System.arraycopy(donnees, 0, neuf, 0, taille) recopie les cases dans l’ordre où elles sont rangées. Si la file a bouclé, l’ordre de sortie est détruit sans qu’aucune exception ne le signale : dans l’exemple, Demba (case 0) se retrouverait en tête, devant Arame et Ndiaga arrivés avant lui. Seul un test qui fait boucler la file puis l’agrandit révèle l’erreur.

Pourquoi garder taille

Avec les seuls indices tete et fin, la file vide et la file pleine donnent la même configuration, \(\texttt{tete}=\texttt{fin}\) : impossible de les distinguer. Deux remèdes existent : garder le compteur taille, retenu ici, ou ne jamais remplir la dernière case. java.util.ArrayDeque retient le second : son tableau a toujours au moins une case vide. Le test tete < fin pour « la file n’est pas vide » est faux dès que la file a bouclé.

Deque : les deux extrémités

Un deque (double-ended queue) ajoute et retire aux deux bouts. Il généralise la pile et la file : restreint à addLast et removeLast, il se comporte comme une pile ; restreint à addLast et removeFirst, comme une file. Son contrat suit les noms du JDK :

public interface Deque<T> {
    void addFirst(T x);
    void addLast(T x);
    T removeFirst();
    T removeLast();
    T peekFirst();
    T peekLast();
    int size();
    boolean isEmpty();
}

private int precedent(int i) {
    return (i - 1 + donnees.length) % donnees.length;
}

public void addFirst(T x) {
    if (taille == donnees.length) agrandir();
    tete = precedent(tete);
    donnees[tete] = x;
    taille++;
}

public void addLast(T x) {
    if (taille == donnees.length) agrandir();
    donnees[(tete + taille) % donnees.length] = x;
    taille++;
}

Sur un tableau circulaire, addFirst recule l’indice de la tête et écrit dans la nouvelle case de tête, addLast écrit après la fin ; removeFirst et removeLast vident une case. Hors agrandissement, chacune des huit opérations lit ou écrit une case et change au plus un indice. La réalisation complète, ArrayDeque, est l’objet du TP.

Le modulo négatif

Reculer un indice demande un soin particulier. En Java, l’opérateur % est un reste, du signe du dividende, et non le modulo mathématique :

public class ExModulo {
    public static void main(String[] args) {
        System.out.println((3 - 1) % 8 + " " + (0 - 1) % 8);
        System.out.println((0 - 1 + 8) % 8 + " " + Math.floorMod(0 - 1, 8));
        String[] donnees = new String[8];
        int tete = (0 - 1) % donnees.length;  // sans le + donnees.length
        donnees[tete] = "Daba";
    }
}

Sortie \(\rightarrow\)

2 -1
7 7

Sortie d’erreur \(\rightarrow\)

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index -1 out of bounds for length 8
    at ExModulo.main(ExModulo.java:7)

\((0-1)\,\%\,8\) vaut \(-1\), et l’écriture en case \(-1\) lève ArrayIndexOutOfBoundsException. Pour un indice \(0\leq i<m\), la valeur \(i-1+m\) est comprise entre \(m-1\) et \(2m-2\), positive : son reste par \(m\) est l’indice précédent sur l’anneau, \(m-1\) quand \(i=0\). C’est l’expression de la méthode precedent. Math.floorMod(a, m) rend le modulo mathématique, toujours entre 0 et \(m-1\).

Les files et les piles du JDK

Le JDK réalise ces ADT par des interfaces (Queue, Deque, List) et des classes (ArrayDeque, ArrayList, LinkedList). java.util.ArrayDeque est un tableau circulaire redimensionnable qui réalise à la fois Queue et Deque : c’est la file du parcours en largeur de la Séance 5.

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Queue;
Queue<String> guichet = new ArrayDeque<>();
guichet.add("Daba");
guichet.add("Mbene");
guichet.add("Kine");
System.out.println(guichet.remove() + " " + guichet);
Deque<String> dossiers = new ArrayDeque<>();
dossiers.push("acte 1");
dossiers.push("acte 2");
dossiers.push("acte 3");
System.out.println(dossiers.pop() + " " + dossiers);

Sortie \(\rightarrow\)

Daba [Mbene, Kine]
acte 3 [acte 2, acte 1]

add écrit en queue et remove retire en tête : la file sert Daba la première. Pour la pile, push est addFirst et pop est removeFirst : le sommet de la pile du JDK est en tête du deque, et son affichage commence par le sommet. La documentation d’ArrayDeque l’annonce plus rapide que Stack comme pile et que LinkedList comme file ; celle de java.util.Stack, classe historique, recommande d’utiliser Deque. ArrayDeque refuse enfin l’élément null, que poll() rend pour signaler une file vide.

Choisir

La démarche se fait en trois temps, dans cet ordre. D’abord, quelles opérations le problème demande-t-il ? : on identifie l’ADT. Annuler la dernière action demande la plus récente : une pile. Servir dans l’ordre d’arrivée : une file. Un historique où l’on consulte le plus récent et d’où l’on purge le plus ancien quand la capacité est atteinte : un deque. Ensuite, quelles opérations sont fréquentes ? : on choisit la structure d’après ce profil d’usage. Enfin, que mesure-t-on ? : on compte, et l’on révise le choix si la mesure contredit la prévision.

besoin	ADT	réalisation courante
accès par rang, ajout en fin	List	tableau redimensionnable
insertions et retraits en tête	List	nœuds chaînés
annuler, revenir en arrière	Stack	tableau, sommet en fin
servir dans l’ordre d’arrivée	Queue	tableau circulaire
ajouter et retirer aux deux bouts	Deque	tableau circulaire

Le programme suivant sert \(n\) clients de deux façons : par une liste sur tableau, avec ajouter(x) pour enqueue et supprimer(0) pour dequeue, et par la file circulaire.

for (int n : new int[] {1000, 4000}) {
    ListeTableau<Integer> l = new ListeTableau<>();
    FileCirculaire<Integer> f = new FileCirculaire<>();
    for (int k = 0; k < n; k++) {
        l.ajouter(k);    // enqueue : en fin
        f.enqueue(k);
    }
    for (int k = 0; k < n; k++) {
        l.supprimer(0);  // dequeue : tout se decale
        f.dequeue();
    }
    System.out.println(n + " clients : liste " + l.decalages
        + " decalages ; file circulaire " + f.copies + " copies");
}

Sortie \(\rightarrow\)

1000 clients : liste 499500 decalages ; file circulaire 1016 copies
4000 clients : liste 7998000 decalages ; file circulaire 4088 copies

La première réalisation respecte le contrat : les clients sortent dans l’ordre d’arrivée, et aucun test de comportement ne la distingue de la seconde. Mais supprimer(0) décale tous les éléments restants : \(n(n-1)/2\) décalages pour servir \(n\) clients, 499 500 pour 1 000 clients, 16 fois plus pour 4 fois plus de clients ; la file circulaire n’en fait aucun, et ses copies restent sous \(2n\). Un programme peut être correct et coûteux : les tests vérifient le contrat, la mesure révèle le coût. La Séance 2 donne les outils pour l’établir sans mesurer.

Les structures côte à côte

opération	tableau redimensionnable	nœuds chaînés	tableau circulaire
lecture au rang \(i\)	1 accès	\(i\) références suivies	1 accès, case \((\texttt{tete}+i) \bmod m\)
ajout en fin	1 écriture, moins de 2 copies amorties	2 références écrites	1 écriture, moins de 2 copies amorties
ajout en tête	\(n\) décalages	2 références écrites	1 écriture (`addFirst`)
retrait en tête	\(n-1\) décalages	1 référence écrite	1 écriture (`dequeue`)
retrait en fin	1 écriture	\(n-2\) références suivies	1 écriture (`removeLast`)
mémoire	\(n\) à \(2n\) cases (ajouts seuls)	\(n\) nœuds	\(n\) à \(2n\) cases (ajouts seuls)

Le retrait en fin d’une liste chaînée dont chaque nœud ne connaît que son suivant est la seule opération d’extrémité qui demande un parcours : la référence queue donne le dernier nœud, mais pas l’avant-dernier, qui doit devenir la nouvelle queue. Un chaînage double (chaque nœud connaît aussi son précédent) lève cette difficulté, au prix d’une référence de plus par nœud. Le tableau circulaire est la seule des trois réalisations où les quatre opérations d’extrémité se font sans décalage ni parcours : c’est le tableau de java.util.ArrayDeque, que la documentation du JDK recommande comme pile et comme file.

Exercices corrigés

Les trois exercices reprennent les mécanismes de la séance sur des données nouvelles ; leur présentation (état de la structure après chaque opération, compteurs, trace d’une pile) est celle qu’attendent le TD et le TP.

Exercice 1 : la même suite sur les deux listes

Une ListeTableau<Integer> créée avec une capacité de 2 et une ListeChainee<Integer> reçoivent, dans cet ordre, les opérations ajouter(64), ajouter(0, 18), ajouter(1, 91), ajouter(0, 27), ajouter(2, 50), supprimer(0), get(3).

Pour la liste sur tableau, donner après chaque opération les cases de donnees (. pour une case vide), taille, et le nombre de décalages et de copies.
Pour la liste chaînée, donner la chaîne et le nombre de références suivies par chaque opération.
Comparer les totaux. Que vaudraient-ils avec une capacité initiale de 8 ?
Quelle valeur rend get(3) ?

Correction

(a) Règles : ajouter(i, x) appelle d’abord agrandir() si \(\texttt{taille}=\texttt{donnees.length}\) (copie des taille éléments dans un tableau deux fois plus grand), puis décale les \(\texttt{taille}-i\) éléments des rangs \(i\) et suivants ; supprimer(i) décale les \(\texttt{taille}-i-1\) éléments qui suivent. Les cases écrites sont en rouge.

opération	`donnees` (tableau)	taille	décalages	copies	chaîne	références
`ajouter(64)`	`64 .`	1	0	0	`64`	0
`ajouter(0, 18)`	`18 64`	2	1	0	`18 64`	0
`ajouter(1, 91)`	`18 91 64 .`	3	1	2	`18 91 64`	0
`ajouter(0, 27)`	`27 18 91 64`	4	3	0	`27 18 91 64`	0
`ajouter(2, 50)`	`27 18 50 91 64 . . .`	5	2	4	`27 18 50 91 64`	1
`supprimer(0)`	`18 50 91 64 . . . .`	4	4	0	`18 50 91 64`	0
`get(3)`	`18 50 91 64 . . . .`	4	0	0	`18 50 91 64`	3
total	capacité 8		11	6		4

ajouter(64) écrit en case 0 d’une liste vide. ajouter(0, 18) décale 64 en case 1 : le tableau de 2 cases est plein. ajouter(1, 91) trouve donc \(\texttt{taille}=\texttt{donnees.length}=2\) : agrandir() recopie 18 et 64 dans 4 cases (2 copies), puis 64 recule en case 2 (1 décalage) et 91 est écrit en case 1. ajouter(0, 27) décale les trois éléments (3 décalages) et remplit le tableau. ajouter(2, 50) le trouve plein : 4 copies vers 8 cases, puis 91 et 64 reculent (2 décalages). supprimer(0) rend 27 et avance les quatre éléments suivants (4 décalages), puis vide la case 4. Au total, 11 décalages et 6 copies, pour une capacité finale de 8.

(b) Règles : en tête et en fin, aucun parcours ; au rang \(i\) (ni en tête, ni en fin), noeud(i - 1) suit \(i-1\) références ; get(i) en suit \(i\). ajouter(64) et ajouter(0, 18) insèrent en tête, ajouter(1, 91) au rang 1 d’une liste de 2 éléments, qui n’est pas la fin : noeud(0), 0 référence. ajouter(2, 50) suit 1 référence (de 27 à 18) pour atteindre le rang 1 ; supprimer(0) retire la tête sans parcours ; get(3) suit 3 références. Total : 4.

(c) Le tableau a fait 11 décalages et 6 copies, la liste chaînée 4 parcours de référence : la suite est riche en insertions en tête et au début, ce qui favorise la liste chaînée. Avec une capacité initiale de 8, aucun agrandissement n’a lieu (5 éléments au plus) : 0 copie, mais toujours 11 décalages, qui ne dépendent que des rangs.

(d) Après supprimer(0), la liste est 18, 50, 91, 64 : get(3) rend 64, en un accès dans le tableau et après 3 références dans la chaîne.

Erreur fréquente : compter les copies de l’agrandissement comme des décalages, ou oublier le décalage qui suit l’agrandissement. ajouter(1, 91) coûte 2 copies et* 1 décalage : l’agrandissement ne place pas le nouvel élément.*

Exercice 2 : une pile pour vérifier, une pile pour calculer

Une boutique de Rufisque facture 3 lots d’un article à 1 500 FCFA accompagné de 2 accessoires à 750 FCFA : \((1\,500+2\times750)\times3\).

Dérouler estEquilibree("{(1500+[2*750])*3}") : pour chaque symbole ouvrant ou fermant, son indice, l’action et la pile après. Donner le verdict et la hauteur maximale.
Évaluer 1500 2 750 * + 3 * : la pile après chaque jeton, le résultat, la hauteur maximale.
Quel résultat donne l’évaluateur dont les deux dépilements sont échangés ? Qu’en conclure pour les tests ?
Que vaut 1500 2 750 * 3 * + ? Écrire l’expression usuelle correspondante.

Correction

(a) Règle : une ouvrante est empilée ; une fermante dépile l’ouvrante en attente la plus récente, qui doit lui correspondre ; à la fin, la pile doit être vide. Les chiffres et les opérateurs ne touchent pas la pile.

indice	caractère	action	pile après (base … sommet)
0	`{`	empile	`{`
1	`(`	empile	`{ (`
7	`[`	empile	`{ ( [`
13	`]`	dépile, correspond	`{ (`
14	`)`	dépile, correspond	`{`
17	`}`	dépile, correspond	`(vide)`

Chaque fermante trouve en sommet l’ouvrante de même nature : ] ferme le [ de l’indice 7, ) le ( de l’indice 1, et } l’accolade de l’indice 0. La pile est vide à la fin : l’expression est équilibrée. La hauteur maximale, 3, est atteinte après l’indice 7 : trois niveaux d’imbrication.

(b) Règle : un nombre est empilé ; un opérateur dépile b (le sommet) puis a, et empile a op b.

jeton	`1500`	`2`	`750`	`*`	`+`	`3`	`*`
pile	1500	2 1500	750 2 1500	1500 1500	3000	3 3000	9000
hauteur	1	2	3	2	1	2	1

Le premier * calcule \(2\times750=1\,500\), le + calcule \(1\,500+1\,500=3\,000\), le dernier * donne \(3\,000\times3=9\,000\) FCFA. La hauteur maximale est 3, après le jeton 750.

(c) 9 000 également : les deux opérateurs sont commutatifs, et l’échange de a et b ne change aucun résultat. Ce calcul ne peut donc pas servir de test pour l’ordre des opérandes : un test doit contenir une soustraction ou une division.

(d) 2 750 * donne 1 500, 3 * donne 4 500, et + ajoute le 1 500 resté en attente : 6 000. C’est \(1\,500+2\times750\times3\) : les mêmes nombres, mais sans les parenthèses, le prix de l’article n’est compté qu’une fois.

Erreur fréquente : dans (a), croire que ] peut fermer n’importe quelle ouvrante en attente. Il ne peut fermer que le sommet ; (4*[5+1)] est rejetée parce que ) trouve [ en sommet.

Exercice 3 : une file circulaire de quatre cases

À la mairie de Rufisque, les tickets sont servis dans l’ordre. Une FileCirculaire<Integer> de capacité 4 reçoit enqueue(31), enqueue(32), enqueue(33), deux dequeue(), enqueue(34), enqueue(35), enqueue(36), enqueue(37), puis un dequeue().

Après chaque opération, donner la case écrite ou libérée, les cases, tete, taille, la capacité et le nombre de copies.
Expliquer l’effet de enqueue(37).
Quel ticket le dernier dequeue() rendrait-il si agrandir() recopiait les cases dans l’ordre physique ?
Quelles cases sont occupées à la fin ?

Correction

(a) Règles : enqueue écrit en case \((\texttt{tete}+\texttt{taille}) \bmod m\) ; dequeue vide la case tete et avance \(\texttt{tete}=(\texttt{tete}+1) \bmod m\) ; quand la file est pleine, agrandir() recopie l’élément de rang \(k\), en case \((\texttt{tete}+k) \bmod m\), dans la case \(k\) d’un tableau de \(2m\) cases, et tete redevient 0. Les cases écrites sont en rouge.

opération	case écrite ou libérée	`donnees` après	`tete`	`taille`	capacité	copies
`enqueue(31)`	0	`31 . . .`	0	1	4	0
`enqueue(32)`	1	`31 32 . .`	0	2	4	0
`enqueue(33)`	2	`31 32 33 .`	0	3	4	0
`dequeue()` \(\rightarrow\) 31	0	`. 32 33 .`	1	2	4	0
`dequeue()` \(\rightarrow\) 32	1	`. . 33 .`	2	1	4	0
`enqueue(34)`	3	`. . 33 34`	2	2	4	0
`enqueue(35)`	0	`35 . 33 34`	2	3	4	0
`enqueue(36)`	1	`35 36 33 34`	2	4	4	0
`enqueue(37)`	4	`33 34 35 36 37 . . .`	0	5	8 (agrandi)	4
`dequeue()` \(\rightarrow\) 33	0	`. 34 35 36 37 . . .`	1	4	8	4

Les deux dequeue() servent 31 puis 32 : tete passe à 2, et les cases 0 et 1 sont libres. enqueue(34) écrit en case \((2+1) \bmod 4=3\), enqueue(35) en case \((2+2) \bmod 4=0\) : la fin a bouclé. enqueue(36) remplit la case 1 : la file est pleine, dans l’ordre logique 33, 34, 35, 36, rangés dans les cases 2, 3, 0, 1.

(b) enqueue(37) trouve \(\texttt{taille}=m=4\) : agrandir() recopie les cases 2, 3, 0, 1 dans les cases 0 à 3 d’un tableau de 8 cases (4 copies), tete redevient 0, puis 37 est écrit en case \((0+4) \bmod 8=4\).

(c) La copie dans l’ordre physique donnerait 35 36 33 34 dans les cases 0 à 3, avec tete \(=0\) : le dequeue() rendrait 35, servi avant 33 et 34 arrivés plus tôt. Aucune exception ne signalerait l’erreur.

(d) Le dernier dequeue() rend 33 : tete \(=1\), taille \(=4\), cases 1 à 4 occupées (34, 35, 36, 37).

Erreur fréquente : calculer la case de enqueue par \(\texttt{taille} \bmod m\), comme si la tête était toujours en case 0 ; après les deux dequeue(), enqueue(34) écrirait alors en case 1 au lieu de 3.

À retenir

Un type abstrait de données est un contrat : des opérations spécifiées par leur comportement. Une structure de données le réalise. En Java, le contrat s’écrit interface, rendue indépendante du type des éléments par un générique ; on déclare avec l’interface, et l’on ne nomme la classe qu’à la création.
La liste sur tableau lit un rang en un pas mais décale \(\texttt{taille}-i\) éléments pour insérer au rang \(i\) ; la liste chaînée insère en tête en écrivant deux références mais suit \(i\) références pour atteindre le rang \(i\).
Le doublement coûte au plus \(2n-6\) copies pour \(n\geq5\) ajouts : moins de 2 par ajout, en coût amorti, même si un ajout isolé en coûte \(n-1\). Une croissance d’un nombre fixe de cases coûte un nombre de copies quadratique.
Iterable et Iterator : le for-each garde sa position et parcourt une liste chaînée en \(n\) références.
La pile (LIFO) vérifie un parenthésage (trois façons d’échouer) et évalue une expression postfixe en un parcours ; le premier pop rend le second opérande.
La file (FIFO) et le deque sur un tableau circulaire n’ont aucun décalage : indices modulo \(m\), (i - 1 + m) % m pour reculer, taille pour distinguer la file vide de la file pleine, agrandissement dans l’ordre logique.
Un programme peut respecter le contrat et coûter cher : les tests vérifient le comportement, la mesure et l’analyse vérifient le coût.

Prochaine séance

La Séance 2, analyse algorithmique, compte les opérations élémentaires d’un algorithme, définit les notations \(\mathcal{O}\), \(\Omega\) et \(\Theta\), distingue meilleur cas, pire cas et cas moyen, et résout les récurrences des algorithmes récursifs jusqu’au théorème maître : les coûts constatés dans cette séance y deviennent des énoncés démontrés.

Références

Sedgewick, Wayne — Algorithms, 4^e éd., Addison-Wesley, 2011 (§ 1.2 : abstraction des données ; § 1.3 : sacs, files et piles, tableaux redimensionnables, listes chaînées, itérateurs, évaluation d’expressions ; § 1.4 : coût amorti).
Cormen, Leiserson, Rivest, Stein — Introduction to Algorithms, 4^e éd., MIT Press, 2022 (ch. 10 : piles, files, listes chaînées ; § 16.4 : tables dynamiques).
Skiena — The Algorithm Design Manual, 3^e éd., Springer, 2020 (ch. 3 : structures de données).
Bloch — Effective Java, 3^e éd., Addison-Wesley, 2018 (item 64 : désigner les objets par leur interface).
OpenJDK 17 — code source de java.util.ArrayList, java.util.ArrayDeque et java.util.Stack.

Le contrat : type abstrait de données

En Java : l’interface générique

List sur un tableau contigu

Exemple pas à pas : deux insertions et un agrandissement

Agrandir et supprimer

Le coût amorti du doublement

List sur des nœuds chaînés

Insérer et supprimer

Exemple pas à pas : une insertion en tête, une insertion au rang 2

Parcourir une liste : Iterable et Iterator

Les deux réalisations mesurées

Stack : le dernier arrivé sort le premier

Application : vérifier un parenthésage

Application : évaluer une expression postfixe

Queue : le premier arrivé sort le premier

Exemple pas à pas : un guichet de six cases

Agrandir dans l’ordre logique

Deque : les deux extrémités

Le modulo négatif

Les files et les piles du JDK

Choisir

Les structures côte à côte

Exercices corrigés

Exercice 1 : la même suite sur les deux listes

Exercice 2 : une pile pour vérifier, une pile pour calculer

Exercice 3 : une file circulaire de quatre cases

À retenir

Prochaine séance

Références

Pour cette séance

Parcourir une liste : `Iterable` et `Iterator`