PROGRAMMATION AVANCEE
2AP 2023/2024
PR. MOHAMMED BAIDADA
Les Piles et les files
1. Définition
Les piles et les files sont des structures de données très utilisées en informatique, surtout dans les
langages de programmation (appel de procédures, ordonnancement système,…).
Elles constituent ce qu’on appelle des structures abstraites de données (SAD), puisqu’elles peuvent
être implémentées de plusieurs façons : en utilisant des tableaux ou des listes à simple chainage,
ou autre.
Une pile est une structure dans laquelle on ne peut introduire ou enlever un élément qu'à une
extrémité appelée tête de pile ou sommet de pile. Exemple : une pile de livres, une pile d’assiettes,
une pile à un jeu de cartes si l’on se refuse le droit de manipuler plus d’un de leurs éléments à la
fois. Noter que dans une pile, le dernier élément inséré sera le premier à être supprimé, retiré : on
parle de liste LIFO ‘Last In First Out’.
Une file, quant à elle, est gérée par l’algorithme ‘First In First Out’, c’est-à-dire que le premier
élément qui entre dans la file sera le premier qui sort. Exemple : une file d’attente.
2. Opérations sur les piles et les files
Pour manipuler une pile ou une file, on a besoin de créer ce qu’on appelle des primitives. Il s’agit
de fonctions usuelles pour exécuter toutes les actions de base. Nous allons présenter dans ce qui
suit, les primitives pour le cas d’une pile, celui d’une file pourra être déduit par analogie.
Notons aussi que pour ces primitives, nous allons donner le cas d’une implémentation avec une
liste à simple chainage.
Les primitives représentant les opérations de base sur les piles sont très simples.
- Empiler (p,e) : empile l’élément e dans la pile p
- Dépiler (p) : dépile un élément de la pile et retourne la valeur de cet élément (e = Depiler (p))
Avec une liste chainée, il n’y a aucune limite au nombre d’éléments qu’on peut empiler. Par contre,
on ne peut dépiler d’une pile vide. À cet effet, on a une fonction PileVide(p) qui retourne Vrai si
la pile est vide sinon Faux.
InitialiserPile(p) ou ViderPile(p) : vide la pile p
On peut vouloir aussi connaître le sommet de pile sans le supprimer (dépiler).
e= SommetDePile(p) : Ce n’est pas réellement une nouvelle opération car on peut l’exprimer
comme suit :
e = Dépiler (p)
Empiler (e,p)
1 [Link]
PROGRAMMATION AVANCEE
2AP 2023/2024
PR. MOHAMMED BAIDADA
SommetDePile() et Dépiler() ne fonctionnent pas sur une pile vide. Aussi, on ne peut empiler dans
une pile pleine.
Application : Évaluation d’une expression postfixée :
L’expression A+B est une expression en notation infixe (l’opérateur se trouve entre les opérandes).
Il existe deux autres notations pour les expressions arithmétiques :
- La notation préfixée, exemple: +AB; l’opérateur est placé avant les opérandes.
- La notation postfixée ou notation polonaise, exemple: AB+; l’opérateur est placé après les
opérandes.
Quand on écrit A+B*C on doit connaître la priorité des opérateurs. C’est équivalent à A+(B*C).
Pour convertir l’expression A+(B*C) en postfixée on effectue les étapes suivantes : A+(B*C)
devient A+(BC*) qui s’écrit ABC*+
Pour traduire une expression arithmétique (infixe) en une expression en notation polonaise, il faut
:
- Convertir la partie la plus prioritaire
- La partie convertie est ensuite considérée comme un opérande.
Exemple : (A+B)*C → (AB+)*C → AB+C*
(A+B)*(C-D) → AB+CD-*
NB :
- Pour les nombres dépassant les dizaines, il faut les décomposer en notation exponentielle (notée
$), avant de les convertir en post ou préfixé. Il y a aussi une technique plus simple consistant à
séparer les éléments de la représentation par des espaces.
- Noter qu’il n’y a pas de parenthèses dans les expressions postfixées.
- L’ordre des opérateurs détermine l’ordre des opérations.
Exemple en C (compilé)
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<malloc.h>
typedef struct noeud
{
float info;
struct noeud * suivant;
}Pile;
2 [Link]
PROGRAMMATION AVANCEE
2AP 2023/2024
PR. MOHAMMED BAIDADA
int pileVide(Pile * pile)
{
if(pile==NULL) return 1;
else return 0;
}
void empiler(Pile * * pile,float i)
{
Pile * nouveau;
nouveau=(Pile *)malloc(sizeof(Pile));
nouveau->info=i;
nouveau->suivant=*pile;
*pile=nouveau;
}
float depiler(Pile ** pile)
{
float r;
r=(*pile)->info;
Pile * p=*pile;
*pile=(*pile)->suivant;
free(p);
return r;
}
void afficherPile(Pile * pile)
{
while(pile!=NULL)
{
printf("%f\t",pile->info);
pile=pile->suivant;
}
}
static char * convertir(char car)
{
static char r[2];
r[0]=car;
r[1]='\0';
return r;
}
float evaluer(char exp[])
{
int l=strlen(exp),i;
Pile * pile=NULL;
3 [Link]
PROGRAMMATION AVANCEE
2AP 2023/2024
PR. MOHAMMED BAIDADA
float x,y,r;
for(i=0;i<l;i++)
{
if(isdigit(exp[i]))
{
empiler(&pile,atof(convertir(exp[i])));
}
else //exp[i] est un operateur
{
x=depiler(&pile);
y=depiler(&pile);
switch(exp[i])
{
case '+' : r=x+y; break;
case '-' : r=y-x; break;
case '*' : r=x*y; break;
case '/' : r=y/x; break;
}
empiler(&pile,r);
}
}
return(depiler(&pile));
}
int main()
{
char exp[]="743*2*-2/";
printf("%s = %.2f",exp,evaluer(exp));
}
4 [Link]
