Une pile qui grandit

L'attribut taille est à la fois le nombre d'éléments et l'indice de la prochaine case libre. Quand le tableau est plein, on en crée un deux fois plus grand, on y recopie les éléments, et l'attribut désigne désormais le nouveau tableau.

class Pile {
    int[] elements = new int[2];
    int taille = 0;            // les éléments sont dans elements[0 : taille)

    boolean estVide() { return taille == 0; }

    void empiler(int v) {
        if (taille == elements.length) {          // plein : on double la capacité
            int[] plusGrand = new int[2 * elements.length];
            for (int i = 0; i < taille; i++) plusGrand[i] = elements[i];
            elements = plusGrand;
        }
        elements[taille] = v;
        taille++;
    }

    int depiler() {            // précondition : la pile n'est pas vide
        taille--;
        return elements[taille];
    }

    int sommet() { return elements[taille - 1]; }
}

public class Ex11Pile {
    public static void main(String[] args) {
        Pile p = new Pile();
        for (int i = 1; i <= 5; i++) p.empiler(i * i);
        System.out.println("capacité : " + p.elements.length + ", taille : " + p.taille);
        System.out.print("dépilés :");
        while (!p.estVide()) System.out.print(" " + p.depiler());
        System.out.println();
    }
}

capacité : 8, taille : 5
dépilés : 25 16 9 4 1

La capacité passe de $2$ à $4$ au troisième élément, puis à $8$ au cinquième. Les éléments ressortent dans l'ordre inverse de leur arrivée : le dernier empilé est le premier dépilé. Doubler la capacité, plutôt que l'augmenter d'une case, garantit que le coût total des recopies reste proportionnel au nombre d'éléments empilés ; c'est ce que fait la classe ArrayList de la bibliothèque (chapitre 12).