5.

Les Piles et Les files

Cours Algorithmique LMSD1 2024-2025 -64- Mr Khaled GHARDALLOU

 1. Les Piles (Stack)
Une pile est une liste chaînée d'informations dans laquelle :

• Un élément ne peut être ajouté qu'au sommet de la pile

• Un élément ne peut être retiré que du sommet de la pile.
Il s'agit donc d'une structure de type LIFO (Last In First Out). On ne
travaille que sur le sommet de la pile. Les piles sont comparables à des
piles d'assiettes

On associe à une pile les termes de :

• PUSH pour empiler c'est-à-dire ajouter un élément,
• POP pour dépiler c'est-à-dire supprimer un élément.

Les piles servent à revenir à l'état précédent et sont utilisées pour :

• Implanter les appels de procédures (pour revenir à l'état d'avant
l'appel)
• Annuler une commande
• Évaluer des expressions arithmétiques
• etc.
a) Les opérations autorisées
Les opérations autorisées avec une pile sont :

Cours Algorithmique LMSD1 2024-2025 -65- Mr Khaled GHARDALLOU

 • Empiler, toujours au sommet, et jusqu’à la limite de la mémoire
• Dépiler, toujours au sommet, si la pile n’est pas vide
• vérifier si la pile est vide ou non
b) Déclaration d’une pile
La déclaration est identique à celle d'une liste chaînée, par exemple
pour une pile de type quelconque :

t désigne un type quelconque

Type :
Cellule = Enregistrement
info : t
Suivant : ^Cellule
Fin Enregistrement
Type Pile = ^Cellule
c) Empiler (PUSH)
Empiler un élément revient à faire une insertion en tête dans la liste
chaînée.

Procedure Empiler (REF Tete : Pile, Val : t)

Var :
I : ^Cellule /* pointeur sur le nouveau élément à empiler/*
Début
Allouer(I) /*Création dynamique d’un nouvel élément/*
I^.info ← Val
I^.Suivant ← Tete /* liaison entre I et Tête /*
Tete ← I /* Modifier la valeur de Tête/*
Fin

d) Dépiler (POP)
Dépiler revient à faire une suppression en tête.

Cours Algorithmique LMSD1 2024-2025 -66- Mr Khaled GHARDALLOU

 Procedure Depiler (REF Tete : Pile)
Var :
P : ^Cellule /* pointeur sur l’élément au sommet à dépiler/*
Début
Si Tete <> Null alors /* Vérifier si la pile est vide */
P ← Tete /* sauvegarder l’élément au sommet à dépiler/*
Tete ← Tete^.Suivant /* Tete va pointer sur le 2ème
élément /*
Libérer(P) /* Modifier la valeur de Tête/*
Fin SI
Fin
e) Pile est Vide
Fonction PileVide (Tête : Pile) : booléen /* indique si la pile est vide
ou non*/ DEBUT
Retourner (Tête = Null)
FIN

f) Sommet (PEEK)
Fonction SommetPile (Tête : Pile) : t /* renvoie la valeur du sommet
*/
DEBUT
Retourner Tête^.Info
FIN

2. Les Files (Queue)

Une file, ou file d'attente, est une liste chaînée d'informations dans
laquelle :

• Un élément ne peut être ajouté qu'à la queue de la file

• Un élément ne peut être retiré qu'à la tête de la file.

Cours Algorithmique LMSD1 2024-2025 -67- Mr Khaled GHARDALLOU

 Il s'agit donc d'une structure de type FIFO (First In First Out). Les
données sont retirées dans l’ordre où elles ont été ajoutées. Une file est
comparable à une queue de clients à la caisse d'un magasin.

Les files servent à traiter les données dans l'ordre où on les a reçues
et permettent de :

• Gérer des processus en attente d'une ressource système (par

exemple la liste des travaux à éditer sur une imprimante)
• Construire des systèmes de réservation
• etc.
Pour ne pas avoir à parcourir toute la liste au moment d'ajouter un
élément en queue, on peut maintient un pointeur de queue. Attention une
file peut très bien être simplement chaînée même s'il y a un pointeur de
queue.

Cours Algorithmique LMSD1 2024-2025 -68- Mr Khaled GHARDALLOU

 a) Opérations autorisées
Les opérations autorisées avec une file sont :

• Enfiler toujours à la queue et jusqu’à la limite de la mémoire,

• Défiler toujours à la tête si la file n’est pas vide,
• Vérifier si la file est vide ou non
b) Déclaration d’une File
La déclaration est identique à celle d'une liste chaînée, Le pointeur
de tête pointe sur le premier élément de la file, et le pointeur de queue
sur le dernier.

t désigne un type quelconque

Type :
Cellule = Enregistrement
info : t
Suivant : ^Cellule
Fin Enregistrement
File = ^Cellule
Var :
Tete : File
Queue : File

c) Enfiler
Enfiler un élément consiste à l'ajouter en queue de liste. Il faut
envisager le cas particulier où la file était vide. En effet, dans ce cas, le
pointeur de tête doit être modifié.

Cours Algorithmique LMSD1 2024-2025 -69- Mr Khaled GHARDALLOU

 Procedure Enfiler (Ref Tete, Queue : File, Valeur : t)
Var :
P : File /* Pointeur pour le nouvel élément */
DEBUT
Allouer(P) /* Réserve de l’espace mémoire pour P*/
P^.Info ← Valeur
P^.Suivant ← Null /* (ce sera le dernier de la file) */
SI Tete = Null ALORS /* file vide */
Tete ← P
SINON /* il y a au moins un élément */
Queue^.Suivant ← P /*le nouvel élément est ajouté à la fin*/
FINSI
Queue ← P /*Queue pointe maintenant sur l'élément ajouté */
FIN

On peut aussi faire référence à la procédure InsertionFin dans le

chapitre Listes chainées simple « Insertion d’un élément à la fin d’une
liste » sans utiliser le pointeur Queue

d) Défiler
Défiler consiste à supprimer l'élément de tête si la file n'est pas vide.
Si la file a un seul élément, il faut mettre à jour le pointeur de queue car on
vide la file. Il faut conserver l'adresse de l'élément qu'on supprime pour
libérer sa place.

Cours Algorithmique LMSD1 2024-2025 -70- Mr Khaled GHARDALLOU

 Procedure Defiler (Ref Tete, Queue : File)
Var :
P : File /* Pointeur pour le nouvel élément */
DEBUT
SI Tete <> Null ALORS /* file n’est pas vide */
P ← Tete /* on sauvegarde l'adresse de tête */
Tete ← Tete^.Suivant /* Tête pointe sur le 2ème élément */
Libérer(P)
Si Tete = Null ALORS
Queue ← NULL /* si la file a été vidée */
FinSI
FINSI
FIN

On peut aussi faire référence à la procédure

SupprimerPremierElement dans le chapitre Listes chainées simple
« Supprimer le premier élément d'une liste chaînée » sans utiliser le
pointeur queue

3. Évaluation d'expressions mathématiques avec les piles

On s'intéresse à l'évaluation d'expressions mathématiques simples
contenant des opérandes, des opérateurs, et des fonctions. Par exemple :

a + b ∗ (c + d) + e

Cours Algorithmique LMSD1 2024-2025 -71- Mr Khaled GHARDALLOU

 a,b,c,d et e sont des opérandes. Il peut s'agir de nombres. +,* sont
des opérateurs, qui agissent sur deux opérandes. Pour évaluer ce type
d'expression, il faut utiliser les règles de calcul associées à cette notation.

a) Priorités des opérateurs

Considérons l'expression suivante : « a + b ∗ c » La multiplication doit
être exécutée avant l'addition, c'est-à-dire que l'on doit sommer a et b ∗ c.
La multiplication a une priorité supérieure à l'addition. De même, la
division est prioritaire sur l'addition (et la soustraction)

b) Associativité
Considérons l'expression suivante : « a − b + c » Elle se calcule
comme « (a − b) + c » et non pas comme a − (b + c). On dit que les
opérateur addition et soustraction (qui ont la même priorité) sont
associatifs à gauche.

De même l'expression : « a/b ∗ c » se calculer comme (a/b) ∗ c et non

pas comme a/(b ∗ c). Les opérateurs multiplication et division sont
associatifs à gauche. L'opérateur de puissance est prioritaire sur la
multiplication, et il est associatif à droite avec lui-même.

c) Notations infixées et suffixées

La notation « a + b » pour l'addition est appelée notation infixée, car
le symbole + est placé en infixe par rapport aux opérandes.

Cours Algorithmique LMSD1 2024-2025 -72- Mr Khaled GHARDALLOU

 Une autre notation consiste à placer l'opérateur en préfixe : « + a b »
Cette notation est aussi appelée notation polonaise, en raison de la
nationalité du mathématicien qui l'a introduite.

Une notation plus intéressante consiste à placer l'opérateur en sufixe

(postfix en anglais) : « a b + » C'est la notation sufixée, appelée aussi
notation polonaise inversée. Elle est utilisée dans certaines calculatrices
HP, ou dans certains langages informatiques (Forth, Postscript). Cette
notation n'est pas très commode pour l'écriture manuscrite, car il faut bien
séparer les deux opérandes. En revanche, elle a l'avantage de dispenser
complètement des parenthèses.

d) Evaluation des expressions postfixées

Soit l’expression infixée suivante : 3 * 5 + 2 * 4 – 6

L’expression postfixée devient : 3 5 * 2 4 * + 6 –

Une expression suffixée est très facile à évaluer pour un programme

informatique. On utilise pour cela une pile contenant les opérandes.

• L'expression est parcourue de la gauche vers la droite.

• Lorsqu’un opérande est rencontré, il est placé au sommet de la
pile.
• Lorsqu'un opérateur est rencontré,
o Les deux derniers opérandes sont enlevés de la pile,
o L’opération est appliquée sur les deux opérandes,
o Le résultat de l’opération est placé au sommet de la pile.
• A la fin le résultat est dans le sommet de la pile

Cours Algorithmique LMSD1 2024-2025 -73- Mr Khaled GHARDALLOU

 Voici un exemple d’exécution de l’expression précédente :

3 5 * 2 4 * + 6 -
4
5 2 2 8 6
3 3 15 15 15 15 23 23 17

Fonction EvaluatePostFixeExpression (exp : string, ) : string

Var :
Stack : Pile
temp: string /* pointeur sur le nouveau élément à empiler/*
Début
/* Creation de la pile/*
Pour (i de 0 à len(exp) – 1) faire /* Parcours de l’expression/*
Si operande (exp[i]) alors /* test si opérande 5 ou 6 …/*
Push(stack, exp[i]) /* ajouter à la pile/*
Sinon /*c’est un operateur */
Op2 = Peek(stack) /*recupérer operateur 2 */
POP(stack) /*sortir de la pile de l’opérateur 2 */
Op1 = Peek(stack) /*recupérer operateur 1 */
POP(Stack) /*sortir de la pile de l’opérateur 1 */
Temp = EvaluerOperation(Op1, Op2, exp[i])
Push(temp) /*Ajouter Résultat à la pile */
FinSi
FinPour
Retourner Peek(Stack)
Fin

e) Conversion infixée au postfixé

Pour évaluer une expression infixée, une méthode consiste à la
convertir tout d'abord en expression postfixé. L'algorithme de la gare de
triage (shunting yard) permet de faire cette conversion.

Cours Algorithmique LMSD1 2024-2025 -74- Mr Khaled GHARDALLOU

 • L’expression infixée (l'entrée) sont traités de la gauche vers la
droite.
• Les opérandes sont ajoutés à l’expression postfixé de sortie.
• Pour les opérateurs on doit faire ces tests :
o Si la pile est vide, il sera ajouté à la pile
o Si la priorité de l’opérateur est inférieure à celui de sommet
de la pile, celui-ci est enlevé de la pile et placé dans
l’expression de sortie. Et en refait les tests
• Lorsque tous les éléments sont traités, la pile est vidée dans la
liste de sortie
Exemple traitement d’Expression a * b + c

Expression Entrée Pile Expression Sortie

a * b + c a
* b + c * a
b + c * ab
+ c + ab*
c + ab*c
ab*c+

Voyons à présent comment sont traitées les parenthèses :

• Lorsqu'une parenthèse ouvrante est rencontrée, elle est ajoutée

à la pile d'opérateurs.
• Lorsqu'une parenthèse fermante est rencontrée, il faut vider la
pile vers la sortie jusqu'à la première parenthèse ouvrante,
laquelle doit bien sûr être enlevée de la pile

Cours Algorithmique LMSD1 2024-2025 -75- Mr Khaled GHARDALLOU

 Voici par exemple la séquence pour l'expression (a − b + c) ∗ d

Expression Entrée Pile Expression Sortie

( a - b + c) * d (
a - b + c) * d ( a
- b + c) * d (- a
b + c) * d (- ab
+ c) * d (+ ab-
c)*d (+ ab-c
)*d ab-c+
*d * ab-c+
d * ab-c+d
ab-c+d*

Voici finalement l'algorithme complet décrivant le traitement à

appliquer aux éléments de l'entrée :

• Si l’élément est un opérande, l'ajouter à la liste de sortie.

• Si l’élément est un opérateur
o Si la pile est vide, il sera ajouté à la pile
o Si la priorité de l’opérateur est inférieure à celui de sommet
de la pile, celui-ci est enlevé de la pile et placé dans
l’expression de sortie. Et en refait les tests
• Si l’élément est (, le placer dans la pile
• Si l’élément est )
o vider la pile vers la sortie jusqu'à rencontrer (.
o Enlever ( de la pile
• Lorsque l'entrée est vide, vider la pile dans la sortie.

Cours Algorithmique LMSD1 2024-2025 -76- Mr Khaled GHARDALLOU