Une Pile, Stack en anglais, est une structure de données qui suit le principe LIFO (Last In First Out - dernier entré, premier sorti). En d'autres termes: on contraint une structure de données dans laquelle l'élément inséré en dernier doit être le premier élément à sortir.

Inversement, cela signifie également que le premier élément mis dans la pile finira toujours par être le dernier élément sorti.

Ce concept limitant est extrêmement utile et permet de manipuler facilement des structures représentant celles de notre monde réel. Un pile représentera par exemple parfaitement une pile d'assiettes ou de livres dans laquelle nous ne pouvons retirer/ajouter, à chaque fois, uniquement l’élément au dessus de la pile.

Les piles sont utilisées absolument partout dans le monde de la programmation. En voici quelques exemples:

Elle peut simuler parfaitement un jeu de carte.

La Pile d’appels (Callstack) fait référence à tous les appels de fonction qui ont lieu pendant l’exécution d’un processus. La pile d'appels est indispensable pour suivre efficacement l'exécution d’un programme.

Ici un exemple de callstack JS générée par l'utilisation de H.urna Explorer.

Ici un algorithme de parcours en profondeur (ou DFS, pour Depth-First Search) est un algorithme de parcours d'arbre, et plus généralement de parcours de graphe, qui se décrit naturellement de manière récursive.

Note : Les algorithmes récursifs utilisent la pile d'appel pour sauvegarder leur context. Comprendre les piles nous permettra de maitriser les algorithmes récursifs beaucoup plus facilement.

Génération DFS, Depth-First Search, d'un labyrinthe utilisant une pile avec H.urna Explorer.

Historique - undo - Ctrl+z :
l'opération d'annulation d'une modification est réalisée en conservant chacune de ces modifications dans une pile.

D’où la plateforme Stack Overflow tire son nom.

Un «débordement de pile» (Stack Overflow) est ce qui se produit lorsque nous essayons de placer un élément sur une pile pleine : la pile déborde pour la quantité de mémoire allouée (cf. implémentation en tableau plus bas).

Faire fonctionner une pile.
Avoir une meilleure compréhension de la récursion.
Créer nos propres structures de pile.
Mettre en pratique les structures de tableaux et de listes chaînées.
Comprendre les avantages / inconvénients de chaque implémentation.

Et ensuite ?

Si nous n’avons pas encore vu les queues (files d'attentes), c’est l’occasion : elles sont implémentées selon le principe FIFO (First-In-First-Out) inversement aux piles vues ici.

Nous pouvons maintenant jouer avec des algorithmes avancés tels que la génération de labyrinthes utilisant la Recherche en Profondeur (DFS). Nous pouvons aussi continuer avec des structures de données plus avancées telles que : les arbres binaires (binary trees) ou les tables de hachage (hash tables).

Nous avons opté pour le C++ pour l'illustration du code, mais pas d'inquiétude, les autres langues utilisent la même logique et le plus souvent une syntaxe similaire.

Une pile est utilisée pour les deux opérations principales suivantes :

  void push(const T& data);  // Insère un nouvel élément en haut de la pile
  void pop();                // Supprime l'élément au-dessus de la pile.

Pour utiliser correctement une pile, les fonctionnalités suivantes sont ajoutées :

  bool empty() const;        // Teste si la pile est vide.
  const T& top() const;      // Montre l’élément du dessus de la pile.
 

Exemple

  stack< string > history; // Initialise la pile
  history.push("paste");   // ["paste"]
  history.push("turn");    // ["paste", "turn"]
  history.pop();           // ["paste"]
  history.top();           // --> "paste"
  history.push("color");   // ["paste", "color"]
  history.push("clean");   // ["paste", "color", "clean"]

  // Get drawing history from the last action
  while (!history.empty()) {
    auto current = history.top();
    history.pop();
  }
 

Cool, maintenant que nous savons utiliser une pile, un question demeure : comment construire notre propre structure de pile? Bonne nouvelle : c’est assez facile. Nous verrons plusieurs implémentations afin d’en comprendre les fonctionnements et pouvoir choisir la plus optimale.

Remarque: La pile est une structure de données abstraite. La définition de leur structure est basée sur leur comportement et non sur leur implémentation. Cela contraste avec les structures de données plus fondamentales, telles que les tableaux et les listes chaînées, qui ont des exigences strictes pour le stockage de leurs données.

En Liste chaînée (Linked List)

L'implémentation utilisant la liste chaînée est l'une des implémentations de pile les plus simples que nous puissions faire. Reprenons le squelette de notre structure vue dans le cours 'liste chaînée'.

  template < typename T >
  class Stack
  {
  public:
    Stack() : head(nullptr) {}  // Construct as an empty stack
    ~Stack() { ... }            // Destructor (same as linked list)

  private:
    // Node structure declaration
    struct Node
    {
        // Constructor
        Node(const T& data) : data(data), next(nullptr) {}
        T data;     // Value
        Node* next; // Pointer to the next node
    };

    Node* head; // Pointer on the first element (also the top of the stack)
  }

Lorsque nous souhaitons ajouter quelque chose à la pile (Push), il nous suffit de l'ajouter au début de la liste (le dessus de notre pile).

Mais... c'est exactement ce que fait la fonction PushFront, non?

  void Push(const T& data)
  {
    Node* newNode = new Node(data); // Allocate memory
    newNode->next = head;           // Set the next node to be the head
    head = newNode;                 // Set head to the new node
  }
  

Pour la fonction Pop, rien de plus simple : supprimons le premier élément de la liste.

  void Pop()
  {
    if (!head) // Empty stack error
      return;

    auto tmp = head;      // Get the current top
    head = head->next;    // Set the head to point to the next node
    delete tmp;           // Delete the node
  }
  

Les fonctions Empty et Top sont elles aussi triviales.

  bool Empty() const { return (head) ? false : true; }

  const T& Top() const
  {
    if (!head); // Throw Exception
    return *head;
  }

  

L'implémentation ci-dessus nous donne les idées impliquées, et toute optimisation dont nous pourrions avoir besoin peut être accomplie en modifiant directement une structure de liste chaînée.

En Tableau (array)

Utiliser une implémentation de tableau pour une pile est une approche simple et implique uniquement de garder le compte.

  template < typename T >
  class Stack
  {
  public:
    // Allocate/Deallocate stack memory
    Stack(const int size) : count(0), max_size(size) {  stack = new T[max_size]; }
    ~Stack() { delete[] stack; }

  private:
    int count;          // Keep track of current stack size (and therefore the top index)
    const int max_size; // Keep track of the max size to check if full
    T* stack;           // Pointer on the array

    Stack(); // Forbid default constructor
  }

Lorsque nous souhaitons ajouter quelque chose à la pile (Push), il nous suffit de le mettre au niveau de l'index et l'incrémenter.

  void Push(const T new_data) {
    if (count == max_size) // Stack overflow exception

    stack[count] = new_data; // Set data
    ++count;                 // Update count
  }
  

Pour la fonction Pop, rien de plus simple : nous decrémentons l'index.

  void Pop()
  {
    if (count == 0) // Empty stack error
      return;

    --count;  // Change top index
  }
  

Les fonctions Empty et Top sont elles aussi encore triviales.

  bool Empty() const { return count == 0; }
  const T& Top() const { return stack[count]; }
  

Stack Overflow !

C'est ce qu'il se passe si nous essayons d'ajouter un élément dans une pile pleine.

Un dépassement de pile ou débordement de pile (stack overflow) est un bug causé par un processus qui, lors de l'écriture dans une pile, écrit à l'extérieur de l'espace alloué à la pile.

Dans le cas de la call stack (pile d'appels des fonctions) par exemple, cela se produira si nous avons une boucle/récursion infinie. (un bug assez fréquent!)

En Tableau dynamique (Vector)

Si nous utilisons une implémentation en tableau dynamique, il nous faudra simplement doubler la capacité de notre tableau lorsque la pile est pleine. Cela implique une perte de performance car cela nécessite une allocation mémoire ainsi qu'une copie de tous les éléments.

En bref

Liste chaînée (Linked List)
Opérations d'insertion et de suppression en O(1).
Peut grandir de manière dynamique.
Allocation/Deallocation mémoire nécessaire pour les opérations d'insertion et de suppression.
Utilise très légèrement plus de mémoire en raison du stockage supplémentaire de pointeurs.

Tableau (Array)
Opérations d'insertion et de suppression en O(1).
Ne peut grandir de manière dynamique : il nécessite une taille maximale à l'initialisation.
Un tableau surdimensionné entraîne quantité de mémoire gaspillée.
Risque de débordement de pile (stack overflow).

Tableau dynamique (Vector)
Opérations d'insertion et de suppression en O(1) (hors redimesionnement).
Peut grandir de manière dynamique.
La redimensionnement d'un tableau est en O(n).
Un tableau surdimensionné entraîne quantité de mémoire gaspillée.

• The Algorithm Design Manual Book par Steven S Skiena
• Wikipedia