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, ... :

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

• np est la donnée
• * est un pointeur qui pointe sur le nœud suivant.

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 :

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

• Créer un nœud tout neuf : Node * node = new Node.
• Initialiser ses données : ici ça se limite à node->val = v;
• Le faire pointer sur le sommet node->next = top;

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

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.