Planche : 1


Détour : les sacs

Les piles et les files sont des cas particuliers des sacs.

Les opérations suivantes sont définies sur les sacs

Le sac typique (en style objet) :

class Bag {
  …
  Bag () { … }
  boolean isEmpty() { … }
  void put(Object o) { … }
  Object get() { … }
}

Remarquer : Le sac est une structure mutable.


Planche : 2


Les piles et les files

Piles et files sont des sacs munis de règles supplémentaires reliant les sorties et les entrées :


Planche : 3


La pile

Planche : 4


La pile

Planche : 5


La file

Planche : 6


La file

Planche : 7


À quoi ça sert ?

La file est la structure la plus intuitive.

La file sert par exemple, dans un système d’exploitation, à servir des demandes d’impression dans l’ordre.


Planche : 8


À quoi ça sert ?

La pile est la structure la plus « informatique ».

Son besoin se fait clairement sentir dans la situation suivante…


Planche : 9


Autre utilisation des piles

Évaluation des expressions arithmétiques.

Soit les piles d’entiers :

class Stack {
  …
  Stack () { … }
  boolean isEmpty() { … }
  void push(int i) { … }
  int pop() { … }
}

Les calculettes en notation postfixe (ou « polonaise ») fonctionnent à l’aide d’une pile, selon ce principe :


Planche : 10


Exemples de calcul en notation postfixe

Calculer 1 + (2 × 3) : 1 2 3 * + (ou 2 3 * 1 + d’ailleurs).

 
→ 1 →
→ 2 →
→ 3 →
→ × →
→ + →

Calculer (1 + 2) × 3 : 1 2 + 3 *

 
→ 1 →
→ 2 →
→ + →
→ 3 →
→ × →

Planche : 11


Une réalisation de la calculette
class Calc {
  public static void main (String [] arg) {
    Stack stack = new Stack () ;
    for (int i = 0 ; i < arg.length ; i++) {
      String cmd = arg[i] ;
      if (cmd.equals("+")) {
        int x = stack.pop(), y = stack.pop() ;
        stack.push(y+x) ;
      } else if …
      // Idem pour "*", "/", "-"
      } else {
        stack.push(Integer.parseInt(cmd)) ; // doc
      }
    }
    System.out.println(stack.pop()) ;
  }
}

Planche : 12


Exécution de Calc
% java Calc 1 2 + 3 '*'
1 -> [1]
2 -> [1, 2]
+ -> [3]
3 -> [3, 3]
* -> [9]
9

Mais…

% java Calc 1 +        
1 -> [1]
Exception in thread "main" java.util.EmptyStackException
        at java.util.Stack.peek(Stack.java:79)
        at java.util.Stack.pop(Stack.java:61)
        at Calc.main(Calc.java:9)

Planche : 13


Précisions sur la notation postfixe

Par définition, une notation postfixe est une suite de symboles P.

P=int
 P1   P2   op

Par exemple :

 
 
0


 
 
 
1   2   +


  
 
3


  *


  -


Par définition, la valeur d’une notation postfixe est :

v(int)=int
v(P1   P2   op)=op(v(P1), v(P2))

Planche : 14


Correction du calcul

Modélisons le programme Calc. Son état : ⟨  I  •  S  ⟩.

Une action consiste à lire le symbole.

  
  int  I  •  S  

  I  •  S,  int  
  
  op  I  •  S,  v1,  v2  

  I  •  S,  op(v1v2)  

Théorème  Si I est une notation postfixe P, alors la pile S contient v(P) à la fin.


  P  •     
* 
     •  v(P)  

Planche : 15


Lemme  Pour toute suite de symboles I, toute pile S, et toute notation postfixe :


  P  I  •  S  
*
  I  •  Sv(P)  

Démonstration  Par induction (sur P). Dans le cas P = P1   P2   op.


  P   I  •  S  
=

  P1   P2   op    I  •  S  
 *

  P2  op    I  •  S ,  v(P1)  
 *

  op    I  •  S ,  v(P1) ,  v(P2)  
 

  I  •  S ,  op(v(P1), v(P2))  
 =

  I  •  S ,  v(P)  

Planche : 16


Pile et appel de méthode

Revenons sur la fusion récursive qui échoue par « débordement de la pile » pour des listes assez longues.

static List merge(List xsList ys) {
  if (xs == null) {
    return ys ;
  } else if (ys == null) {
    return xs ;
  } // NB: désormais xs != null && ys != null 
    else if (xs.val <= ys.val) {
    return new List (xs.valmerge(xs.nextys)) ;
  } else { // NB: ys.val < xs.val
    return new List (ys.valmerge(xsys.next)) ;
  }
}

Planche : 17


Appel de méthode

En simplifiant un peu.


Planche : 18


Dans le cas qui nous occupe

Nous allons modéliser un processeur en Java, et examiner ce que fait le code compilé de merge.

merge// « Étiquette » de début de la méthode.
/* La pile S est P ,  ret ,  xs ,  ys
   Il faut rendre P ,  merge(xs, ys) */

  ys = S.pop() ;
  xs = S.pop() ;
  if (xs == null) {
    lab = S.pop() ; S.push(ys) ; gotolab ;
  } …

Planche : 19


Appel récursif
  ⋮
/* La pile S est P ,  ret
   Il faut rendre P ,  merge(xs, ys) */

  if (xs.val <= ys.val) {
     S.push(xs.val) ; // Sauver xs.val dans la pile
     S.push(lab1) ; S.push(xs.next) ; S.push(ys) ;
     // S est P ,  xs.val ,  lab1 ,  xs.next ,  ys
     goto merge ; // Appel récursif
   lab1:
     // S est P ,  merge(xs.next, ys)
     r = S.pop() ;          // Résultat de l'appel
     xsPointVal = S.pop() ; // xs.val sauvé avant l'appel
     lab = S.pop() ;        // Étiquette de retour
     S.push(new List (xsPointValr)) ;
     gotolab ; // La pile est P ,  merge(xs, ys) ok.
  } …

Planche : 20


Codage des piles (d’entiers)

Le principe est le suivant :

class Stack {
  private List me ;
  Stack () { me = null ;  }
  boolean isEmpty() { return me == null ; }
  …
}

Planche : 21


Diversion : modificateurs de visibilité

Le champ me des objets Stack est déclaré private.

class Stack {
  private List me ; …

En effet, il ne faut pas que qui que ce soit d’autre (que l’objet Stack) utilise me.

Les modificateurs, du plus restrictif au plus permissif.

Puisque nous n’utilisons ni package, ni héritage, on se limite à private et à rien. (sauf pour public static void main).


Planche : 22


Empiler : ajouter au début
  me = new List (4, me) ;

Planche : 23


Dépiler : enlever du début
   me = me.next ;

Planche : 24


Code de push et pop
  void push(int i) {
    me = new List (ime) ;
  }

  int pop() {
    if (me == nullthrow new Error("Pile Vide") ;
    int r = me.val ;
    me = me.next ;
    return r ;
  }

Remarquer  « throw new Error() » qui interrompt le programme en lançant (instruction throw) une exception (ici objet de la classe Error).


Planche : 25


Diversion : programmation des erreurs

Si l’effet attendu d’une erreur est de faire échouer le programme, on se demande bien l’intérêt de l’exception.

   System.err.println("Erreur : pile vide") ; // NB sortie d'erreur
   System.exit(2) ;                           // Tout arrêter

Mais on veut pouvoir réparer les erreurs dans le programme.

Or, une exception est un résultat innattendu, qui passe par tous les appels en attente.

% java Calc 1 +        
1 -> [1]
Exception in thread "main" java.util.EmptyStackException
        at java.util.Stack.peek(Stack.java:79)
        at java.util.Stack.pop(Stack.java:61)
        at Calc.main(Calc.java:9)

Et on peut « attraper » l’erreur au passage.


Planche : 26


Signaler une erreur

Déclarer une classe de nos exceptions (plus propre).

class StackEmpty { } extends Exception

Lancer notre exception.

 int pop() throws StackEmpty { // Obligatoire ici
    if (me == nullthrow new StackEmpty () ;
  …

Note : Le code la classe Stack se contente de signaler l’erreur.

Cette classe n’est pas modifiable (par ex. code de la bibliothèque).


Planche : 27


Traiter l’erreur

Comme la vraie calculette HP: une pile « vide » contient en fait 0, 0, …

Attraper l’exception (∼ résultat exceptionnel) pour la rempacer par un résultat normal.

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

Et appeler popStack(s) en place de s.pop(). dans Calc.


Planche : 28


Réalisation des files

Le principe est le suivant, l’objet file maintient une liste (privée) d’entiers.

Pour réaliser ces opérations en temps constant il nous faut deux références :

class Fifo {
  private List inout ;
  Fifo () { in = out = null ; }
  boolean isEmpty() { return in == null && out == null ; }
  …
}

Planche : 29


Enfiler : ajouter à la fin
  in.next = new List (4, null) ;

Planche : 30


Enfiler : ajouter à la fin (suite)
  i = i.next ;

Planche : 31


Défiler : enlever du début
   out = out.next ;

Planche : 32


Code complet d’enfiler

Le code final doit tenir compte des files vides.

void enfiler(int i) {
   if (isEmpty()) {
     in = out = new List (inull) ;
   } else {
     in.next = new List (inull) ;
     in = in.next ;
   }
}

Il en va de même pour défiler (attention à bien remettre in à null en cas de défilage du dernier élément.)


Planche : 33


Autre réalisation des piles/files

Pile et files peuvent également être codées à l’aide de tableaux.

Voici l’exemple des piles :

class Stack {
  private final static int SZ=32 ; // Taille de pile
  private int [] t ;
  private int sp ; // « pointeur de pile »
  Stack() { t = new int[SZ] ; sp = 0 ; }
  …
}

Principe : le tableau est rempli de 0 à sp-1.


Planche : 34


La pile avec un tableau
class Stack {
  …
  boolean isEmpty() { return sp <= 0 ; } // Expression booléenne

  int pop() {
    if (isEmpty()) throw new Error ("Pile vide") ;
    return t[--sp] ; // pour sp = sp-1 ; return t[sp] ;
  }

  void push(int x) {
    if (sp >= t.length) {
      throw new Error ("Pile pleine") ; // Comme Java!
    }
    t[sp++] = x ; // Pour t[sp] = x ; sp = sp+1 ;
  }
}

Planche : 35


Exemple de pile tableau




Planche : 36


Redimensionnement automatique

Il est dommage de limiter la taille des piles à priori.

Profitons des tableaux « dynamiques » de Java.

// Double la taille du tableau interne
  private void resize() {
    if (sp >= t.length) {
      int [] newT = new int [2*t.length] ; // Allouer
      for (int i = 0 ; i < sp ; i++) {
        newT[i] = t[i] ;
      } // Copier t[0..sp] -> newT[0..sp]
      t = newT ; // t référence vers nouveau tableau
    }
  }

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

Planche : 37


Coût de push en cas de redimensionnement

Jusqu’ici push et pop s’exécutaient en temps constant.

Ce n’est plus le cas : push peut maintenant prendre un temps arbitrairement long.

Mais push est toujours en O(1) « amorti ».


Planche : 38


Les piles toutes faites

La pile est une structure tellement utile, que la bibliothèque Java la propose, classe Stack, package java.util

Mais des piles de quoi ?

Par exemple Stack<String>, Stack<List>, …

Voir la doc


Planche : 39


Exemple, pile de String

Notation postfixe → Notation infixe (usuelle).

import java.util.* ; // Stack est java.util.Stack
class Infix {
  public static void main (String [] arg) {
    Stack<Stringstack = new Stack<String> () ;
    for (int k = 0 ; k < arg.length ; k++) {
      String x = arg[k] ;
      if (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()) ;
  }}

Planche : 40


Exemple de transformation
% java Infix 1 2 + 3 '*'
1 -> [1]
2 -> [1, 2]
+ -> [(1+2)]
3 -> [(1+2), 3]
* -> [((1+2)*3)]
((1+2)*3)

Planche : 41


Piles de scalaires

Dans Stack<C> C est une classe.

On ne peut pas faire des piles Stack<int>.

Mais on peut faire des piles Stack<Integer>, où Integer est une classe fournie par défaut (package java.lang).

Deux méthodes utiles :

Il y a des classes semblables (Char, Short etc.) pour tous les types scalaires (char, short etc.)


Planche : 42


La calculette avec pile de la bibliothèque

Cela semble assez lourd.

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

Planche : 43


La calculette avec pile de la bibliothèque II

Mais en fait le compilateur sait faire les conversions intInteger tout seul.

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

Attention, le code qui s’exécute est bien par exemple stack.push(Integer.valueOf(i2+i1)).


Planche : 44


Une file dans un tableau, principe

Deux champs privés, int in et int out. La file va de la case out à la case in-1.


Planche : 45


File dans le tableau, difficulté I



Le tableau est « circulaire »

Solution, incrémenter modulo la taille du tableau.


Planche : 46


File dans le tableau, difficulté II



in et out ne suffisent pas toujours.



Solution, conserver une information additionelle : le nombre d’éléments de la file.


Planche : 47


Files de la bibliothèque

Une classe commode LinkedList<C> (package java.util) convient, il s’agit en fait d’une double-ended queue.

La documentation de la classe LinkedList<C>.

D’autres classes de bibliothèque existent avec des noms plus séduisants (Queue), mais LinkedList<C> est la plus commode.


Planche : 48


Queue à deux bouts

Un petit exemple,


Planche : 49


Choix de l’implémentation

Planche : 50


Une autre utilisation des files/piles

Soit un petit robot, perdu dans un labyrinthe, mais muni d’un sac (de cases) d’un pinceau et de trois couleurs. Le robot cherche la sortie ainsi :

  bag.put(entrée) ;
  while (!bag.isEmpty()) {
    Case case = bag.get() ;
    case.colorie(rouge) ;
    if (case.equals.(sortie)) return ;
    for ( … ) { // Tous les voisins non-coloriés
      Case voisin = … ;
      voisin.colorie(bleu) ;
      bag.put(voisin) ;
    }
    case.colorie(vert) ;
  }

Planche : 51


Rapport voisins/couleur

Planche : 52


Mettre les voisins dans le sac (file ici)




Planche : 53


Sortir une case de la file



Noter : c’est la case la plus ancienne qui est sortie de la file.


Planche : 54


Différents sacs, différents parcours

Sur un labyrinthe sans murs, l’effet est notable.

 
Pile File

Ce document a été traduit de LATEX par HEVEA