Piles

Une pile, en anglais Stack, est une structure de données LIFO, pour Last In, First Out, au sens où l'élément le plus récemment ajouté sur la pile sera le prochain à en être retiré. En cela, elle peut représenter une pile d'objets sur une table (on enlève, conceptuellement, l'élément sur le dessus, pas un élément en-dessous, pour éviter que le tout ne s'écroule, et on ajoute seulement sur le dessus pour les mêmes raisons), mais aussi toute entité structurée sans chevauchement, comme le début et la fin d'une fonction ou une paire de parenthèses. C'est probablement la structure de données la plus simple... et la plus utile.

Opérations clés

Les opérations clés d'une file suivent. Une implémentation peut bien sûr offrir d'autres services, ou utiliser d'autres noms que ceux utilisés ici.

Nom (français) Nom (anglais) Sémantique Complexité typique Risques d'échec / d'exception Remarques 
empiler
 
push

Ajouter un élément sur le dessus de la pile

La pile est pleine; s'applique si la pile a une capacité maximale fixée a priori

Manque de ressources; s'applique si les noeuds sont alloués dynamiquement

   
depiler
 
pop

Retirer un élément du dessus de la pile. Retournera l'élément dans certaines implémentations, et sera void dans d'autres implémentations

La pile est vide

Une implémentation générique devra implémenter ce service de telle sorte qu'il soit void, du moins en l'absence d'un moteur de collecte d'ordures, sinon elle ne pourra être Exception-Safe

 
est_vide
 
empty

Prédicat qui s'avère seulement si la pile est vide

 

Si le langage le supporte, sera typiquement const

Si le langage le supporte, sera typiquement noexcept

 
examiner
 
top
peek

Consulter le dessus de la pile, sans en extraire l'élément

La pile est vide

Si le langage le supporte, sera typiquement const

Si le langage le supporte, sera typiquement noexcept

Nécessaire pour réaliser une implémentation générique qui soit Exception-Safe, du moins en l'absence d'un moteur de collecte d'ordures. Peut être omise sinon

Technique

Implémentation naïve à base de noeuds (capacité dynamique).

Pile d'entiers avec C++ Pile générique avec C++ 
#include <iostream>
class Empty {};
class pile
{
   struct noeud
   {
      int valeur;
      noeud *pred;
      noeud(int valeur) noexcept
         : valeur{ valeur }, pred{}
      {
      }
   };
   noeud *tete;
public:
   bool empty() const noexcept
      { return !tete; }
   pile() noexcept
      : tete{}
   {
   }
   //
   // incopiable mais déplaçable
   //
   pile(const pile&) = delete;
   pile& operator=(const pile&) = delete;
   pile(pile &&autre)
      : tete{ autre.tete }
   {
      autre.tete = {};
   }
   pile& operator=(pile &&autre)
   {
      tete = autre.tete;
      autre.tete = {};
      return *this;
   }
   void push(int valeur)
   {
      auto p = new noeud{ valeur };
      p->pred = tete;
      tete = p;
   }
private:
   void raw_pop()
   {
      auto p = tete->pred;
      delete tete;
      tete = p;
   }
public:
   void pop()
   {
      if (empty()) throw Empty{};
      raw_pop();
   }
   int top()
   {
      if (empty()) throw Empty{};
      return tete->valeur;
   }
   ~pile()
   {
      while (!empty())
         raw_pop();
   }
};
int main()
{
   using namespace std;
   enum { N = 10 };
   pile ze_pile;
   for (int i = 0; i < N; ++i)
      ze_pile.push(i + 1);
   while (!ze_pile.empty())
   {
      cout << ze_pile.top() << endl;
      ze_pile.pop();
   }
}
 
#include <iostream>
#include <string>
class Empty {};
template <class T>
   class pile
   {
   public:
      using value_type = T;
      using reference = T&;
      using const_reference = const T&;
   private:
      struct noeud
      {
         value_type valeur;
         noeud *pred;
         noeud(const_reference valeur) noexcept
            : valeur{ valeur }, pred{}
         {
         }
      };
      noeud *tete;
   public:
      bool empty() const noexcept
         { return !tete; }
      pile() noexcept
         : tete{}
      {
      }
      //
      // incopiable mais déplaçable
      //
      pile(const pile&) = delete;
      pile& operator=(const pile&) = delete;
      pile(pile &&autre)
         : tete{ autre.tete }
      {
         autre.tete = {};
      }
      pile& operator=(pile &&autre)
      {
         tete = autre.tete;
         autre.tete = {};
         return *this;
      }
      void push(const_reference valeur)
      {
         auto p = new noeud{ valeur };
         p->pred = tete;
         tete = p;
      }
   private:
      void raw_pop()
      {
         auto p = tete->pred;
         delete tete;
         tete = p;
      }
   public:
      void pop()
      {
         if (empty()) throw Empty{};
         raw_pop();
      }
      reference top()
      {
         if (empty()) throw Empty{};
         return tete->valeur;
      }
      const_reference top() const
      {
         if (empty()) throw Empty{};
         return tete->valeur;
      }
      ~pile()
      {
         while (!empty())
            raw_pop();
      }
   };
int main()
{
   using namespace std;
   enum { N = 10 };
   pile<string> ze_pile;
   for (int i = 0; i < N; ++i)
      ze_pile.push(to_string(i + 1) + "!");
   while (!ze_pile.empty())
   {
      cout << ze_pile.top() << endl;
      ze_pile.pop();
   }
}
Exécution Exécution 
10
9
8
7
6
5
4
3
2
1
 
10!
9!
8!
7!
6!
5!
4!
3!
2!
1!

Quelques exemples :

Lectures complémentaires

Versions sans verrous :

Valid XHTML 1.0 Transitional

CSS Valide !