Posez votre question »

Les piles en langage C

Juillet 2015


Les piles




Requis


Les types de données
Les structures
L'utilisation de typedef
Les pointeurs
Les fonctions utilisateur
Les listes simplement chaînées
Les listes doublement chaînées

I. INTRODUCTION


Cette article a pour but la compréhension des piles.
L'implémentation en fonction du besoin vous appartient.
Pour expliquer l'algorithme j'ai choisi d'utiliser une liste simplement chaînée. Donc la compréhension des listes chaînées est nécessaire.

II. Définition


La pile est une structure de données, qui permet de stocker les données dans l'ordre LIFO (Last In First Out) - en français Dernier Entré Premier Sorti).
La récupération des données sera faite dans l'ordre inverse de leur insertion.

Pour l'implémentation j'ai choisi une liste simplement chaînée, présentée sur la verticale.
L'insertion se faisant toujours au début de la liste, le 1er élément de la liste sera le dernier élément saisi, donc sa position est en haut de la pile.
Je n'ai pas utilisé un pointeur fin, comme je l'ai fait dans le cas des listes simplement chaînées, puisque le but ce n'est pas de traiter une liste chaînée, mais la pile.
Ce qui nous intéresse c'est que le dernier élément entré, sera le 1er élément récupéré.


III. La construction du prototype d'un élément de la pile


Pour définir un élément de la pile le type struct sera utilisé.
L'élément de la pile contiendra un champ donnee et un pointeur suivant.
Le pointeur suivant doit être du même type que l'élément, sinon il ne pourra pas pointer vers l'élément.
Le pointeur suivant permettra l'accès vers le prochain élément.
typedef struct ElementListe {
    char *donnee;
    struct ElementListe *suivant;
}Element;

Pour permettre les opérations sur la pile, nous allons sauvegarder certains éléments :
  • le premier élément
  • le nombre d'éléments


Le 1er élément, qui se trouve en haut de la pile, nous permettra de réaliser l'opération de récupération des données situées en haut de la pile.


Pour réaliser cela, une autre structure sera utilisée (ce n'est pas obligatoire, des variables peuvent être utilisées).
Voici sa composition :
typedef struct ListeRepere{
  Element *debut;
  int taille;
} Pile;

Le pointeur debut contiendra l'adresse du premier élément de la liste.
La variable taille contient le nombre d'éléments.

Observation :
Nous n'utilisons pas cette fois un pointeur fin (voir les listes simplement chaînées), puisque nous n'en avons pas besoin, vu que nous travaillons qu'au début de la liste.

Quelque soit la position dans la liste, le pointeur debut pointe toujours vers le 1er élément, qui sera en haut de la pile.
Le champ taille contiendra le nombre d'éléments de la pile, quelque soit l'opération effectuée sur la pile.

IV. Opérations sur les piles


A. Initialisation


Prototype de la fonction :
void initialisation (Pile *tas);

Cette opération doit être faite avant toute autre opération sur la pile.
Elle initialise le pointeur debut avec le pointeur NULL, et la taille avec la valeur 0.

La fonction
void initialisation (Pile * tas){
  tas->debut = NULL;
  tas->taille = 0;
}

B. Insertion d'un élément dans la pile


Voici l'algorithme d'insertion et de sauvegarde des éléments :
  • déclaration d'élément(s) à insérer
  • allocation de la mémoire pour le nouvel élément
  • remplir le contenu du champ de données
  • mettre à jour le pointeur debut vers le 1er élément (le haut de la pile)
  • mettre à jour la taille de la pile



Prototype de la fonction :
int empiler (Pile *tas, char *donnee);

La 1ère image montre le début de l'insertion, donc la liste a la taille 1 après l'insertion. La caractéristique de la pile n'est pas très bien mise en évidence avec un seul élément, puisque c'est le seul à récupérer.



En revanche la 2ème image nous permet d'observer le comportement de la pile.
La chose qu'il faut retenir, c'est que l'insertion se fait toujours en haut de la pile (au début de la liste).



La fonction
/* empiler (ajouter) un élément dans la pile */
int empiler (Pile * tas, char *donnee){
  Element *nouveau_element;
  if ((nouveau_element = (Element *) malloc (sizeof (Element))) == NULL)
    return -1;
  if ((nouveau_element->donnee = (char *) malloc (50 * sizeof (char)))
      == NULL)
    return -1;
  strcpy (nouveau_element->donnee, donnee);
  nouveau_element->suivant = tas->debut;
  tas->debut = nouveau_element;
  tas->taille++;
}

C. Ôter un élément de la pile


Pour supprimer (ôter ou dépiler) l'élément de la pile, il faut tout simplement supprimer l'élément vers lequel pointe le pointeur debut.
Cette opération ne permet pas de récupérer la donnée en haut de la pile, mais seulement de la supprimer.

Prototype de la fonction :
int depiler (Pile *tas);

La fonction renvoie -1 en cas d'échec sinon elle renvoie 0.

Les étapes :
  • le pointeur supp_elem contiendra l'adresse du 1er élément
  • le pointeur debut pointera vers le 2ème élément (après la suppression du 1er élément, le 2ème sera en haut de la pile)
  • la taille de la pile sera décrémentée d'un élément




La fonction
int depiler (Pile * tas){
  Element *supp_element;
  if (tas->taille == 0)
    return -1;
  supp_element = tas->debut;
  tas->debut = tas->debut->suivant;
  free (supp_element->donnee);
  free (supp_element);
  tas->taille--;
  return 0;
}

D. Affichage de la pile


Pour afficher la pile entière, il faut se positionner au début de la pile (le pointeur debut le permettra).
Ensuite, en utilisant le pointeur suivant de chaque élément, la pile est parcourue du 1er vers le dernier élément.
La condition d'arrêt est donnée par la taille de la pile.

La fonction
/* affichage de la pile */
void affiche (Pile * tas){
  Element *courant;
  int i;
  courant = tas->debut;

  for(i=0;i<tas->taille;++i){
    printf("\t\t%s\n", courant->donnee);
    courant = courant->suivant;
  }
}

E. Récupération de la donnée en haut de la pile


Pour récupérer la donnée en haut de la pile sans la supprimer, j'ai utilisé une macro. La macro lit les données en haut de la pile en utilisant le pointeur debut.
#define pile_donnee(tas)  tas->debut->donnee

V. Exemple complet


pile.h


/*********************\

 *      pile.h       *
\*********************/
typedef struct ElementListe{
  char *donnee;
  struct ElementListe *suivant;
} Element;

typedef struct ListeRepere{
  Element *debut;
  int taille;
} Pile;


/* initialisation */
void initialisation (Pile *tas);

/* EMPILER*/
int empiler (Pile *tas, char *donnee);

/* DEPILER*/
int depiler (Pile *tas);

/* Affichage de élément en haut de la pile (LastInFirstOut) */
#define pile_donnee(tas)  tas->debut->donnee

/* Affiche la pile */
void affiche (Pile *tas);

pile_function.h


/***********************\

 * pile_function.h     *
\***********************/

void initialisation (Pile * tas){
  tas->debut = NULL;
  tas->taille = 0;
}

/* empiler (ajouter) un élément dans la pile */
int empiler (Pile * tas, char *donnee){
  Element *nouveau_element;
  if ((nouveau_element = (Element *) malloc (sizeof (Element))) == NULL)
    return -1;
  if ((nouveau_element->donnee = (char *) malloc (50 * sizeof (char)))
      == NULL)
    return -1;
  strcpy (nouveau_element->donnee, donnee);
  nouveau_element->suivant = tas->debut;
  tas->debut = nouveau_element;
  tas->taille++;
}

/* depiler (supprimer un élément de la pile */
int depiler (Pile * tas){
  Element *supp_element;
  if (tas->taille == 0)
    return -1;
  supp_element = tas->debut;
  tas->debut = tas->debut->suivant;
  free (supp_element->donnee);
  free (supp_element);
  tas->taille--;
  return 0;
}

/* affichage de la pile */
void affiche (Pile * tas){
  Element *courant;
  int i;
  courant = tas->debut;

  for(i=0;i<tas->taille;++i){
    printf("\t\t%s\n", courant->donnee);
    courant = courant->suivant;
  }
}

pile.c


/*********************\

 *      pile.c       *
\*********************/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include "pile.h"
#include "pile_function.h"

int main ()
{
  Pile *tas;
  char *nom;
  if ((tas = (Pile *) malloc (sizeof (Pile))) == NULL)
    return -1;
  if ((nom = (char *) malloc (50 * sizeof (char))) == NULL)
    return -1;
  initialisation (tas);

  printf ("Entrez un mot : ");
  scanf ("%s", nom);
  empiler (tas, nom);
  printf ("La pile (%d éléments): \n",tas->taille);
  printf("\n********** Haut de la PILE **********\n");
  affiche(tas);
  printf("__________ Bas de la PILE __________\n\n");

  printf ("Entrez un mot : ");
  scanf ("%s", nom);
  empiler (tas, nom);
  printf ("La pile (%d éléments): \n",tas->taille);
  printf("\n********** Haut de la PILE **********\n");
  affiche(tas);
  printf("__________ Bas de la PILE __________\n\n");

  printf ("Entrez un mot : ");
  scanf ("%s", nom);
  empiler (tas, nom);
  printf ("La pile (%d éléments): \n",tas->taille);
  printf("\n********** Haut de la PILE **********\n");
  affiche(tas);
  printf("__________ Bas de la PILE __________\n\n");

  printf ("\nLe dernier entré (LastInFirstOut) [ %s ] sera supprimé",
                  pile_donnee(tas));
  printf ("\nLe dernier entré est supprime\n");
  depiler (tas);              /* suppression de dernier element entre */
  printf ("La pile (%d éléments): \n",tas->taille);
  printf("\n********** Haut de la PILE **********\n");
  affiche(tas);
  printf("__________ Bas de la PILE __________\n\n");

  return 0;
}

VI. Voir aussi


Pour une lecture illimitée hors ligne, vous avez la possibilité de télécharger gratuitement cet article au format PDF :
Les-piles-en-langage-c.pdf

Réalisé sous la direction de , fondateur de CommentCaMarche.net.

A voir également

Dans la même catégorie

Las pilas en lenguaje C
Par Carlos-vialfa le 16 juin 2009
As pilhas em linguagem C
Par pintuda le 26 octobre 2011
Publié par lami20j. - Dernière mise à jour par christelle.b
Ce document intitulé «  Les piles en langage C  » issu de CommentCaMarche (www.commentcamarche.net) est mis à disposition sous les termes de la licence Creative Commons. Vous pouvez copier, modifier des copies de cette page, dans les conditions fixées par la licence, tant que cette note apparaît clairement.