TD 5 - Pile, File

Pile

L'objectif de cet exercice est de construire une classe C++ correspondant au type de donnée Pile d'entiers (structure LIFO, Last In First Out) muni des fonctions empiler, dépiler, tête et test du vide. Le contenu de la pile sera stocké avec une liste chainée utilisant les blocs :
struct Element {
  int       _val;
  Element * _suivant;
};

Le canevas de notre classe PileE est le suivant :

class PileE {
 private:

  Element * _psommet;

 public:
  PileE();
  void Empiler(int x);
  void Depiler();
  int Sommet();
  int Est_vide();
};

Le champ psommet contient l'adresse du premier bloc (la tête) de la pile.

  1. Implémenter les différentes fonctions de la classe PileE.

     

  2. Plutôt que de définir le type Element comme ci-dessus, on souhaite le définir sous la forme d'une classe (avec un constructeur) et surtout on souhaite le cacher de tout ce qui ne concerne pas le type PileE, on procède comme suit :
    class PileE {
     private:
    
      class Element {
      public:
        int       _val;
        Element * _suivant;
        Element(int v =0, Element * s =0)
        {_val = v; _suivant = s;}
      };
    
    
      Element * _psommet;
    
     public:
      PileE();
      void Empiler(int x);
      void Depiler();
      int Tete();
      int Est_vide();
    };
    

    Maintenant Element est un sous-type de PileE; étant dans la partie private, il n'est visible que depuis les fonctions membres de PileE, et son nom complet est PileE::Element.

    Redéfinir les fonctions membres de PileE.

     

File

On souhaite maintenant définir une classe correspondant au type de donnée File d'entiers (structure FIFO, First In First Out) muni des fonctions ajouter, supprimer, tête et test du vide. Le contenu de la file sera stocké avec une liste chainée circulaire. Le canevas de la classe FileE est le suivant :
class FileE {
 private:

  class Element {
  public:
    int       _val;
    Element * _suivant;
    Element(int v =0)
    {_val = v; _suivant = 0;}
  };

  Element * _pdernier;

 public:
  FileE();
  void Ajouter(int x);
  void Supprimer();
  int Tete();
  int Est_vide();
};

_pdernier est un pointeur sur le dernier élément de la file (i.e. l'élément qui a été ajouté en dernier) qui pointe sur le plus ancien élément (la tête, le prochain à sortir) qui lui-même pointe sur le deuxième plus ancien etc. jusqu'au dernier.

L'usage de _dernier permet donc de récupérer facilement l'adresse de la tête de la file (il est donc inutile d'avoir un pointeur sur cet élément dans la structure de données).

Ecrire les fonctions de FileE.


fl@lsv.ens-cachan.fr                                      Last modification: January 23, 2002