Previous Up Next

Chapitre 2  Piles et files

Les piles et les files sont des exemples de structures de données que faute de mieux, nous appellerons des sacs. Un sac offre trois opérations élémentaires :

  1. tester si le sac est vide,
  2. ajouter un élément dans le sac,
  3. retirer un élément du sac (tenter de retirer un élément d’un sac vide déclenche une erreur).

Le sac est une structure impérative : un sac se modifie au cours du temps. En Java, il est logique de représenter un sac (d’éléments E) par un objet (d’une classe BagE) qui possède trois méthodes.

class BagE⟩ {
  BagE⟩ { … } // Construire un sac vide
  boolean isEmpty() { … }
  void add(E e) { … }
  E remove() { … }
}

Ainsi on ajoute par exemple un élément e dans le sac b par b.add(e), ce qui modifie l’état interne du sac.

Piles et files se distinguent par la relation entre éléments ajoutés et éléments retirés. Dans le cas des piles, c’est le dernier élément ajouté qui est retiré. Dans le cas d’une file c’est le premier élément ajouté qui est retiré. On dit que la pile est une structure LIFO (last-in first-out), et que la file est une structure FIFO (first-in first-out).

Si on représente pile et file par des tas de cases, on voit que la pile possède un sommet, où sont ajoutés et d’où sont retirés les éléments, tandis que la file possède une entrée et une sortie.


Figure 2.1: Une pile (ajouter et retirer du même côté), une file (ajouter et retirer de côtés opposés).

Tout ceci est parfaitement conforme à l’intuition d’une pile d’assiettes, ou de la queue devant un guichet, et suggère fortement des techniques d’implémentations pour les piles et les files.

Exercice 2.1   Soit la méthode build suivante qui ajoute tous les éléments d’une liste dans un sac de int puis construit une liste en vidant le sac.
static List build(List p) {
  Bag bag = new Bag () ;
  for ( ; p != null ; p = p.next)
    bag.add(p.val) ;
  List r = null ;
  while (!bag.isEmpty())
    r = new List (bag.remove(), r) ;
  return r ;
}
Quelle est la liste renvoyée dans le cas où le sac est une pile, puis une file ?
Solution. Si le sac est une pile, alors build renvoie une copie de la liste p. Si le sac est une file, alors build renvoie une copie en ordre inverse de la liste p. □

Il y a un peu de vocabulaire spécifique aux piles et aux files. Traditionnellement, ajouter un élément dans une pile se dit empiler (push), et l’enlever dépiler (pop), tandis qu’ajouter un élément dans une file se dit enfiler, et l’enlever défiler.

2.1  À quoi ça sert ?

La file est peut-être la structure la plus immédiate, elle modélise directement les files d’attente gérées selon la politique premier-arrivé, premier-servi. La pile est plus informatique par nature. Dans la vie, la politique dernier-arrivé, premier-servi n’est pas très populaire. Elle correspond pourtant à une situation courante, la survenue de tâches de plus en plus urgentes. Les piles modélisent aussi tout système où l’entrée et la sortie se font par le même passage obligé : wagons sur une voie de garage, cabine de téléphérique, etc.

2.1.1  Premier arrivé, premier servi

Utiliser une file informatique est donc naturel lorsque l’on modélise une file d’attente au sens courant du terme. Considérons un exemple simple :

Notre objectif est d’écrire une simulation informatique afin d’estimer le rapport clients repartis sans être servis sur nombre total de clients, en fonction de la probabilité p.

Nous implémentons la simulation par une classe Simul (source Simul.java). Pour réaliser les tirages aléatoires nécessaires, nous employons une source pseudo-aléatoire, les objets de la classe Random du package java.util (voir B.1.4 pour la notion de package et B.6.3.1 pour une description de Random).

  // Source pseudo-aléatoire
  static private Random rand = new Random () ;

  // Loi uniforme sur [min…max[
  static private int uniform(int min, int max) {
    return min + rand.nextInt(max-min) ;
  }

  // Survenue d'un événement de probabilité prob ∈ [0…1]
  static private boolean occurs(double prob) {
    return rand.nextDouble() < prob ;
  }

Un client en attente est modélisé par un objet de la classe Client. Un objet Client est créé lors de l’arrivée du client au temps t, ce qui donne l’occasion de calculer l’heure à laquelle le client exaspéré repartira s’il il n’a pas été servi.

class Client {
  // Temps d'attente
  final static int waitMin = 120,  waitMax = 1800 ;

  int arrival, departure ;

  Client (int t) {
    arrival = t ; departure = t+Simul.uniform(waitMin, waitMax) ;
  }
}

Noter que les constantes qui gouvernent le temps d’attente sont des variables final de la classe Client.

L’implémentation d’une file sera décrite plus tard. Pour l’instant une file (de clients) est un objet de la classe Fifo qui possède les méthodes isEmpty, add et remove décrites pour les Bag de l’introduction.

La simulation est discrète. Durant la simulation, une variable tFree indique la date où le guichet sera libre. À chaque seconde t, il faut :

Le code qui réalise cette simulation naïve en donné par la figure 2.2. La méthode simul prend la probabilité d’arrivée d’un client en argument et renvoie le rapport clients non-servis sur nombre total de clients.


Figure 2.2: Code de la simulation.
  static double simul(double probNewClient) {
    Fifo f = new Fifo () ;
    int nbClients = 0, nbFedUp = 0 ;
    int tFree = 0 ; // Le guichet est libre au temps tFree 

    for (int t = 0 ; t < tMax ; t++) {
      // Tirer l'arrivée d'un client dans [t..t+1[
      if (occurs(probNewClient)) {
        nbClients++ ;
        f.add(new Client(t)) ;
      }
      if (tFree <= t) {
        // Le guichet est libre, servir un client (si il y en a encore un)
        while (!f.isEmpty()) {
          Client c = f.remove() ;
          if (c.departure >= t) { // Le client est encore là
            tFree = t + uniform(serviceMin, serviceMax) ;
            break ; // Sortir de la boucle while
          } else { // Le client était parti
            nbFedUp++ ;
          }
        }
      }
    }
    return ((double)nbFedUp)/nbClients ;
  }

Le code suit les grandes lignes de la description précédente. Il faut surtout noter comment on résout le problème d’une boucle while qui doit d’une part s’effectuer tant que la file n’est pas vide et d’autre part cesser dès qu’un client effectivement présent est extrait de la file (sortie par break). On note aussi la conversion de type explicite ((double)nbFedUp)/nbClients, nécessaire pour forcer la division flottante. Sans cette conversion on aurait la division euclidienne. La figure 2.3 donne les résultats de la simulation pour diverses valeurs de la probabilité prob. Il s’agit de moyennes sur dix essais.


Figure 2.3: Résultat de la simulation de la file d’attente

2.1.2  Utilisation d’une pile

Nous allons prendre en compte la nature très informatique de la pile et proposer un exemple plutôt informatique. Les calculatrices d’une célèbre marque états-unienne ont popularisé une notation des calculs dite parfois « polonaise inverse »1 ou plus généralement postfixe. Les calculs se font à l’aide d’une pile, les nombres sont simplement empilés, et l’exécution d’une opération op revient à d’abord dépiler un premier opérateur e1, puis un second e2, et enfin à empiler le résultat e2 op e1. Par exemple, la figure 2.4 donne les étapes successives du calcul 6 3 2 - 1 + / 9 6 - * exprimé en notation postfixe.


Figure 2.4: Calcul de l’expression postfixe 6 3 2 - 1 + / 9 6 - *

Le fabricant états-unien de calculatrices affirme qu’avec un peu d’habitude la notation postfixe est plus commode que la notation usuelle (dite infixe). C’est peut-être vrai, mais on peut en tout cas être sûr que l’interprétation de la notation postfixe par une machine est bien plus facile à réaliser que celle de la notation infixe. En voici pour preuve le programme Calc (source Calc.java) qui réalise le calcul postfixe donné sur la ligne de commande. Dans ce code les objets de la classe Stack sont des piles d’entiers.

class Calc {
  public static void main (String [] arg) {
    Stack stack = new Stack () ;
    for (int k = 0 ; k < arg.length ; k++) {
      String x = arg[k] ;
      if (x.equals("+")) {
        int i1 = stack.pop(), i2 = stack.pop() ;
        stack.push(i2+i1) ;
      } else if (x.equals("-")) {
        int i1 = stack.pop(), i2 = stack.pop() ;
        stack.push(i2-i1) ;
      …
      /* Idem pour "*" et "/" */
      …
      } else {
        stack.push(Integer.parseInt(x)) ;
      }
      System.err.println(x + " -> " + stack) ;
    }
    System.out.println(stack.pop()) ;
  }
}

Le source contient des messages de diagnostic (sur System.err on n’insistera jamais assez), un essai2 nous donne (le sommet de pile est à droite) :

% java Calc 6 3 2 - 1 + / 9 6 - ’*’
6 -> [6]
3 -> [6, 3]
  ⋮
6 -> [3, 9, 6]
- -> [3, 3]
* -> [9]
9

La facilité d’interprétation de l’expression postfixe provient de ce que sa définition est très opérationnelle, elle dit exactement quoi faire. Dans le cas de la notation infixe, il faut régler le problème des priorités des opérateurs. Par exemple si on veut effectuer le calcul infixe 1 + 2 * 3 il faut procéder à la multiplication d’abord (seconde opération), puis à l’addition (première opération) ; tandis que pour calculer 1 * 2 + 3, on effectue d’abord la première opération (multiplication) puis la seconde (addition). Par contraste, la notation postfixe oblige l’utilisateur de la calculatrice à donner l’ordre désiré des opérations (comme par exemple 1 2 3 * + et 1 2 * 3 +) et donc simplifie d’autant le travail de la calculatrice. Dans le même ordre d’idée, la notation postfixe rend les parenthèses inutiles (ou empêche de les utiliser selon le point de vue).

Exercice 2.2  Écrire un programme Infix qui lit une expression sous forme postfixe et affiche l’expression infixe (complètement parenthésée) qui correspond au calcul effectué par le programme Calc. On supposera donnée une classe Stack des piles de chaînes.
Solution. Il suffit tout simplement de construire la représentation infixe au lieu de calculer.
class Infix {
  public static void main (String [] arg) {
    Stack stack = new Stack () ;
    for (int k = 0 ; k < arg.length ; k++) {
      String x = arg[k] ;
      if (x.equals("+") || x.equals("-") || x.equals("*") || x.equals("/")) {
        String i1 = stack.pop(), i2 = stack.pop() ;
        stack.push("(" + i2 + x + i1 + ")") ;
      } else {
        stack.push(x) ;
      }
      System.err.println(x + " -> " + stack) ;
    }
    System.out.println(stack.pop()) ;
  }
}
L’emploi systématiques des parenthèses permet de produire des expressions infixes justes. Sans les parenthèses 1 2 3 - - et 1 2 - 3 - conduiraient au même résultat 1 - 2 - 3 qui serait incorrect pour 1 2 3 - -. Sur l’expression déjà donnée, on obtient :
% java Infix 6 3 2 - 1 + / 9 6 - ’*’
6 -> [6]
3 -> [6, 3]
  ⋮
6 -> [(6/((3-2)+1)), 9, 6]
- -> [(6/((3-2)+1)), (9-6)]
* -> [((6/((3-2)+1))*(9-6))]
((6/((3-2)+1))*(9-6))
Nous verrons plus tard que se passer des parenthèses inutiles ne se fait simplement qu’à l’aide d’une nouvelle notion. □

2.2  Implémentation des piles

Nous donnons d’abord deux techniques d’implémentation possibles, avec un tableau et avec une liste simplement chaînée. Ensuite, nous montrons comment utiliser la structure de pile toute faite de la bibliothèque.

2.2.1  Une pile dans un tableau

C’est la technique conceptuellement la plus simple, directement inspirée par le dessin de gauche de la figure 2.1.

Plus précisément, une pile (d’entiers) contient un tableau d’entiers, dont nous fixons la taille arbitrairement à une valeur constante. Seul le début du tableau (un segment initial) est utilisé, et un indice variable sp indique le pointeur de la pile. Le pointeur de pile indique la prochaine position libre dans la pile, mais aussi le nombre d’éléments présents dans la pile.

Dans ce schéma, seules les 5 premières valeurs du tableau sont significatives.

class Stack {
  final static int SIZE = 10; // assez grand ?

  private int sp ;
  private int [] t ;

  Stack () { // Construire une pile vide
    t = new int[SIZE] ; sp = 0;
  }
  ⋮
}

Notons que tous les champs des objets Stack sont privés (private, voir B.1.4). La taille des piles est donnée par une constante (final), statique puisque qu’il n’y a aucune raison de créer de nombreux exemplaires de cette constante.

À la création, une pile contient donc un tableau de SIZE=10 entiers. La valeur initiale contenue dans les cases du tableau est zéro (voir B.3.6.2), mais cela n’a pas d’importance ici, car aucune case n’est valide (sp est nul).

Il nous reste à coder les trois méthodes des objets de la classe Stack pour respectivement, tester si la pile est vide, empiler et dépiler.

  boolean isEmpty() { return sp == 0 ; }

  void push(int x) {
    if (sp >= SIZE) throw new Error ("Push : pile pleine") ;
    t[sp++] = x ; // Ou bien : t[sp] = x ; sp = sp+1 ;
  }

  int pop() {
    if (isEmpty()) throw new Error ("Pop : pile vide") ;
    return t[--sp] ; // Ou bien : sp = sp-1 ; return t[sp] ;
  }

La figure 2.5 donne un exemple d’évolution du tableau t et du pointeur de pile sp.


Figure 2.5: Empiler 9, puis dépiler.

Le code ci-dessus signale les erreurs en lançant l’exception Error (voir B.4.2), et emploie les opérateurs de post-incrément et pré-décrément (voir B.3.4). Notons surtout que toutes opérations sont en temps constant, indépendant du nombre d’éléments contenus dans la pile, ce qui semble attendu dans le cas d’opérations aussi simples que push et pop.

Les deux erreurs possibles "Push : pile pleine" et "Pop : pile vide" sont de natures bien différentes. En effet, la première découle d’une contrainte technique (la pile est insuffisamment dimensionnée), tandis que la seconde découle d’une erreur de programmation de l’utilisateur de la pile. Nous allons voir ce que nous pouvons faire au sujet de ces deux erreurs.

Commençons par l’erreur "pile pleine". Une première technique simple est de passer le bébé à l’utilisateur, en lui permettant de dimensionner la pile lui-même.

class Stack {
  …
  Stack (int sz) { t = new int[sz] ; sp = 0 ; }

  void push(int x) {
    if (sp >= t.length) throw new Error ("Push : pile pleine") ;
    t[sp++] = x ;
  }
  …
}

Ainsi, en cas de pile pleine, on peut toujours compter sur l’utilisateur pour recommencer avec une pile plus grande. Cela paraît abusif, mais c’est à peu près ce qui se passe au sujet de la pile des appels de méthode.

Mais en fait, les tableaux de Java sont suffisamment flexibles pour autoriser le redimensionnement automatique de la pile. Il suffit d’allouer un nouveau tableau plus grand, de recopier les éléments de l’ancien tableau dans le nouveau, puis de remplacer l’ancien tableau par le nouveau (et dans cet ordre, c’est plus simple).

  private void resize() {
    int [] newT = new int [2 * this.t.length] ; // Allouer le nouveau tableau
    for (int k = 0 ; k < sp ; k++)              // Recopier
      newT[k] = this.t[k] ;
    this.t = newT ;                             // Remplacer
  }

  void push(int x) {
    if (sp >= t.length) resize() ;
    t[sp++] = x ;
  }

Le redimensionnement automatique offre une flexibilité maximale. En contrepartie, il a un coût : un appel à push ne s’exécute plus en temps garanti constant, puisqu’il peut arriver qu’un appel à push entraîne un redimensionnement dont le coût est manifestement proportionnel à la taille de la pile.

Mais vu globalement sur une exécution complète, le coût de N appels à push reste de l’ordre de N. On dira alors que le coût amorti de push est constant. En effet, considérons N opérations push. Au pire, il n’y a pas de pop et la pile contient finalement N éléments pour une taille 2P du tableau interne, où 2P est la plus petite puissance de 2 supérieure à N. En outre, supposons que le tableau est redimensionné P fois (taille initiale 20). L’ordre de grandeur du coût cumulé de tous les push est donc de l’ordre de N (coût constant de N push) plus ∑k=1k=P 2k = 2P+1−1 (coût des P redimensionnements). Soit un coût final de l’ordre de N, puisque 2P < 2·N. Pour ce qui est de la mémoire, on alloue au total de l’ordre de 2P+1 cellules de mémoire, dont la moitié ont pu être récupérées par le garbage collector. Notons finalement que le coût amorti constant est assuré quand les tailles des tableaux successifs suivent une progression géométrique, dont la raison n’est pas forcément 2. En revanche, le coût amorti devient linéaire pour des tableaux les tailles suivent une progression arithmétique. Pour cette raison, écrire int [] newT = new int [t.length + K] est rarement une bonne idée.

Abordons maintenant l’erreur "pile vide". Ici, il n’y a aucun moyen de supprimer l’erreur, car rien n’empêchera jamais un programmeur maladroit ou fatigué de dépiler une pile vide. Mais on peut signaler l’erreur plus proprement, ce qui donne la possibilité au programmeur fautif de la réparer. Pour ce faire, il convient de lancer, non plus l’exception Error, mais une exception spécifique. Les exceptions sont complètement décrites dans l’annexe Java en B.4. Ici, nous nous contentons d’une présentation minimale. La nouvelle exception StackEmpty se définit ainsi.

class StackEmpty extends Exception { }

C’est en fait une déclaration de classe ordinaire, car une exception est un objet d’une classe un peu spéciale (voir B.4.2). La nouvelle exception se lance ainsi.

  int pop () throws StackEmpty {
    if (isEmpty()) throw new StackEmpty () ;
    return t[--sp] ;
  }

On note surtout que la méthode pop déclare (par throws, noter le « s ») qu’elle peut lancer l’exception StackEmpty. Cette déclaration est ici obligatoire, parce que StackEmpty est une Exception et non plus une Error. La présence de la déclaration va obliger l’utilisateur des piles à s’occuper de l’erreur possible.

Pour illustrer ce point revenons sur l’exemple de la calculatrice Calc (voir 2.1.2). La calculatrice emploie une pile stack, elle dépile et empile directement par stack.pop() et stack.push(…). Nous supposons que la classe Stack est telle que ci-dessus (avec une méthode pop qui déclare lancer StackEmpty) et que nous ne pouvons pas modifier son code. Pour organiser un peu la suite, nous ajoutons deux nouvelles méthodes statiques push et pop à la classe Calc, et transformons les appels de méthode dynamiques en appels statiques.

class Calc {
  static int pop(Stack stack) { return stack.pop() ; }

  static void push(Stack stack, int x) { stack.push(x) ; }

  public static void main (String [] arg) {
    …
    if (x.equals("+")) {
      int i1 = pop(stack), i2 = pop(stack) ;
      push(stack, i2+i1) ;
    …
  }
}

Le compilateur refuse le programme ainsi modifié. Il exige le traitement de StackEmpty qui peut être lancée par stack.pop(). Traiter l’exception peut se faire en attrapant l’exception, par l’instruction try.

  static int pop(Stack stack) {
    try {
      return stack.pop() ;
    } catch (StackEmpty e) {
      return 0 ;
    }
  }

L’effet est ici que si l’instruction return stack.pop() échoue parce que l’exception StackEmpty est lancée, c’est alors l’instruction return 0 qui s’exécute. Cela revient à remplacer la valeur « exceptionnelle » StackEmpty par la valeur plus normale 0 (voir B.4.1 pour les détails). Par conséquent, une pile vide se comporte comme si elle contenait une infinité de zéros.

On peut aussi décider de ne pas traiter l’exception, mais alors il faut signaler que les méthodes Calc.pop puis main peuvent lancer l’exception StackEmpty, même si c’est indirectement.

class Calc {
  static int pop(Stack stack) throws StackEmpty { return stack.pop() ; }

  public static void main (String [] arg) throws StackEmpty {
    …
  }
}

Si l’exception survient, elle remontera de méthode en méthode et fera finalement échouer le programme. En fait, comme les déclarations throws, ici obligatoires, sont quand même pénibles, on a plutôt tendance à faire échouer le programme explicitement dès que l’exception atteint le code que l’on contrôle.

  static int pop(Stack stack) {
    try {
      return stack.pop() ;
    } catch (StackEmpty e) {
      System.err.println("Adieu : pop sur pile vide") ;
      System.exit(2) ; // Arrêter le programme immédiatement (voir B.6.1.5)
      return 0 ; // Le compilateur exige ce return jamais exécuté
    }
  }

Bien sûr, si on veut que dépiler une pile vide provoque un arrêt du programme, il aurait été plus court de lancer new Error ("Pop : pile vide") dans la méthode pop des objets Stack. Mais nous nous sommes interdit de modifier la classe Stack.

2.2.2  Une pile dans une liste

C’est particulièrement simple. En effet, les éléments sont empilés et dépilés du même côte de la pile, qui peut être le début d’une liste. On suppose donc donnée une classe des listes (d’entiers). Et on écrit :

class Stack {
  private List p ;

  Stack () { p = null ; }

  boolean isEmpty() { return p == null ; }

  void push(int x) { p = new List (x, p) ; }

  int pop() throws StackEmpty {
    if (p == nullthrow new StackEmpty () ;
    int r = p.val ;
    p = p.next ;
    return p ;
  }
}

Voici un exemple d’évolution de la liste p.

2.2.3  Les piles de la bibliothèque

Il existe déjà une classe des piles dans la bibliothèque, la classe Stack du package java.util, implémentée selon la technique des tableaux redimensionnés. Mais une classe des piles de quoi ?

En effet, dans les deux sections précédentes, nous n’avons codé que des piles de int en nous disant que pour coder une pile, par exemple de String, il nous suffisait de remplacer int par String partout dans le code. Il est clair qu’une telle « solution » ne convient pas à une classe de bibliothèque qui est compilée par le fabricant. Après bien des hésitations, Java a résolu ce problème en proposant des classes génériques, ou paramétrées. La classe Stack est en fait une classe Stack<E>, où E est n’importe quelle classe, et les objets de la classe Stack<E> sont des piles d’objets de la classe E. Formellement, Stack n’est donc pas exactement une classe, mais plutôt une fonction des classes dans les classes. Informellement, on peut considérer que nous disposons d’une infinité de classes Stack<String>, Stack<List> etc. Par exemple on code facilement la pile de chaînes de l’exercice 2.2 comme un objet de la classe java.util.Stack<String> (source Infix.java).

import java.util.* ;
class Infix {
  public static void main (String [] arg) {
    Stack<String> stack = new Stack<String> () ;
    …
        String i1 = stack.pop(), i2 = stack.pop() ;
        stack.push("(" + i2 + x + i1 + ")") ;
    …
  }
}

(Pour import, voir B.3.5.) Cela fonctionne parce que la classe Stack<E> possède bien des méthodes pop et push, où par exemple pop() renvoie un objet E, ici un String.

Comme le paramètre E dans Stack<E> est une classe, il n’est pas possible de fabriquer des piles de int. Plus généralement, il est impossible de fabriquer des piles de scalaires (voir B.3.1 pour la définition des scalaires). Mais la bibliothèque fournit une classe associée par type scalaire, par exemple Integer pour int. Un objet Integer n’est guère plus qu’un objet dont une variable d’instance (privée) contient un int (voir B.6.1.1). Il existe deux méthodes pour convertir un scalaire int en un objet Integer et réciproquement, valueOf (logiquement statique) et intValue (logiquement dynamique). De sorte qu’écrire la calculatrice Calc (voir 2.1.2) avec une pile de la bibliothèque semble assez lourd au premier abord.

import java.util.* ;
class Calc {
  public static void main (String [] arg) {
    Stack<Integer> stack = new Stack<Integer> () ;
    …
        int i1 = stack.pop().intValue(), i2 = stack.pop().intValue() ;
        stack.push(Integer.valueOf(i2+i1)) ;
    …
  }
}

Mais en fait, le compilateur Java sait insérer les appels aux méthodes de conversion automatiquement, c’est-à-dire que l’on peut écrire plus directement.

import java.util.* ;
class Calc {
  public static void main (String [] arg) {
    Stack<Integer> stack = new Stack<Integer> () ;
    …
        int i1 = stack.pop(), i2 = stack.pop() ;
        stack.push(i2+i1) ;
    …
  }
}

Tout semble donc se passer presque comme si il y avait une pile de int ; mais attention, il s’agit bien en fait d’une pile de Integer. Tout se passe plutôt comme si le compilateur traduisait le programme avec les int vers le programme avec les Integer, et c’est bien ce dernier qui s’exécute, avec les conséquences prévisibles sur la performance en général et la consommation mémoire en particulier.

2.3  Implémentation des files

Comme pour les piles, nous présentons trois techniques, tableaux, listes et bibliothèque.

2.3.1  Une file dans un tableau

L’idée, conceptuellement simple mais un peu délicate à programmer, est de gérer deux indices : in qui marque la position où ajouter le prochain élément et out qui marque la position d’où proviendra le prochain élément enlevé. L’indice out marque le début de la file et in sa fin. Autrement dit, le contenu de la file va la case d’indice out à la case qui précède la case d’indice in.

Dans le schéma ci-dessus, les cases valides sont grisées, de sorte que la file ci-dessus contient les entiers 2, 7, 0, 9 (dans l’ordre, 2 est le premier entré et 9 le dernier entré). Au cours de la vie de la file, les deux indices sont croissants. Plus précisément, on incrémente in après ajout et on incrémente out après suppression. Lorsqu’un indice atteint la fin du tableau, il fait tout simplement le tour du tableau et repart à zéro. Il en résulte que l’on peut avoir out < in. Par exemple, voici une autre file contenant cette fois 2, 0, 4, 6, 2, 7.

Le tableau d’une file est un tableau circulaire, que l’on parcourt en incrémentant un indice modulo n, où n est la taille du tableau. Par exemple pour parcourir le contenu de la file, on parcourt les indice de out à (in−1) mod n. Soit un parcours de 1 à 4 dans le premier exemple et de 7 à 2 dans le second.

Une dernière difficulté est de distinguer entre file vide et file pleine. Comme le montre le schéma suivant, les deux indices out et in n’y suffisent pas.

Ici, out (début) et in (fin) valent tous deux 4. Pour connaître le contenu de la file il faut donc parcourir le tableau de l’indice 4 à l’indice 3. Une première interprétation du parcours donne une file vide, et une seconde une file pleine.


Figure 2.6: Implémentation d’une file dans un tableau
class FifoEmpty extends Exception { }

class Fifo {
  final static int SIZE=10 ;
  private int in, out, nb ;
  private int [] t ;

  Fifo () { t = new int[SIZE] ; in = out = nb = 0 ; }

  /* Increment modulo la taille du tableau t, utilisé partout */
  private int incr(int i) { return (i+1) % t.length ; }

  boolean isEmpty() { return nb == 0 ; }

  int remove() throws FifoEmpty {
    if (isEmpty()) throw new FifoEmpty () ;
    int r = t[out] ;
    out = incr(out) ; nb-- ; // Effectivement enlever
    return r ;
  }

  void add(int x) {
    if (nb+1 >= t.length) resize() ;
    t[in] = x ;
    in = incr(in) ; nb++ ; // Effectivement ajouter
  }

  private void resize() {
    int [] newT = new int[2*t.length] ; // Allouer
    int i = out ; // indice du parcours de t
    for (int k = 0 ; k < nb ; k++) {    // Copier
      newT[k] = t[i] ;
      i = incr(i) ;
    }
    t = newT ; out = 0 ; in = nb ;     // Remplacer
  }

/* Méthode toString, donne un exemple de parcours de la file */
  public String toString() {
    StringBuilder b = new StringBuilder () ;
    b.append("[") ;
    if (nb > 0) {
      int i = out ;
      b.append(t[i]) ; i = incr(i) ;
      for ( ; i != in ; i = incr(i))
        b.append(", " + t[i]) ;
    }
    b.append("]") ;
    return b.toString() ;
  }
}

On résout facilement la difficulté par une variable nb supplémentaire, qui contient le nombre d’éléments contenus dans la file. Une autre solution aurait été de décréter qu’une file qui contient n−1 éléments est pleine. On teste en effet cette dernière condition sans ambiguïté par in+1 congru à out modulo n. Nous choisissons la solution de la variable nb, car connaître simplement le nombre d’éléments de la file est pratique, notamment pour gérer le redimensionnement.

La figure 2.6 donne la classe Fifo des files implémentées par un tableau, avec redimensionnement automatique. Un point clé de ce code est la gestion des indices in et out. Pour ajouter un élément dans la file, in est incrémenté (modulo n). Par exemple, voici l’ajout (méthode add) de l’entier 11 dans une file.

Pour supprimer un élément, on incrémente out. Par exemple, voici la suppression du premier élément d’une file (la méthode remove renvoie ici 2).

Le redimensionnement (méthode resize) a pour effet de tasser les éléments au début du nouveau tableau. Voici l’exemple de l’ajout de 13 dans une file pleine de taille 4.

Avant ajout la file contient 7, 11, 6, 2, après ajout elle contient 7, 11, 6, 2, 13.

Le code du redimensionnement (méthode resize) est un peu simplifié par la présence de la variable nb. Pour copier les éléments de t dans newT, le contrôle est assuré par une simple boucle sur le compte des éléments transférés. Un contrôle sur l’indice i dans le tableau t serait plus délicat. La méthode toString donne un exemple de ce style de parcours du contenu de la file, entre les indices out (inclus) et in (exclu), qui doit particulariser le cas d’une file vide et effectuer la comparaison à in à partir du second élément parcouru (à cause du cas de la file pleine).

2.3.2  Une file dans une liste

L’implémentation est conceptuellement simple. Les éléments de la file sont dans une liste, on enlève au début de la liste et on ajoute à la fin de la liste. Pour garantir des opérations en temps constant, on utilise une référence sur la dernière cellule de liste. Nous avons déjà largement exploité cette idée, par exemple pour copier une liste itérativement (voir l’exercice 1.2). Nous nous donnons donc une référence out sur la première cellule de la liste, et une référence in sur la dernière cellule.

La file ci-dessus contient donc les entiers 2, 7, 0, 9 dans cette ordre. Une file vide est logiquement identifiée par une variable out valant null. Par souci de cohérence in vaudra alors aussi null.

class Fifo {
  private List out, in ;

  Fifo () { out = in = null ; }

  boolean isEmpty() { return out == null ; }

  int remove() throws FifoEmpty {
    if (isEmpty()) throw new FifoEmpty () ;
    int r = out.val ;
    out = out.next ;
    if (out == null) in = null ; // La file est vide
    return r ;
  }

  void add(int x) {
    List last = in ;
    in = new List(x, null) ;
    if (last == null) { // La file était vide
      out = in ;
    } else {
      last.next = in ;
    }
  }
}

On constate que le code est bien plus simple que dans le cas des tableaux (figure 2.6). La méthode remove est essentiellement la même que la méthode pop des piles (voir 2.2.2), car les deux méthodes réalisent la même opération d’enlever le premier élément d’une liste. La méthode add est à peine plus technique, voici par exemple la suite des états mémoire quand on ajoute 3 à la file déjà dessinée. La première instruction List last = in garde une copie de la référence in.

L’instruction suivante in = new List (x, null) alloue la nouvelle cellule de liste.

Et enfin, l’instruction last.next = in, ajoute effectivement la nouvelle cellule pointée par in à la fin de la liste-file.

2.3.3  Les files de la bibliothèque

Le package java.util de la bibliothèque offre plusieurs classes qui peuvent servir comme une file, même si nous ne respectons pas trop l’esprit dans lequel ces classes sont organisées. (Les files de la bibliothèque Queue ne sont pas franchement compatibles avec notre modèle simple des files).

Nous nous focalisons sur la classe LinkedList. Comme le nom l’indique à peu près, cette classe est implémentée par une liste chaînée. Elle offre en fait bien plus que la simple fonctionnalité de file, mais elle possède les méthodes add et remove des files. La classe LinkedList est générique, comme la classe Stack de la section 2.2.3, ce qui la rend relativement simple d’emploi.

Exercice 2.3   Les objets LinkedList implémentent en fait les « queues à deux bouts » (double ended queue), qui offrent deux couples de méthodes addFirst/removeFirst et addLast/removeLast pour ajouter/enlever respectivement au début et à la fin de queue. Afin d’assurer des opérations en temps constant, la classe de bibliothèque repose sur les listes doublement chaînées. Voici une classe DeList des cellules de liste doublement chaînée.
class DeList {
  int val ; DeList next, prev ;

  DeList (int val, DeList next, DeList prev) {
    this.val = val ; this.next = next ; this.prev = prev ;
  }
}
Le chaînage double permet de parcourir la liste de la première cellule à la dernière en suivant les champs next, et de la dernière à la première en suivant le champ prev.
Autrement dit, si p est une référence vers une cellule de liste doublement chaînée qui n’est pas la première, on a l’égalité p.prev.next == p ; et si p pointe vers la première cellule, on a p.prev == null. De même, si p pointe vers une cellule qui n’est pas la dernière, on a p.next.prev == p ; et si p pointe vers la dernière cellule, on a p.next == null.
Solution.

Figure 2.7: Classe des queues à deux bouts
class DeQueue {
  private DeList fst, lst ; // First and last cell

  DeQueue () { fst = lst = null ; }

  boolean isEmpty() { return fst == null ; }

  void addFirst(int x) {
    fst = new DeList(x, fst, null) ;
    if (lst == null) {
      lst = fst ;
    } else {
      fst.next.prev = fst ;
    }
  }

  void addLast(int x) {
    lst = new DeList(x, null, lst) ;
    if (fst == null) {
      fst = lst ;
    } else {
      lst.prev.next = lst ;
    }
  }

  int removeFirst() {
    if (fst == nullthrow new Error ("removeFirst: empty queue") ;
    int r = fst.val ;
    fst = fst.next ;
    if (fst == null) {
      lst = null ;
    } else {
      fst.prev = null ;
    }
    return r ;
  }

  int removeLast() {
    if (lst == nullthrow new Error ("removeLast: empty queue") ;
    int r = lst.val ;
    lst = lst.prev ;
    if (lst == null) {
      fst = null ;
    } else {
      lst.next = null ;
    }
    return r ;
  }
}

Décomposons une opération, par exemple addFirst, en ajoutant 3 au début de la queue déjà dessinée. Dans un premier temps on peut allouer la nouvelle cellule, avec un champ next correct (voir push en 2.2.2). Le champ prev peut aussi être initialisé immédiatement à null.
Reste ensuite à ajuster le champ prev de la nouvelle seconde cellule de la liste, cellule accessible par fst.next ((fst.next).prev = fst).
Pour supprimer par exemple le dernier élément de la queue, il suffit de changer le contenu de lst (lst = lst.prev).
Reste ensuite à ajuster le champ next de la nouvelle dernière cellule (lst.next = null).
Le code, pas si difficile est donné par la figure 2.7. Une fois compris le mécanisme d’ajout et de retrait des cellules, le point délicat est de bien gérer le cas de la queue vide qui correspond à fst et lst tous deux égaux à null. □

2.4  Type abstrait, choix de l’implémentation

Nous avons présenté trois façons d’implémenter piles et files. Il est naturel de se demander quelle implémentation choisir. Mais nous tenons d’abord à faire remarquer que, du strict point de vue de la fonctionnalité, la question ne se pose pas. Tout ce qui compte est d’avoir une pile (ou une file). En effet, les trois implémentations des piles offrent exactement le même service, de sorte que le choix d’une implémentation particulière n’a aucun impact sur le résultat d’un programme qui utilise une pile. La pile qui est définie exclusivement par les services qu’elle offre est un exemple de type de données abstrait.

Java offre des traits qui permettent de fabriquer des types abstraits qui protègent leur implémentation des interventions intempestives. Dans nos deux classes Stack, le tableau (ainsi que le pointeur de pile sp) et la liste sont des champs privés. Un programme qui utilise nos piles doit donc le faire exclusivement par l’intermédiaire des méthodes push et pop. Champs privés et méthodes accessibles correspondent directement à la notion de type abstrait défini par les services offerts.

Il faut toutefois remarquer que, du point de vue du langage de programmation, l’existence des deux (trois en fait) méthodes reste pour le moment une convention : nous avons conventionnellement appelé Stack la classe des piles et conventionnellement admis qu’elle possède ces trois méthodes :

  boolean isEmpty() { … }
  void push(int x) { … }
  int pop() throws StackEmpty { … }

Il en résulte par exemple que nous ne pouvons pas encore mélanger les piles en tableau et les piles en liste dans le même programme, à moins de changer le nom des classes ce qui contredirait l’idée d’un type abstrait. Nous verrons au chapitre suivant comment procéder, à l’aide des interfaces.

Répondons maintenant sérieusement à la question du choix de l’implémentation. Dans disons 99 % des cas pour les files et 90 % des cas pour les piles, il faut choisir la classe de bibliothèque, parce que c’est la solution qui demande d’écrire le moins de code. La différence de pourcentage s’explique en comparant le temps de lecture de la documentation au temps d’écriture d’une classe des files ou des piles, et parce que la classe des piles est quand même simple à écrire.

La bibliothèque peut ne pas convenir pour des raisons d’efficacité : le code est trop lent ou trop gourmand en mémoire pour notre programme particulier et nous pouvons faire mieux que lui. Par exemple, le code de bibliothèque entraîne la fabrication d’objets Integer en pagaille, et une pile de scalaires se montre au final plus rapide. La classe de bibliothèque peut aussi ne pas convenir parce qu’elle n’offre pas la fonctionnalité inédite dont nous avons absolument besoin (par exemple une inversion complète de la pile), ou plus fréquemment parce que programmer cette fonctionnalité de la façon autorisée par la structuration de la bibliothèque serait trop compliqué, trop coûteux, ou tout simplement impossible avec notre connaissance limitée de Java.

Il reste alors à choisir entre tableaux et listes. Il n’y a pas de réponse toute faite à cette dernière question. En effet, d’une part, la difficulté de l’écriture d’un programme dépend aussi du goût et de l’expérience de chacun ; et d’autre part, l’efficacité respective de l’une ou de l’autre technique dépend de nombreux facteurs, (la pile croît-elle beaucoup, par exemple) et aussi de l’efficacité de la gestion de la mémoire par le système d’exécution de Java. Toutefois, dans le cas où le redimensionnement est inutile, le choix d’une pile-tableau s’impose probablement, puisque simplicité et efficacité concordent. Dans le cas général, on peut tout de même prévoir qu’utiliser les listes demande d’écrire un peu moins de code que d’utiliser les tableaux (redimensionnés). On peut aussi penser que les tableaux seront un plus efficaces que les listes, ou en tout cas utiliseront moins de mémoire au final. En effet, fabriquer une pile-tableau de N éléments demande d’allouer log2 N objets (tableaux) contre N objets (cellules de listes) pour une pile-liste. Or, allouer un objet est une opération chère.

Supposons qu’un objet occupe deux cases de mémoire en plus de l’espace nécessaire pour ses données (c’est une hypothèse assez probable pour Java). Une cellule de liste occupe donc 4 cases et un tableau de taille n occupe 3+n cases (dont une case pour la longueur). Pour un programme effectuant au total P push, la pile-liste aura alloué au total 4·P cases de mémoire, tandis que la pile-tableau aura alloué entre une (si la taille initiale du tableau est 1, et que le programme alterne push et pop) et environ 4·P + 3·log2 P cases de mémoire (dans le cas où aucun pop ne sépare les push et où le tableau est redimensionné par le dernier push). La pile-tableau n’alloue donc jamais significativement plus de mémoire que la pile-liste, et généralement plutôt moins.

Un autre coût intéressant est l’empreinte mémoire, la quantité de mémoire mobilisée à un instant donné. Une pile-file de N éléments mobilise 4·N cases de mémoire. Une pile-tableau mobilise entre 3+N et un nombre arbitrairement grand de cases de mémoire (le nombre arbitraire correspond à la taille du tableau lorsque, dans le passé, la pile a atteint sa taille maximale). Un nouvel élément intervient donc dans le choix de l’implémentation : la profondeur maximale de pile au cours de la vie du programme. Si cette profondeur reste raisonnable le choix de la pile-tableau s’impose, autrement le choix est moins net, mais la flexibilité de l’allocation petit-à-petit des cellules de la pile-liste est un avantage. On peut aussi envisager de réduire la taille du tableau interne de la pile tableau, par exemple en réduisant le tableau de la moitié de sa taille quand il n’est plus qu’au quart plein. Mais il faut alors y regarder à deux fois, notre classe des piles commence à devenir compliquée est tout ce code ajouté entraîne un prix en temps d’exécution.


1
En hommage au philosophe et mathématicien Jan Łukasiewicz qui a introduit cette notation dans les années 20.
2
Il faut citer le symbole * par exemple par ’*’, afin d’éviter son interprétation par le shell, voir 6.3.1.

Previous Up Next