LES PILES ET FILES

définition
fonctions de base
utilisations

définition

Ce sont des structures de données ordonnées, mais qui ne permettent l'accès qu'à une seule donnée. On utilise souvent le nom générique de pile pour les piles et les files, un seul nom existant en anglais (stack). Les piles (stack LIFO : Last In First Out) correspondent à une pile d'assiettes : on prend toujours l'élément supérieur, le dernier empilé. Les files (on dit aussi queues) (stack FIFO: First In First Out) correspondent aux files d'attente : on prend toujours le premier élément, donc le plus ancien (on ne tolère pas ici les resquilleurs). Les piles et files sont très souvent utiles : elles servent à mémoriser des choses en attente de traitement. Elles permettront une clarification des algorithmes quand effectivement on n'a pas besoin d'accéder directement à tous les éléments. Elles sont souvent associées à des algorithmes récursifs. Il n'y a pas de structures spécifiques prévues dans les langages (sauf FORTH), il faut donc les créer de toutes pièces. Pour les piles, on utilisera un tableau unidimensionnel (statique ou dynamique) en cas de piles de hauteur maximale prévisible (la hauteur de la pile est mémorisée par une variable entière), ou une liste en cas de longueur très variable (ne pas oublier que dans ce cas on a un surcoût en mémoire d'autant de liens (pointeurs) que d'éléments empilés). Pour les files, l'utilisation d'un tableau nécessite deux variables : la position du premier et celle du dernier. La suppression du premier élément ne se fait pas par décalage des suivants mais en incrémentant 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 début du tableau (en fait, l'indice du suivant est l'indice plus 1, modulo la taille du tableau. La fonction modulo est en fait très rapide pour les nombres correspondants à une puissance de 2, à condition de l'implanter à 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 dépilage, pour les files l'enfilage et le défilage. Dans les deux cas on prévoira également un fonction d'initialisation, et une fonction indiquant si la pile est vide. Seules ces fonctions de base dépendent de la méthode réelle 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 mémoire sans réécrire les programme. Ceci permet de tester d'abord la faisabilité du programme sur des petites quantités de données puis seulement on l'optimise pour l'utilisation réelle. Pour une implantation par tableaux, on écrira par exemple, pour une pile de flottants (base_p_t) :

#define dim_pile 100
#define composante float
/* static pour empêcher l'accès direct extérieur*/
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 saturée");return(1);}
}

composante depiler(void)
{
 if (sommet>0) return(pile[--sommet]);
 else puts("pile vide");return(0);
}

Si l'on désire 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 saturée");return(1);}
}

composante depiler(void)
{
 composante x;
 if (sommet!=NULL)
  {
   x=sommet->val;
   free(sommet);  /*pour plus de sûreté, 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 préférer ne pas libérer la mémoire au dépilage pour gagner du temps : au dépilage, mais aussi à l'empilage, on ne prend du temps que s'il faut agrandir la pile. On peut également utiliser une pile de tableaux dynamiques, ce qui permet d'économiser de la place mémoire, sans être limité 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 saturée");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 prévoir un indice pour chaque extrémité de la file. Il en serait de même pour une implantation par liste chaînée (un pointeur pour chaque extrémité).

utilisations

Les piles sont souvent nécessaires pour rendre itératif un algorithme récursif. Une application courante des piles est pour les calculs arithmétiques: l'ordre dans la pile permet d'éviter l'usage des parenthèses. Il existe trois possibilités pour représenter une équation (du moins de manière unidimensionnelle, les arbres en sont une généralisation bidimensionnelle), suivant la position relative des opérateurs et de leurs opérandes. Il faut avant tout définir l'arité d'une opération : une opération unaire nécessite un opérateur (- unaire, cosinus, log, factorielle...), une opération deuxaire (dénomination P. Trau, pour différencier d'une opération binaire qui pour moi traite des nombres en base 2) nécessite deux arguments (+, -, *, /, produit vectoriel,...), une opération ternaire nécessite trois opérandes (produit mixte,...). La notation préfixée (dite polonaise) consiste à placer l'opérateur, suivi de ses arguments. La notation postfixée (polonaise inverse) consiste à placer les opérandes devant l'opérateur. La notation infixée (parenthèsée) consiste à entourer les opérateurs deuxaires par leurs opérandes, pour les autres arités on place l'opérateur en premier, suivi de ses opérandes (entre parenthèses, séparés par des virgules pour les opérateurs ternaires). Les parenthèses sont nécessaires uniquement en notation infixée, certaines règles permettent d'en réduire le nombre (priorité de la multiplication par rapport à l'addition, en cas d'opérations unaires représentées par un caractère spécial (-, !,...). Les notations préfixée et postfixée sont d'un emploi plus facile puisqu'on sait immédiatement combien d'opérandes il faut rechercher. Détaillons ici la saisie et l'évaluation d'une expression postfixée (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 vérifie rien */
 {
  composante x;
  char txt[100],*deb;
  char rep;
  init_pile();
  printf("entrez opérandes (nombres) et opérateurs (+,-,*,/,C (cos),S)\n");
  printf("séparés par des blancs ou virgules\n");
  fflush(stdin);
  gets(txt); /* on lit un texte qui sera traité par après */
  deb=txt; /* deb pointe le début du texte non encore traité */
  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 opérateur */
     {
      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 postfixée");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 opérateurs 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 opératoire inconnu par exemple)");
  return(0);
 }

void main(void)
 {
  saisie();
  printf("l'expression postfixée vaut %6.1f\n",eval_post());
 }

Les piles permettent très souvent de clarifier l'implantation d'un algorithme, bien qu'évidemment on puisse utiliser le principe tout en n'utilisant que des tableaux ou listes.