Cours 3: Le type Pile.

Voici la signature du type abstrait Pile .

Pile creer_pile();
Element_pile sommet_pile(Pile p);
Pile empiler_pile(Pile p, Element_pile e);
Pile depiler_pile(Pile p);
unsigned int est_vide_pile(Pile p);
// p: Pile; e: Element_pile;
// préconditions
//  depiler_pile(p) est-défini-ssi est_vide_pile(p) == 0
//  sommet_pile(p) est-défini-ssi est_vide_pile(p) == 0
// axiomes
//  depiler_pile(empiler_pile(p, e)) == p
//  sommet_pile(empiler_pile(p, e)) == e
//  est_vide_pile(creer_pile()) != 0
//  est_vide_pile(empiler(p, e)) == 0

Les préconditions imposent qu'on ne puisse ni dépiler, ni consulter le sommet d'une pile vide.
Le premier axiome indique qu'en empilant puis dépilant, on laisse la pile inchangée (l'élément dépilé est donc celui qui vient d'être empilé).
Le second axiome montre qu'après avoir empilé un élément e , on le trouve au sommet de la pile.
Le troisième axiome affirme qu'une nouvelle pile est vide à sa création.
Le quatrième axiome précise qu'une pile n'est plus vide après un empilement.

Une pile est-elle une variété de liste? Dans l'affirmative, on dérive la définition du type Pile de celui du type Liste.
L'empilement et le dépilement peuvent se concevoir comme des accès à la tête de liste: empiler écrit en tête ( inserer_liste(l, 0, e) ) alors que dépiler supprime la tête ( supprimer_liste(l, 0) ).
Cela montre qu'une pile est une liste dans laquelle on accède en tête.
L'empilement peut encore s'exprimer comme une écriture en queue ( inserer_liste(l, longueur_liste(l), e) et le dépilement comme la suppression de l'élément de queue ( supprimer_liste(l, longueur_liste(l) - 1) .
Cela montre qu'une pile est aussi une liste dans laquelle on accède en queue.

Voici une implémentation de pile en table (la taille de la pile est fixée à sa création), exprimée à partir de la spécification d'une liste en table.

// fichier pile_en_table.c
#include <stdio.h>
#include "pile_en_table.h"
#include "liste_en_table.h"
Pile creer_pile() {
 Liste l;
 l = creer_liste();
 return (Pile)l;
}
Element_pile sommet_pile(Pile p) {
// précondition est_vide_pile(p) == 0
 if (est_vide_pile(p)) {
   fprintf(stderr, "sommet_pile: pile vide\n");
   exit(1);
 }
 return lire_liste((Liste)p, longueur_liste((Liste)p) - 1);
}
Pile empiler_pile(Pile p, Element_pile e) {
 unsigned int longueur;
 longueur = longueur_liste((Liste)p);
 Liste l;
 if (longueur == TAILLE_LISTE) {
   fprintf(stderr, "empiler_pile: pile pleine\n");
   exit(1);
 }
 l = inserer_liste((Liste)p, longueur, e);
 return (Pile)l;
}
Pile depiler_pile(Pile p) {
// précondition est_vide_pile(p) == 0
 Liste l;
 if (est_vide_pile(p)) {
   fprintf(stderr, "depiler_pile: pile vide\n");
   exit(1);
 }
 l = supprimer_liste((Liste)p, longueur_liste((Liste)p) - 1);
 return (Pile)l;
}
unsigned int est_vide_pile(Pile p) {
 return (!longueur_liste((Liste)p));
}

Le code ci-dessus fait apparaître que nous avons privilégié des accès en queue de liste pour effectuer empilement et dépilement. Cela vient de l'implémentation des listes en table. Dans l'implémentation du cours précédent, une suppression en tête de liste se traduit par un tassement du tableau et une insertion en tête provoque un décalage du tableau d'un cran à droite. En revanche, une suppression en queue n'effectue qu'une mise à jour de la longueur de la liste et une insertion en queue ne fait qu'écrire l'élément à sa place.
Voici le fichier pile_en_table.h

// fichier pile_en_table.h
#include "pile.h"
#include "liste_en_table.h"
#define TAILLE_PILE TAILLE_LISTE

Voici le fichier pile.h .

// fichier pile.h
#include "pile_def.h"
#include "element_pile_def.h"
Pile creer_pile();
Element_pile sommet_pile(Pile p);
Pile empiler_pile(Pile p, Element_pile e);
Pile depiler_pile(Pile p);
unsigned int est_vide_pile(Pile p);
// p: Pile; e: Element_pile;
// préconditions
//  depiler_pile(p) est-défini-ssi est_vide_pile(p) == 0
//  sommet_pile(p) est-défini-ssi est_vide_pile(p) == 0
// axiomes
//  depiler_pile(empiler_pile(p, e)) == p
//  sommet_pile(empiler_pile(p, e)) == e
//  est_vide_pile(creer_pile()) != 0
//  est_vide_pile(empiler(p, e)) == 0

Voici le fichier pile_def.h

// fichier pile_def.h
typedef void *Pile;

Voici le fichier main_table.c qui met en œuvre le type pile en table.
On peut remarquer la façon dont on s'assure que la pile n'est pas pleine avant de tenter un empilement. La constante TAILLE_PILE est définie et rendue visible par le fichier pile_en_table.h . Comme on ne dispose d'aucune fonction donnant le nombre d'éléments empilés (cela ne fait pas partie de notre spécification d'une pile), on tient à jour un compteur de la profondeur de pile.

// fichier main_table.c
#include <stdio.h>
#include "element_int_pile.h"
#include "pile_en_table.h"
#define TAILLE_REP 128
main() {
 Pile p;
 Element_pile e;
 int i;
 unsigned int profondeur;
 char rep[TAILLE_REP];
 p = creer_pile();
 profondeur = 0;
 do {
  afficher_menu();
  fgets(rep, TAILLE_REP, stdin);
  if (rep[0] == 'q') exit(0);
  switch (rep[0]) {
   case 'd':
     if (est_vide_pile(p)) printf("pile vide\n");
     else {
      p = depiler_pile(p);
      profondeur--;
     }
     break;
   case 'e':
     if (profondeur == TAILLE_PILE) printf("pile pleine\n");
     else {
      sscanf(&rep[1], "%d", &i);
      e = creer_element_pile();
      e = ecrire_element_pile(e, i);
      p = empiler_pile(p, e);
      profondeur++;
     }
     break;
   case 's':
     if (est_vide_pile(p)) printf("pile vide\n");
     else printf("%d\n", lire_element_pile(sommet_pile(p)));
     break;
   case 'v':
     if (est_vide_pile(p)) printf("vrai\n");
     else printf("faux\n");
     break;
  }
 } while (1);
}
afficher_menu() {
 printf("menu:\n");
 printf("  (q)uitter\n");
 printf("  (e)mpiler (i)\n");
 printf("  (d)épiler\n");
 printf("  la pile est-elle (v)ide?\n");
 printf("  afficher le (s)ommet de pile\n");
}

Voici le makefile.

# fichier make_pile_en_table
main_table: main_table.o liste_en_table.o pile_en_table.o element_int_pile.o
        cc -o main_table main_table.o liste_en_table.o pile_en_table.o element_int_pile.o
main_table.o: main_table.c pile_en_table.h pile.h pile_def.h element_pile_def.h element_int_pile.h
        cc -c main_table.c
pile_en_table.o: pile_en_table.c pile_en_table.h pile.h pile_def.h liste_en_table.h liste.h liste_def.h element_pile_def.h
        cc -c pile_en_table.c
liste_en_table.o: liste_en_table.c liste.h liste_en_table.h liste_def.h element_pile_def.h
        cc -c liste_en_table.c
element_int_pile.o: element_int_pile.c element_int_pile.h element_pile_def.h
        cc -c element_int_pile.c

Voici maintenant une implémentation de pile en liste chaînée.

// fichier pile_en_chaine.c
#include <stdio.h>
#include "pile.h"
#include "liste.h"
Pile creer_pile() {
 Liste l;
 l = creer_liste();
 return (Pile)l;
}
Element_pile sommet_pile(Pile p) {
// précondition est_vide_pile(p) == 0
 if (est_vide_pile(p)) {
   fprintf(stderr, "sommet_pile: pile vide\n");
   exit(1);
 }
 return lire_liste((Liste)p, 0);
}
Pile empiler_pile(Pile p, Element_pile e) {
 Liste l;
 l = inserer_liste((Liste)p, 0, e);
 return (Pile)l;
}
Pile depiler_pile(Pile p) {
// précondition est_vide_pile(p) == 0
 Liste l;
 if (est_vide_pile(p)) {
   fprintf(stderr, "depiler_pile: pile vide\n");
   exit(1);
 }
 l = supprimer_liste((Liste)p, 0);
 return (Pile)l;
}
unsigned int est_vide_pile(Pile p) {
 return (!longueur_liste((Liste)p));
}

On remarquera que cette fois on a opté pour des accès en tête de liste (on insère et on supprime au rang 0). En effet, des accès en queue auraient provoqué un parcours de la liste.

Voici le fichier main_chaine.c de mise en œuvre.

// fichier main_chaine.c
#include <stdio.h>
#include "element_int_pile.h"
#include "pile.h"
#define TAILLE_REP 128
main() {
 Pile p;
 Element_pile e;
 int i;
 char rep[TAILLE_REP];
 p = creer_pile();
 do {
  afficher_menu();
  fgets(rep, TAILLE_REP, stdin);
  if (rep[0] == 'q') exit(0);
  switch (rep[0]) {
   case 'd':
     if (est_vide_pile(p)) printf("pile vide\n");
      else p = depiler_pile(p);
     break;
   case 'e':
     sscanf(&rep[1], "%d", &i);
     e = creer_element_pile();
     e = ecrire_element_pile(e, i);
     p = empiler_pile(p, e);
     break;
   case 's':
     if (est_vide_pile(p)) printf("pile vide\n");
     else printf("%d\n", lire_element_pile(sommet_pile(p)));
     break;
   case 'v':
     if (est_vide_pile(p)) printf("vrai\n");
     else printf("faux\n");
     break;
  }
 } while (1);
}
afficher_menu() {
 printf("menu:\n");
 printf("  (q)uitter\n");
 printf("  (e)mpiler (i)\n");
 printf("  (d)épiler\n");
 printf("  la pile est-elle (v)ide?\n");
 printf("  afficher le (s)ommet de pile\n");
}

Voici le fichier make_pile_en_chaine .

# fichier make_pile_en_chaine
main_chaine: main_chaine.o liste_en_chaine.o pile_en_chaine.o element_int_pile.o
        cc -o main_chaine main_chaine.o liste_en_chaine.o pile_en_chaine.o element_int_pile.o
main_chaine.o: main_chaine.c liste.h liste_def.h pile.h pile_def.h element_pile_def.h element_int_pile.h
        cc -c main_chaine.c
pile_en_chaine.o: pile_en_chaine.c liste.h liste_def.h pile.h pile_def.h element_pile_def.h
        cc -c pile_en_chaine.c
liste_en_chaine.o: liste_en_chaine.c liste.h liste_def.h element_pile_def.h
        cc -c liste_en_chaine.c
element_int_pile.o: element_int_pile.c element_int_pile.h element_pile_def.h
        cc -c element_int_pile.c