Université Bordeaux 1

Licence Semestre 3  - Algorithmes et structures de données 1

Dernière mise à jour effectuée le 23 Juin 2014


Piles et Files


  1. Définitions
  2. Les piles et les files sont des containeurs dans lesquels l'accès ne peut se faire qu'à un objet particulier.
    Définition 3.1. Dans une pile, l'objet supprimé est le dernier inséré (LIFO, Last-In, First-Out).
    Définition 3.2. Dans une file, l'élément supprimé est le plus ancien dans la file (FIFO, First-In, First-Out).
    On écrira pour déclarer des variables :
    type_pile=pile de objet;
    type_file=file de objet;
    

  3. Primitives de pile
  4. Une pile est défini par les opérations suivantes :

    Construire une listeSC inverse à partir d'une listeSC

    fonction listeInverse(val L:listeSC de objet):listeSC de objet;
        var P:pile de objet;
        var LR:liste de objet;
        début
          creerListe(LR);
          creerPile(P);
          debutListe(L);
          tant que !finListe(L) faire
            empiler(P,valeur(L));
            suivant(L);
          fintantque
          insererEnTete(LR,valeur(P));
          depiler(P);
          tant que non(pileVide(P)) faire
            insererApres(LR,valeur(P));
            suivant(LR);
            depiler(P);
          fintantque;
          detruirePile(P)
          retourner(LR);
        fin
    finfonction
    
    On peut peut-être se dispenser de pile ! Oui si la liste est implémenté de manière statique car alors le passage par valeur fournit une copie du tableau.
    fonction listeInverse(val L:listeSC de objet):listeSC de objet;
       var LR:liste de objet;
        début
          creerListe(LR);
          debutListe(L);
          tant que !finListe(L) faire
            insererEnTete(LR,valeur(L));
            suivant(L);
          fintantque;
          retourner(LR);
        fin
    finfonction
    

    Compter le nombre d'élément d'une pile d'entiers

    fonction comptePile(val P:pile de objet): entier;
        var compt:entier;
        var PS:pile de objet;
        var v:objet;
        début
          compt=0;
          creerPile(PS);
          tant que non(pileVide(P)) faire
            compt=compt+1;
            v=valeur(P);
            depiler(P);
            empiler(PS,v);
          fintantque;
          tant que non(pileVide(PS)) faire
            v=valeur(PS);
            depiler(PS);
            empiler(P,v);
          fintantque;
          detruirePile(PS);
          retourner(compt);
        fin
    finfonction
    

    Exercice

    Peut-on se dispenser de copier la pile ?
    La réponse est ca dépend: En effet, le paramètre étant passé par valeur, il est inutile de copier la pile si l'implémentation est statique, dans les implémentations dynamiques : il faut le faire.
    fonction comptePile(val P:pile de objet): entier;
    /* implémentation statique */
        var compt:entier;
        début
          compt=0;
          tant que non(pileVide(P)) faire
            compt=compt+1;
            depiler(P);
          fintantque;
          retourner(compt);
        fin
    finfonction
    

  5. Primitives de File
  6. Une file est défini par les opérations suivantes :

    Compter le nombre d'élément d'une file d'entiers non nuls

    fonction compteFile(ref F:file de entier): entier;
      var v,compt:entier;
      début
        compt=0;
        enfiler(F,0);
        tant que valeur(F)!=0 faire
          compt=compt+1;
          v=valeur(F);
          defiler(F);
          enfiler(F,v);
        fintantque;
        defiler(F);
        retourner(compt);
      fin
    finfonction
    

    inverser une file d'entiers non nuls

    fonction inverserFile(ref F:file de entier): file d'entier;
      var P:pile de entier;
      var FS:file d'entier;
      début
        creerPile(P);
        creerFile(FS);
        enfiler(F,0);
        tant que valeur(F)!=0 faire
          v=valeur(F);
          defiler(F);
          enfiler(F,v);
          empiler(P,v);
        fintantque
        defiler(F);
        tant que non(pileVide(P)) faire
          v=valeur(P);
          enfiler(FS,v);
          depiler(P);
        fintantque;
        detruirePile(P);
        retourner(FS);
      fin
    finfonction
    

  7. Implémentations de pile
  8. Implémentation dans un tableau

    Chaque objet de la pile est un élémént du tableau. On doit de plus avoir un champs qui permet d'accéder au sommet de pile. On a donc
    pile d'objet=structure
                     taille:entier;
                     sommet:entier;
                     pile:tableau[1..taille] d'objets;
                   finstructure;
    

    Implémentation par une listeSC

    Chaque objet de la pile est un objet de la listeSC.
    pile d'objet=listeSC de objet;
    

  9. Implémentations de file
  10. Implémentation dans un tableau

    Chaque objet de la file est un élément du tableau. On utilise le tableau de manière circulaire avec un pointeur donnant le premier et un autre donnant le dernier.
    file d'objet=structure
                     taille:entier;
                     premier:entier;
                     dernier : entier;
    		 plein:booléen;
                     file:tableau[0..taille-1] d'objets;
                   finstructure;
    

    Implémentation par une listeDC

    Chaque objet de la file est un objet de la listeDC car Il faut un accès au dernier.
    file d'objet=listeDC de objet;
    

    Implémentation par une liste comportant un pointeur sur le dernier

    cellule=structure
               valeurElement:objet;
               pointeurSuivant:^cellule;
            finstructure;
    curseur=^cellule;
    file d'objet=structure
                   premier:curseur;
                   dernier:curseur
                 finstructure