LES PILES ET FILES

definition

Ce sont des structures de donnees ordonnees, mais qui ne permettent l'acces qu'a une seule donnee. On utilise souvent le nom generique de pile pour les piles et les files, un seul nom existant en anglais (stack). Les piles (stack LIFO : Last In First Out) correspondent a une pile d'assiettes : on prend toujours l'element superieur, le dernier empile. Les files (on dit aussi queues) (stack FIFO: First In First Out) correspondent aux files d'attente : on prend toujours le premier element, donc le plus ancien (on ne tolere pas ici les resquilleurs). Les piles et files sont tres souvent utiles : elles servent a memoriser des choses en attente de traitement. Elles permettront une clarification des algorithmes quand effectivement on n'a pas besoin d'acceder directement a tous les elements. Elles sont souvent associees a des algorithmes recursifs. Il n'y a pas de structures specifiques prevues dans les langages (sauf FORTH), il faut donc les creer de toutes pieces. Pour les piles, on utilisera un tableau unidimensionnel (statique ou dynamique) en cas de piles de hauteur maximale previsible (la hauteur de la pile est memorisee par une variable entiere), ou une liste en cas de longueur tres variable (ne pas oublier que dans ce cas on a un surcout en memoire d'autant de liens (pointeurs) que d'elements empiles). Pour les files, l'utilisation d'un tableau necessite deux variables : la position du premier et celle du dernier. La suppression du premier element ne se fait pas par decalage des suivants mais en incrementant la variable indiquant le premier. La gestion est alors un peu plus complexe que pour les piles, puisque le suivant de la fin du tableau est le debut du tableau (en fait, l'indice du suivant est l'indice plus 1, modulo la taille du tableau. La fonction modulo est en fait tres rapide pour les nombres correspondants a une puissance de 2, a condition de l'implanter a l'aide d'un masquage. L'utilisation d'une liste pour une file par contre est aussi simple que pour une pile.

fonctions de base

Les fonctions de base pour les piles sont l'empilage et le depilage, pour les files l'enfilage et le defilage. Dans les deux cas on prevoira egalement un fonction d'initialisation, et une fonction indiquant si la pile est vide. Seules ces fonctions de base dependent de la methode reelle de mise en oeuvre (tableau, liste,...). Tous les algorithmes n'utiliseront que ces fonctions. C'est le grand avantage des piles et files, puisque l'on va pouvoir modifier facilement le type d'implantation en memoire sans reecrire les programme. Ceci permet de tester d'abord la faisabilite du programme sur des petites quantites de donnees puis seulement on l'optimise pour l'utilisation reelle. Pour une implantation par tableaux, on ecrira par exemple, pour une pile de flottants (base_p_t) :
#define dim_pile 100
#define composante float
/* static pour empecher l'acces direct exterieur*/
static composante pile[dim_pile]; 
static int sommet;

void init_pile(void)
{sommet=0;}

int pile_vide(void)
{return(sommet=0);}

int empiler(composante x)
/* retourne 0 si pas d'erreur (donc il restait de la place dans la pile) */
{
 if(sommet<dim_pile)
   {pile[sommet++]=x;return(0);}
 else
   {puts("pile saturee");return(1);}
}

composante depiler(void)
{
 if (sommet>0) return(pile[--sommet]);
 else puts("pile vide");return(0);
}
Si l'on desire un dimensionnement totalement dynamique de la pile, on utilisera une liste (base_p_l) :
#include <alloc.h>
#include <stdio.h>
#define composante float
typedef struct s_comp
   {composante val;struct s_comp *prec;}type_comp;

static type_comp *sommet=NULL;

int empiler(composante x)
/* retourne 0 si pas d'erreur (donc il restait de la place dans la pile)*/
{
 type_comp *nouv;
 if((nouv=(type_comp*)malloc(sizeof(type_comp)))!=NULL)
  {
   nouv->val=x;
   nouv->prec=sommet;
   sommet=nouv;
   return(0);}
 else
   {puts("pile saturee");return(1);}
}

composante depiler(void)
{
 composante x;
 if (sommet!=NULL)
  {
   x=sommet->val;
   free(sommet);  /*pour plus de surete, on peut passer par
                      une variable*/
   sommet=sommet->prec;
   return(x);
  }
 else puts("pile vide");return(0);
}

void init_pile(void)
{while(sommet!=NULL)depiler();}

int pile_vide(void)
{return(sommet==NULL);}
Pour certaines applications, on pourra preferer ne pas liberer la memoire au depilage pour gagner du temps : au depilage, mais aussi a l'empilage, on ne prend du temps que s'il faut agrandir la pile. On peut egalement utiliser une pile de tableaux dynamiques, ce qui permet d'economiser de la place memoire, sans etre limite en taille.

Pour les files, l'implantation des fonctions de base est similaire, par exemple par tableaux (base_f_t) :

#define dim_file 100
#define composante float
static composante file[dim_file]; 
static int bas,sommet,taille;
#define suiv(i) ((i)<dim_file-1 ? ((i)+1) : 0)

void init_file(void)
{bas=sommet=taille=0;}

int file_vide(void)
{return(taille=0);}

int enfiler(composante x)
/* retourne 0 si pas d'erreur (donc il restait de la place dans la pile)
*/
{
 if(taille<dim_file)
   {file[sommet]=x;sommet=suiv(sommet);taille++;return(0);}
 else
   {puts("file saturee");return(1);}
}

composante depiler(void)
{
 composante x;
 if (taille>0) {x=file[bas];bas=suiv(bas);taille--;return(x);}
 else {puts("file vide");return(0);}
}
Il faut prevoir un indice pour chaque extremite de la file. Il en serait de meme pour une implantation par liste chainee (un pointeur pour chaque extremite).

utilisations

Les piles sont souvent necessaires pour rendre iteratif un algorithme recursif. Une application courante des piles est pour les calculs arithmetiques: l'ordre dans la pile permet d'eviter l'usage des parentheses. Il existe trois possibilites pour representer une equation (du moins de maniere unidimensionnelle, les arbres en sont une generalisation bidimensionnelle), suivant la position relative des operateurs et de leurs operandes. Il faut avant tout definir l'arite d'une operation : une operation unaire necessite un operateur (- unaire, cosinus, log, factorielle...), une operation deuxaire (denomination P. Trau, pour differencier d'une operation binaire qui pour moi traite des nombres en base 2) necessite deux arguments (+, -, *, /, produit vectoriel,...), une operation ternaire necessite trois operandes (produit mixte,...). La notation prefixee (dite polonaise) consiste a placer l'operateur, suivi de ses arguments. La notation postfixee (polonaise inverse) consiste a placer les operandes devant l'operateur. La notation infixee (parenthesee) consiste a entourer les operateurs deuxaires par leurs operandes, pour les autres arites on place l'operateur en premier, suivi de ses operandes (entre parentheses, separes par des virgules pour les operateurs ternaires). Les parentheses sont necessaires uniquement en notation infixee, certaines regles permettent d'en reduire le nombre (priorite de la multiplication par rapport a l'addition, en cas d'operations unaires representees par un caractere special (-, !,...). Les notations prefixee et postfixee sont d'un emploi plus facile puisqu'on sait immediatement combien d'operandes il faut rechercher. Detaillons ici la saisie et l'evaluation d'une expression postfixee (polonais) : on modifie le type de composantes de la pile (et donc les fonctions de base) : 
#define operande 1
#define operateur 0

typedef struct
    {int type;
     union {float op_r;char op_c;}val;
    }composante;
void saisie(void)
/* marche pour toute notation puisque ne verifie rien */
 {
  composante x;
  char txt[100],*deb;
  char rep;
  init_pile();
  printf("entrez operandes (nombres) et operateurs (+,-,*,/,C (cos),S)\n");
  printf("separes par des blancs ou virgules\n");
  fflush(stdin);
  gets(txt); /* on lit un texte qui sera traite par apres */
  deb=txt; /* deb pointe le debut du texte non encore traite */
  do
   {
    while(*deb==' '||*deb==',') deb++;
    if(*deb==0)break;
    if(isdigit(*deb)||*deb=='.'||(*deb=='-'&&isdigit(*(deb+1))))
     {
      x.type=operande;
      sscanf(deb,"%f",&(x.val.op_r));
      empiler(&x);
      while(isdigit(*deb)||*deb=='.') deb++; /*pointer la suite*/
     }
    else /*cas d'un operateur */
     {
      x.val.op_c=toupper(*(deb++));
      x.type=operateur;
      empiler(&x);
     }
   }
  while(1);
 }

float eval_post(void)
 {
  float r1,r2;
  composante x;
  if(depiler(&x)!=0) {puts("expression non postfixee");return(0);}
  if(x.type==operande) return(x.val.op_r);
  /* else inutile car les autres cas se finissent par return */
  /* on traite d'abord les operateurs unaires */
  if (x.val.op_c=='C') return(cos(eval_post()));
  if (x.val.op_c=='S') return(sin(eval_post()));
  /* les deuxaires maintenant */
  r2=eval_post();
  r1=eval_post();
  switch (x.val.op_c)
   {
    case '+':return(r1+r2);
    case '-':return(r1-r2);
    case '*':return(r1*r2);
    case '/':return(r1/r2);
   }
  puts("erreur (code operatoire inconnu par exemple)");
  return(0);
 }

void main(void)
 {
  saisie();
  printf("l'expression postfixee vaut %6.1f\n",eval_post());
 }
Les piles permettent tres souvent de clarifier l'implantation d'un algorithme, bien qu'evidemment on puisse utiliser le principe tout en n'utilisant que des tableaux ou listes.