Structures de données de collection

De nombreux types de données fondamentaux reposent sur la gestion d'une collection d'objets. La valeur du type est un ensemble d'objets, et les opérations consistent à ajouter, supprimer ou accéder à ces objets. Nous examinerons trois structures de données de ce type : le Sac (Bag), la File d'attente (Queue) et la Pile (Stack). Leur différence réside dans l'ordre dans lequel les éléments sont accessibles ou supprimés.

Le type Sac (Bag)

Un sac est une collection qui ne permet pas la suppression d'éléments. L'ordre d'itération n'est pas spécifié et est indépendant de la séquence d'ajout.

API du Sac

public class Bag<Item> implements Iterable<Item>
    Bag()                           // Crée un sac vide
    void add(Item item)             // Ajoute un élément
    boolean isEmpty()               // Vérifie si le sac est vide
    int size()                      // Retourne le nombre d'éléments

La file d'attente (Queue)

L'utilisation d'une file d'attente permet de conserver les éléments dans leur ordre d'arrivée : le premier ajouté est le premier à être retiré (FIFO - First-In, First-Out).

API de la file d'attente

public class Queue<Item> implements Iterable<Item>
    Queue()                         // Crée une file vide
    void enqueue(Item item)         // Ajoute un élément à la fin
    Item dequeue()                  // Retire l'élément ajouté le plus récemment
    boolean isEmpty()               // Vérifie si la file est vide
    int size()                      // Retourne le nombre d'éléments

La pile (Stack)

La pile (ou pile LIFO - Last-In, First-Out) est une collection où le dernier élément ajouté est le premier à être retiré. Un itérateur parcourt les éléments dans l'ordre inverse de leur insertion. Elle est utile pour inverser un ordre de traitement.

API de la pile

public class Stack<Item> implements Iterable<Item>
    Stack()                         // Crée une pile vide
    void push(Item item)            // Ajoute un élément au sommet
    Item pop()                      // Retire et retourne l'élément au sommet
    boolean isEmpty()               // Vérifie si la pile est vide
    int size()                      // Retourne le nombre d'éléments

Exemple d'application : Évaluation d'expression arithmétique

Un algorithme classique utilise deux piles (une pour les opérateurs, une pour les opérandes) pour évaluer une expression parenthésée. L'expression est lue de gauche à droite selon ces règles :

• Si c'est un opérande (nombre), on l'empile sur la pile des opérandes.
• Si c'est un opérateur (+, -, *, /, sqrt), on l'empile sur la pile des opérateurs.
• On ignore les parenthèses ouvrantes '('.
• À une parenthèse fermante ')', on dépile un opérateur, on dépile le nombre nécessaire d'opérandes, on calcule le résultat et on l'empile sur la pile des opérandes.

Exemple : Évaluer l'expression ( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) ).

Implémentation possible de l'évaluateur :

package algorithm;

import stdLib.StdIn;

public class Evaluateur {

    public static void main(String[] args) {
        Stack<String> operateurs = new Stack<>();
        Stack<Double> operandes = new Stack<>();

        while (!StdIn.isEmpty()) {
            String token = StdIn.readString();

            if(token.equals("fin")){
                System.out.println(operandes.pop());
                break;
            }

            if (token.equals("(")) { /* Ignorer */ }
            else if (token.equals("+")) operateurs.push(token);
            else if (token.equals("-")) operateurs.push(token);
            else if (token.equals("*")) operateurs.push(token);
            else if (token.equals("/")) operateurs.push(token);
            else if (token.equals("sqrt")) operateurs.push(token);
            else if (token.equals(")")) {
                String op = operateurs.pop();
                double resultat = operandes.pop();
                if(op.equals("+")) resultat = operandes.pop() + resultat;
                else if(op.equals("-")) resultat = operandes.pop() - resultat;
                else if(op.equals("*")) resultat = operandes.pop() * resultat;
                else if(op.equals("/")) resultat = operandes.pop() / resultat;
                else if(op.equals("sqrt")) resultat = Math.sqrt(resultat);
                operandes.push(resultat);
            } else {
                operandes.push(Double.parseDouble(token));
            }
        }
    }
}

Saisie console :

( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) )
fin
101.0

Implémentation d'une pile

Pile à capacité fixe

La conception la plus simple, non générique et non itérable :

package algorithm;

public class PileCapaciteFixe {
    private String[] tableau;
    private int compteur;

    public PileCapaciteFixe(int capacite){
        tableau = new String[capacite];
    }

    public boolean estVide(){
        return compteur == 0;
    }

    public int taille(){
        return compteur;
    }

    public void empiler(String element){
        tableau[compteur++] = element;
    }

    public String depiler(){
        return tableau[--compteur];
    }
}

Pile redimensionnable avec itérateur

Améliorations : générique, tableau dynamique et support de l'itération.

package algorithm;

import java.util.Iterator;

public class PileRedimensionnable<E> implements Iterable<E>{
    private E[] tableau = (E[]) new Object[1];
    private int compteur = 0;

    public boolean estVide(){
        return compteur == 0;
    }

    public int taille(){
        return compteur;
    }

    private void redimensionner(int nouvelleCapacite){
        E[] copie = (E[]) new Object[nouvelleCapacite];
        for(int i=0; i<compteur; i++){
            copie[i] = tableau[i];
        }
        tableau = copie;
    }

    public void empiler(E element){
        if(compteur == tableau.length) redimensionner(2*tableau.length);
        tableau[compteur++] = element;
    }

    public E depiler(){
        E element = tableau[--compteur];
        tableau[compteur] = null; // Aide le ramasse-miettes
        if(compteur > 0 && compteur == tableau.length/4) redimensionner(tableau.length/2);
        return element;
    }

    @Override
    public Iterator<E> iterator() {
        return new IterateurInverse();
    }

    private class IterateurInverse implements Iterator<E>{
        private int position = compteur;

        @Override
        public boolean hasNext() {
            return position > 0;
        }

        @Override
        public E next() {
            return tableau[--position];
        }
    }
}

Cette implémentation offre des performances proches de l'optimal pour les opérations courantes et un espace proportionnel à la taille de la collection. L'inconvénient est que les opérations empiler et depiler qui déclenchent un redimensionnement ont un coût proportionnel à la taille de la pile.

Pile basée sur une liste chaînée

Une alternative qui élimine le coût des redimensionnements.

package algorithm;

public class PileChainee<E>{
    private Noeud sommet;
    private int compteur;

    private class Noeud {
        E donnee;
        Noeud suivant;
    }

    public boolean estVide(){
        return sommet == null;
    }

    public int taille(){
        return compteur;
    }

    public void empiler(E element){
        Noeud ancienSommet = sommet;
        sommet = new Noeud();
        sommet.donnee = element;
        sommet.suivant = ancienSommet;
        compteur++;
    }

    public E depiler(){
        E element = sommet.donnee;
        sommet = sommet.suivant;
        compteur--;
        return element;
    }
}

Cette implémentation en liste chaînée permet de traiter tout type de données, utilise un espace strictement proporitonnel à la taille et garantit des temps d'opération constants.

Implémentation d'une file d'attente par liste chaînée

package algorithm;

public class FileChainee<E> {
    private Noeud tete;
    private Noeud queue;
    private int compteur;

    private class Noeud {
        E donnee;
        Noeud suivant;
    }

    public boolean estVide(){
        return tete == null;
    }

    public int taille(){
        return compteur;
    }

    public void enfiler(E element){
        Noeud ancienneQueue = queue;
        queue = new Noeud();
        queue.donnee = element;
        queue.suivant = null;
        if(estVide()){
            tete = queue;
        } else {
            ancienneQueue.suivant = queue;
        }
        compteur++;
    }

    public E defiler(){
        E element = tete.donnee;
        tete = tete.suivant;
        if(estVide()){
            queue = null;
        }
        compteur--;
        return element;
    }
}

Implémentation d'un sac par liste chaînée

La structure du sac est similaire à celle de la pile, sans opération de suppression. Une méthode ajouter insère au début de la liste chaînée.

package algorithm;

import java.util.Iterator;

public class SacChainee<E> implements Iterable<E> {
    private Noeud tete;

    private class Noeud {
        E donnee;
        Noeud suivant;
    }

    public void ajouter(E element){
        Noeud ancienneTete = tete;
        tete = new Noeud();
        tete.donnee = element;
        tete.suivant = ancienneTete;
    }

    @Override
    public Iterator<E> iterator() {
        return new IterateurListe();
    }

    private class IterateurListe implements Iterator<E>{
        private Noeud courant = tete;

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

        @Override
        public E next() {
            E element = courant.donnee;
            courant = courant.suivant;
            return element;
        }
    }
}

Le code itératif peut être adapté aux piles et files chaînées pour les rendre itérables, en appliquant la même logique de parcours de liste. La différence réside dans l'ordre de parcours pour l'utilisateur : LIFO pour la pile, FIFO pour la file.

En résumé, les listes chaînées constituent une alternative fondamentale aux tableaux pour le stockage structuré de données, offrant des compromis performants en espace et en temps pour ces structures de collection.