Une Pile (stack ou LIFO en anglais) est un conteneur d'éléments qui réalise le principe dernier arrivé, premier sorti (Last In, First Out en anglais).
Dans la vie courante, une analogie usuelle serait une pile d'assiettes : "l'assiette qu'on récupère est toujours la dernière qui a été empilée".
Cette fiche précise le Type Abstrait de Données Pile, puis introduit l'implémentation en C des piles qui sera la référence pour ce module, basée sur une simple liste chaînée dynamique.
1. Le type abstrait Pile (Stack ou LIFO)
Parmi les types abstraits "conteneurs d'éléments", une Pile s'appuie sur le principe dernier arrivé, premier sorti.
En anglais, on parle de stack ou de LIFO pour Last In, First Out.
Dans nos sources, on appellera le type C lifo_t
(car le mot clé stack_t existe déjà dans
librairie C).
Les principales opérations qui définissent le TAD Pile sont :
- Créer (new) : créer une pile vide
- Détruire (delete) : détruire une pile
- Empiler (push) : ajouter un élément sur la pile
- Consulter la tête (peek) : récupérer le dernier élément ajouté (on dit la "tête de pile") sans l'enlever. N'a pas de sens que si la pile est vide.
- Dépiler (pop) : récupérer la tête et l'enlever de la pile. N'a pas de sens si la pile est vide.
- Tester si vide : retourner VRAI ou FAUX suivant que la pile est vide ou non
On peut remarquer que, dans cette définition basique du TAD pile, on ne peut accéder qu'à la tête de la pile, c'est à dire au dernier élément ajouté. A l'inverse, il n'est pas possible d'accéder à un élément à l'intérieur de la pile.
Dans cette approche "rigoriste", le TAD ne définit par exemple même pas d'opération pour afficher tous les éléments contenus dans la pile ! Dans la vraie vie, on ajoute quand même souvent cette opération d'affichage - et nous vous conseillons de le faire, ne serait-ce que pour débugger vos programmes...
Les opérations du TAD Pile sont ainsi parfois complétées :
- Afficher : affiche tous les éléments présents dans la pile
- Compter : retourne le nombre d'éléments présents dans la pile
- etc.
Comme d'habitude, lors de l'implantation du TAD dans une structure de données, il importera de s'assurer que les coûts des fonctions réalisant les opérations du TAD sont minimaux.
Pour les piles, les principales opérations (empiler, dépiler, accéder à la tête) sont censées être à coût constant O(1).
2. Pile dynamique : implémentation du TAD Pile s'appuyant sur une liste chaînée
Le TAD Pile peut être réalisé par plusieurs structures de données. Cette secton est consacrée à l'implémentation des piles qui s'appuie sur une simple liste chaînée dynamique.
Cette implémentation s'appuie sur la remarque simple suivante :
Une liste chaînée dynamique, comme vue dans les fiches précédentes, peut tout à fait être utilisée comme une pile.
Il faut et suffit de n'accéder qu'à la tête de la liste.
Dès lors :
- "Empiler" un élément, c'est tout simplement ajouter l'élément en tête de la liste
- Et "dépiler" un élément, c'est tout simplement enlever l'élément en tête de la liste
Exemple de mise en oeuvre du TAD pile au moyen d'une liste chaînée dynamique.
Pour implanter le TAD Pile au moyen d'une structure de données de type liste chaînée, deux solutions :
-
On peut définir le type pile (
lifo_t) comme on avait définit le type liste, puis on écrit les fonctionslifo_push()etlifo_pop()comme on avait écrit les fonctions d'ajout et suppression en tête sur les listes. - Si on dispose déjà du code de la liste chaînée dynamique, on peut aussi dire que la pile est en fait une liste, puis écrire les fonctions du TAD pile tout simplement en appelant les fonctions du TAD liste. Autrement dit, dans ce cas, une pile est en fait une liste dont on a juste changé la sémantique.
Voyons comment faire dans le 2nd cas.
2.1 Ficher header lifo.h : type C et API du module Pile
On suppose donc qu'on dispose d'un module liste, tel que vu dans la fiche implémentation de référence des listes :
// Fichier list.h
#ifndef _LIST_H
#define _LIST_H
#include "element.h"
// 1. Définition des types maillon (link_t) et liste (list_t)
typedef struct _link {
element_t val; /* un élément de la liste*/
struct _link *next; /* l'adresse du maillon suivant */
} link_t, *list;
// 2. Protoype des fonctions realisant les opérations essentielles du type abstrait Liste
// Crée une liste vide
list_t list_new() ;
// Retourne VRAI si l est une liste vide
int list_is_empty(list_t l);
// Retourne l'élément en tête de liste
// PRECONDITION : liste non vide
element_t list_first(list_t l);
// Retourne le reste de la liste
// PRECONDITION : liste non vide
list_t list_next(list_t l);
// Ajoute l'élément e en tête de la liste et retourne la nouvelle liste
list_t list_add_first(element_t e, list_t l);
// Supprime le maillon en tête de liste et retourne la nouvelle liste
// PRECONDITION : liste non vide
list_t list_del_first(list_t l);
// Retourne le nombre d'éléments (ou de maillons) de la liste
size_t list_length(list_t l);
// Retourne un pointeur sur le premier maillon contenant e,
// ou NULL si e n'est pas dans la liste
list_t list_contains(list_t l, element_t e);
// Affiche la liste
void list_print(list_t l);
// Libère toute la liste et retourne une liste vide
list_t list_delete(list_t l);
#endif
Pour déclarer le type
lifo_t
dans le fichier header lifo.h du module pile,
il suffit d'importer le module list
puis d'indiquer que "une pile est en fait une liste" :
// fichier lifo.h pour l'implantation du TAD pile au moyen d'une liste chaînée dynamique
#ifndef LIFO_H_
#define LIFO_H_
#include "list.h" // On importe le TAD liste chaînée dynamique
// 1. declaration du type lifo_t.
// Il suffit de déclarer que "une pile est une liste" !
typedef list_t lifo_t ;
// 2. prototype des fonctions de l'API du TAD Pile
...
#endif
Pour l'API du module lifo,
c'est à dire la liste des prototype des fonctions réalisant le TAD Pile,
on traduit les opérations du TAD.
Le fichier lifo.h est alors donné
in extenso ci-dessous :
// fichier lifo.h pour l'implantation du TAD pile au moyen d'une liste chaînée dynamique
#ifndef LIFO_H_
#define LIFO_H_
#include "list.h" // On importe le TAD liste chaînée dynamique
// 1. declaration du type lifo_t.
// Il suffit de déclarer que "une pile est une liste" !
typedef list_t lifo_t ;
...
// 2. prototype des fonctions de l'API du TAD Pile
// Crée et retourne un pile vide ou NULL en cas d'erreur
lifo_t lifo_new();
// Détruit la pile et retourne une pile vide
lifo_t lifo_delete(lifo_t stack);
// Retourne 1 si la pile stack est vide, 0 sinon
int lifo_is_empty(lifo_t stack);
// Ajoute l'élément e à la pile stack et retourne la nouvelle pile
lifo_t lifo_push(element_t e, lifo_t stack);
// Retourne l'élément en tête de pile (sans l'enlever de la pile)
// PRECONDITION : la pile stack ne doit pas être vide
element_t lifo_peek(lifo_t stack);
// Enlève l'élément en tête de la pile, et retourne cet élément
// PRECONDITION : la pile pointée par p_stack ne doit pas être vide
element_t lifo_pop(lifo_t * p_stack);
#endif
Dans ce fichier lifo.h,
le prototype de la fonction
lifo_pop()
appelle une remarque importante.
Cette fonction lifo_pop() doit en effet "retourner" 2 choses :
- l'élément qui était en tête
- et la pile modifiée, dont on enlevée l'ancienne tête
Seulement voila : en langage C, il n'est possible de retourner (avec return)
qu'une unique valeur.
Pour cette fonction, il faut donc nécessairement avoir recours à un passage par pointeur (ou "par adresse") pour l'une des deux valeurs à "retourner".
Dans notre API, le choix réalisé est de
passer la pile par pointeur et de
retourner l'élément qui était en tête avec return.
C'est pourquoi le prototype de la fonction est : element_t lifo_pop(lifo_t * p_stack).
2.2 Ficher source lifo.c
Le fichier source lifo.c du module pile est alors particulièrement simple à écrire :
puisque une pile est une file dans cette implémentation,
il faut et suffit d'appeler les fonctions des listes !
// Extrait du fichier lifo.c pour l'implantation du TAD pile au moyen d'un tableau
#include "lifo.h"
// Crée et retourne un pile vide ou NULL en cas d'erreur
lifo_t lifo_new() {
return list_new(); // "créer une pile, c'est en fait créer une liste !"
}
...
// Ajoute l'élément e à la pile s et retourne la nouvelle pile
lifo_t lifo_push(element_t e, lifo_t stack) {
return list_add_first(e, stack); // "empiler, c'est en fait ajouter en tête de la liste !"
}
// Retourne l'élément en tête de pile (sans l'enlever de la pile)
// PRECONDITION : la pile stack ne doit pas être vide
element_t lifo_peek(lifo_t stack) {
return list_first(stack);
}
... etc ...
Ecrire de la fonction lifo_pop()
est un peu plus délicat du fait que
la pile est passée par adresse à cette fonction.
Le QCM suivant propose alors 3 implémentations. Retrouverez-vous laquelle est correcte ?
// Enlève l'élément en tête de la pile, et retourne cet élément
// PRECONDITION : la pile pointée par p_stack ne doit pas être vide
element_t lifo_pop(lifo_t * p_stack) {
element_t e = list_first(*p_stack);
list_del_first(*p_stack);
return e;
}
La fonction
list_del_first() supprime le
premier maillon de la liste et retourne la nouvelle liste.
A la ligne 5, il faut penser à mettre à jour la variable liste (ici : la pile pointée par
p_stack)
à partir de la valeur retournée par la fonction !
// Enlève l'élément en tête de la pile, et retourne cet élément
// PRECONDITION : la pile pointée par p_stack ne doit pas être vide
element_t lifo_pop(lifo_t * p_stack) {
* p_stack = list_del_first(*p_stack);
return list_first(*p_stack);
}
// Enlève l'élément en tête de la pile, et retourne cet élément
// PRECONDITION : la pile pointée par p_stack ne doit pas être vide
element_t lifo_pop(lifo_t * p_stack) {
element_t e = list_first(*p_stack);
* p_stack = list_del_first(*p_stack);
return e;
}
2.3 Embryon de code de test du module lifo
Enfin, voici un embryon de code de test de notre module pile,
qui correspond aux évolution de l'image précédente
(on suppose donc que le type element_t
a été défini avec typedef double element_t ;).
// Code de test des piles, dans le cas où les éléments sont des double
#include "lifo.h"
int main() {
lifo_t une_pile = lifo_new();
une_pile = lifo_push(9.5, une_pile);
printf("L'élément en tete de pile vaut : %lf\n", lifo_peek(une_pile));
// affiche 9.5 . Remarque : l'élément n'a pas été enlevé
une_pile = lifo_push(6.0, une_pile);
une_pile = lifo_push(5.4, une_pile);
une_pile = lifo_push(3.6, une_pile);
element_t ancienne_tete = lifo_pop( &une_pile );
printf("L'élément qui vient d'être supprimé en tete de pile vaut : %lf\n", ancienne_tete);
// affiche 3.6
une_pile = lifo_delete(une_pile);
return 0;
}
2.4 Un QCM pour finir
int main() {
... // Même début
// ICI LA PILE CONTIENT 4 ELEMENTS
element_t ancienne_tete = lifo_pop( &une_pile );
printf("L'élément qui vient d'être supprimé en tete de pile vaut : %lf\n", ancienne_tete);
// affiche 3.6
lifo_pop( &une_pile );
lifo_pop( &une_pile );
lifo_pop( &une_pile );
lifo_pop( &une_pile ); // <=====
une_pile = lifo_delete(une_pile);
}
fifo_pop() le précise bien
en annonçant la précondition "la pile ne doit pas être vide" !
list_pop()
a un gros problème, puisqu'il ne
traite pas le cas d'erreur "pile vide" !
3 En conclusion
Nous avons introduit l'implémentation du TAD pile qui s'appuie sur une structure de données "liste chaînée dynamique".
Avec l'implémentation du TAD à base d'une liste chaînée dynamique, il n'y a pas de limite au nombre d'éléments contenus dans la pile (à part celle due à la mémoire disponible sur la machine), la complexité mémoire croit linéairement avec la taille de la pile, et la complexité des fonctions est constante, O(1).
Le code s'avère particulièrement simple à écrire si on dispose déjà d'un module liste.
Notre implémentation des piles qui s'appuie sur les listes dynamiques a un problème :
puisque le type C pile est défini comme le type liste avec
typedef list_t lifo_t ;,
alors, si on créer une variable de type pile,
cette variable est en fait de type liste... et rien n'empêche
d'utiliser cette variable comme une liste.
Autrement dit, il devient possible d'appeler toutes les fonctions du module
liste
avec une variable de type Pile.
Par exemple, il est possible d'appeler la fonction
d'ajout en queue de liste, d'appeler la fonction qui supprime
les maillons contenant un certain élément, etc.
Ceci n'est pas cohérent avec l'idée que, dans une pile, on ne doit voir et manipuler que le dernier élément ajouté dans la pile (la "tête de pile"), mais pas le reste.
Il y a deux solutions à ce problème en langage C.
- Définir explicitement le type pile comme on avait défini le type liste, et tricher dans le fichier .c en indiquant au compilateur que les deux types sont en fait identiques.
- Avoir recours aux types opaques en langage C.
La seconde solution est la plus propre, mais elle est au delà de nos compétences ce semestre. Voyons donc la première
Définir explicitement le type pile comme on avait défini le type liste, et tricher dans le fichier .c en indiquant au compilateur que les deux types sont en fait identiques.
Il s'agit d'abord de ne pas indiquer dans le fichier header du module pile qu'une pile est une liste, mais juste de définir le type pile comme on avait défini le type liste.
Le fichier header devient donc :
#ifndef LIFO_H_
#define LIFO_H_
#include "element.h"
// 1. declaration explicite du type lifo_t.
// En fait, on sait que c'est la même chose que le type list_t
// Mais ca, le compilateur ne le sait pas !
typedef struct _lifo_link {
element_t val;
_lifo_link * next;
} * lifo_t ;
// 2. prototype des fonctions de l'API du TAD Pile
... ETC ... // les prototypes ne changent pas
#endif
Comme le type pile n'est pas défini comme étant identique au type liste, le compilateur râlera si on veut appeler, dans le main() par exemple, une fonction du module liste en lui passant une variable de type pile. Ca tombe bien, c'est tout à fait ce que l'on cherche !
Dans le fichier source du module pile, et uniquement dans ce fichier, le secret est alors de "tricher" en indiquant au compilateur que, en fait, on sait nous qu'une variable pile est la même chose qu'une variable liste.
Pour cela, on utilise des casts de pointeurs.
Voici alors ce que devient le fichier lifo.c.
// Extrait du fichier lifo.c pour l'implantation du TAD pile au moyen d'une liste
// avec les "types opaques"
#include "lifo.h"
#include "list.h" // ici on inclue list.h pour connaître les prototypes des fonctions sur les listes
// Crée et retourne un pile vide ou NULL en cas d'erreur
lifo_t lifo_new() {
list_t l = list_new();
return (lifo_t) l; // <=== Remarquez le cast du type du pointeur
// ou directement :
// return (lifo_t) list_new();
}
// Ajoute l'élément e à la pile s et retourne la nouvelle pile
lifo_t lifo_push(element_t e, lifo_t stack) {
list_t l = (list_t) stack; // <=== Remarquez le cast du type du pointeur
l = list_add_first(e, l);
return (lifo_t) l; // <=== Remarquez le cast du type du pointeur
// ou directement :
// return (lifo_t) list_add_first(e, (list_t) stack);
}
... etc ...
Et voila, le tour est joué : à part dans notre fichier lifo.c,
personne ne sait que derrière nos piles se cachent en fait
une bête liste chaînée dynamique !
Et hors de ce module, par exemple dans la fonction
main(), le compilateur ralera
si on passe une variable pile de type
lifo_t
à une fonction du module list.