More is less

19/09/2015

Stack : liste chaînée

Le C++ offfre en standard (STL) plusieurs conteneurs aussi chiants à manier, les uns que les autres. Pour implémenter une simple pile LIFO on peut recourir à verctor, list ou même l'usine à gaz stack. Ce n'est pourtant pas sorcier d'implémenter une pile.

Correction (24/09/2015) Il semblerait que forward_list fournit une pile LIFO. Je n'ai pas encore essayé.

Pile d'entiers

Les nœeuds

Une liste chaînée est un suite de nœuds qui pointent les uns sur les autres. Ici on prend le cas simple de liste d'entiers n0, n1, ... :

(n0|*) -> (n1|*) -> (n3|*) - - -> (nk|*) -> NULL

(np|*) est un nœud (un élément de la liste) où :

La traduction en C++ sera : struct Node { int val; struct Node * next; };

La pile proprement dite aura la structure :

class Stack {
	...
	Node * top = NULL // sommet de la pile, NULL à la création
}

A la création la pile est vide. Le pointeur sommet, Node * top est initialisé à NULL.

Le premier élément de la liste viendra se greffer dessus :

(n0|*) -> NULL

L'opération à faire est push(n0), elle se décompose ainsi :

Le sommet pointe maintenant sur le dernier nœud crée.

Les méthodes primaires.

Empiler

Nous venons de voir push(int) qui empile les éléments de la liste.

Dépiler

Une méthode indispensable, int pop(), consiste à dépiler le sommet de la pile :

  1. Si besoin, récupérer les données, avant qu'il ne soit trop tard
  2. Créer un pointeur qui repère le sommet
  3. Affecter le sommet de la pile à l'élément suivant
  4. Détruire l'élement temporaire du 2. pour libérer la mémoire
  5. Éventuellement renvoyer les données récupérées en 1.
Parcours de la pile
  1. Définir un pointeur sur Node
  2. Affecter ce pointeur au sommet de la pile
  3. Tant que le pointeur n'est pas NULL faire ce qu'il y a à faire
  4. Déplacer le pointeur sur le noeud suivant

Source complet

 1 // compile g++ std=c++11 -o stack stack
 2 #include <string>
 3 #include <iostream>
 4 using namespace std;
 5 // Node
 6 struct Node {
 7    int val;   // données de la liste
 8    // datas
 9    struct Node * next; // pointeur pour chaîner les éléments
10 };
11 // Stack
12 class Stack
13 {
14 public:
15    void push(int);   // crée et empile les éléments
16    int  pop();       // dépile (supprime) et renvoie la valeur
17    void show();      // pour voir la liste (pédagogique)
18    int count();      // compteur (pédagogique)
19 protected:
20    Node * top = NULL;// sommet de la pile NULL à la création
21 };
22 // push
23 void Stack::push(int v)
24 {  // crée un noeud et le fait pointer sur le sommet de la pile
25    Node * node = new Node; // crée le noeud
26    node->val = v;          // initialise ses données
27    node->next = top;       // le fait pointer sur le sommet de la pile
28    top = node;             // c'est lui qui devient le sommet
29 }
30 // pop
31 int Stack::pop()
32 { // dépile un élément, le détruit et renvoie ses données
33    if(top != NULL ) {      // on s'assure que la pile n'est pas vide
34       int v = top->val;    // on récupère les données à renvoyer
35       Node * node = top;   // pointeur pour la destruction
36       top = top->next;     // le sommet est repoussé au suivant
37       delete node;         // destruction du nœud (libérer mémoire)
38       return v;            // retour des données
39    }
40 }
41 // show
42 void Stack::show()
43 {  // pour la démonstration
44    cout << "Stack: ";
45    Node * node = top;
46    while(node != NULL) {
47       cout  << "[ " << node->val << " *] → ";
48       node = node->next;
49    }
50    cout << "NULL\n";
51 }
52 // count
53 int Stack::count()
54 { // montre comment on peut parcourir la pile de haut en bas
55    int c = 0; // compteur
56    Node * p = top; // pointeur noeud pour le parcours
57    while(p != NULL) { // fin à NULL
58       c++; // compte
59       p = p->next; // suivant
60    }
61    return c;
62 }
63 // -----------------------------------------------------------------------
64 int main()
65 {
66    Stack stack;
67    string c;
68    int v;
69    cout << "\nStack : pile LIFO chaînée\n";
70    while(true) {
71       cout << "\np: push -  d: pop - q: quit\n";
72       cin >> c;
73       if(c == "q") break;
74       if(c == "d") stack.pop();
75       else if(c == "p") {
76          cout << "Integer: ";
77          cin >> v;
78          stack.push(v);
79          }
80       stack.show();
81    }
82    return 0;
83 }
84 
85 
Remarque

Vim a une fonction TOhtml, qui produit un fichier html avec la coloration syntaxique. Il suffit de l'élaguer un peu pour obtenir l'affichage ci-dessus.

Exécution

Appuyez sur ENTRÉE ou tapez une commande pour continuer
 
Stack : pile LIFO chaînée
 
p: push -  d: pop - q: quit
p
Integer: 12
Stack: [ 12 *] → NULL
 
p: push -  d: pop - q: quit
p
Integer: 9
Stack: [ 9 *] → [ 12 *] → NULL
 
p: push -  d: pop - q: quit
p
Integer: 48
Stack: [ 48 *] → [ 9 *] → [ 12 *] → NULL
 
p: push -  d: pop - q: quit
d
Stack: [ 9 *] → [ 12 *] → NULL
 
p: push -  d: pop - q: quit
q
 
Appuyez sur ENTRÉE ou tapez une commande pour continuer
Conteneur Vector de la STL

On peut implémenter plus rapidement une pile avec vector<int>stack.

Pour empiler c'est aussi immédiat stack.push_back(v).

Là où les choses se gâtent, c'est quand il faut parcourir la pile. Tout est à l'envers. On pourrait envisager de pousser les éléments vers le début, mais ce ne serait pas résonnable. L'implémentation est faite avec un array, qu'il faudrait reconstruire et recopier à chaque opération.

Il y aurait aussi list. Là ça devient la bazooka pour tuer un moustique.


Réalisé avec Qlam - LGPL