Piles

   

On a vu au § 1.6, page  que les cadres d'invocation des méthodes sont des blocs de mémoire << empilés >> les uns sur les autres, le dernier empilé étant le premier retiré (en anglais last in, first out ou LIFO), comme une vulgaire pile d'assiettes. Les piles permettent également de parcourir un graphe en profondeur sans récursivité. La figure 2.11 montre le fonctionnement d'une pile. Les quatre opérations sur une pile sont : ajouter un élément au sommet de la pile (ou empiler), lire la valeur se trouvant au sommet d'une pile non-vide, tester si une pile est vide, retirer l'élément au sommet de la pile (ou dépiler). En anglais, << pile >> se dit stack et les opérations portent respectivement les noms push, top, isEmpty, pop. Voici l'interface des piles, en Java :

interface Pile {
  boolean estVide();
  void empiler(Object o);
  Object sommet();
  Object dépiler();
}

On va implémenter les piles en utilisant les fonctionnalités des listes et leur implémentation sous forme de tableau fournie par l'API Java :

import java.util.List;
import java.util.ArrayList;

class PileParListe implements Pile {

  private List contenu;

  PileParListe() {
    contenu = new ArrayList(); 
  }

  public boolean estVide() {
    return contenu.isEmpty();
  }

  public void empiler(Object o) {
    contenu.add(o);
  }
  
  public Object sommet() {
      return contenu.get(contenu.size()-1);
  }

  public Object dépiler() {
      return contenu.remove(contenu.size()-1);
  } 
}