Chapitre IV – Les piles
- Définition d’une pile
Une pile (en anglais stack) est une structure de données fondée sur le principe « dernier arrivé, premier sorti » (ou LIFO pour Last In, First Out), ce qui veut dire, qu’en général, le dernier élément ajouté à la pile sera le premier à être utilisé. Le fonctionnement est similaire à celui d’une pile d’assiettes : on ajoute des assiettes sur la pile, et on les récupère dans l’ordre inverse, en commençant par la dernière ajoutée. (wikipedia)
Son implémentation est analogue à la SDA liste. En représentation chaînée, une pile est un pointeur sur la cellule sommet de la pile, si elle existe. Une pile vide est un pointeur vers NULL. Par construction, chaque cellule de la pile contient l’information à mémoriser ainsi que l’adresse de la cellule suivante. La dernière cellule (ou première chronologiquement) admet NULL comme élément suivant. Les opérations standard sur les piles sont :
- Opération de création : creer_pile
- Opérations de consultation : vide_pile et sommet_pile
- Opérations de modification : empiler (en anglais push) et depiler (pop)
ASD2 – TI1-7 – Les piles
1/6
- Spécification d’une pile chaînée : fichier pile.h
/* fichier pile.h */ typedef int element;
typedef struct cellule{ element information; struct cellule * suivant; } cellule;
typedef struct cellule * pile;
void creer_pile(pile*); element sommet_pile(pile); /* sommet d’une pile non vide */ int vide_pile(pile); void empiler_pile(pile* , element); void depiler_pile(pile*); /* supprime le sommet d’une pile non vide */
- Implémentation d’une pile chaînée : fichier pile.c
NB : Les schémas ci-dessous sont donnés à titre indicatif, des corrections sur ces schémas seront faites en classe.
ASD2 – TI1-7 – Les piles
2/6
ASD2 – TI1-7 – Les piles
3/6
/* fichier pile.c */ #include « pile.h » #include <stdlib.h>
void creer_pile(pile*p){ *p = NULL; } element sommet_pile(pile p){ return p->information; } int vide_pile(pile p){ return p == NULL; } void empiler_pile(pile*p , element e){ cellule*n; n = (cellule*)malloc(sizeof(cellule)); n->information = e; n->suivant = *p; *p = n; } void depiler_pile(pile*p){ cellule * n = *p; *p = (*p)->suivant; free(n) ; }
- Exercice 1 : Utilisation du module pile.h
Ecrire un programme principal qui utilise et teste efficacement le module pile.h
/* fichier main.c */ #include <stdio.h>
ASD2 – TI1-7 – Les piles
4/6
#include « pile.h »
void main() { pile p1; int i;
creer_pile(&p1); for(i = 0 ; i < 5 ; i++) empiler_pile(&p1 , i);
while(!vide_pile(p1)){ printf(« %d\t » , sommet_pile(p1)); depiler_pile(&p1); } } Résultat de l’exécution
4 3 2 1 0
- Exercice 2 : pile en représentation contiguë
Ecrire la spécification, l’implémentation et une utilisation du module pile_contig.h qui implémente la pile en représentation contiguë (à base d’un tableau).
/* fichier pile_contig.h */ #define taille_max 100
typedef int element; typedef struct pile{ element information[taille_max]; int sommet; } pile;
void creer_pile(pile*); int vide_pile(pile); element sommet_pile(pile); void depiler(pile*); void empiler(pile* , element);
/* fichier pile_contig.c */ #include « pile_contig.h »
void creer_pile(pile * p){ p->sommet = -1; } int vide_pile(pile p){ return p.sommet == -1; } element sommet_pile(pile p){ return p.information[p.sommet]; } void depiler(pile * p){ p->sommet–; } void empiler(pile * p , element e){ if(p->sommet < taille_max-1){ p->sommet++;
ASD2 – TI1-7 – Les piles
5/6
p->information[p->sommet] = e; } } /* fichier main.c */ #include <stdio.h> #include « pile_contig.h »
void main() {
pile p1;
creer_pile(&p1); empiler(&p1 , 0); empiler(&p1 , 1); empiler(&p1 , 2); empiler(&p1 , 3); empiler(&p1 , 4);
while(!vide_pile(p1)){ printf(« %d\t » , sommet_pile(p1)); depiler(&p1); } } Résultat de l’exécution
4 3 2 1 0
ASD2 – TI1-7 – Les piles
6/6
télécharger gratuitement cours piles et files
