Chapitre 12 : Les piles et les files
1. Présentation des Piles 1. Présentation des Piles
1.1. Définition:
Toutes les opérations sont effectuées sur la même
Une pile est une suite de cellules allouées dynamiquement (liste) où
l’insertion et la suppression d’un élément se font toujours en
extrémités: on parle de structure en LIFO (LAST IN
tête de liste, par exemple une pile d’assiettes. FIRST OUT: dernier arrivé, premier sorti)
in
Avec les Piles, on autorise seulement 4 opérations: out
Consulter le dernier élément de la pile
Tester si la pile est vide
Empiler un élément, le mettre au sommet de la pile (PUSH)
Dépiler un élément par le sommet (POP)
1 Figure 1: Structure d’une PILE 2
1. Présentation des Piles 2. Manipulation d’une Pile
1.2. Déclaration: Pour cela, on peut utiliser les procédures et les fonctions suivantes
L’utilisation de la pile s’impose lorsqu’on mémorise des ayant pour tâches:
informations qui devront être traitées dans l’ordre inverse de leur
arrivée. 2.1. Création d’une Pile vide:
Procédure initialiser(Var P:Pile)
Début
En supposant que les éléments de la pile sont des entiers, celles-ci se P←Nil
déclare de la façon suivante: Fin
Types Pile= pointeur sur element 2.2. Vérification si la pile P est vide:
element =Structure Fonction Pile_Vide(P:Pile): booléen
donnee: entier //valeur à stocker Début
suivant: Pile retourner (P=Nil) //renvoie vrai si P est NIL
FinStructure Fin
Variables P: Pile 3 4
, 2. Manipulation d’une Pile 2. Manipulation d’une Pile
2.4. Supprimer un élément de la Pile:
2.3. Ajouter un élément X au sommet de la Pile:
Procédure Dépiler(var X: entier, VAR P:Pile)
Variable
Procédure Empiler(X: entier, VAR P:Pile)
O: Pile
Variable
Début
O: Pile
si ( non Pile_Vide(P)) alors
Début
X ← P^.donnee
Allouer (O)
O←P
O^.donnee ←X
P←P^.suivant
O^.suivant←P
libérer (O)
P←O
sinon écrire (impossible de supprimer, Pile vide »)
Fin
finsi
5 Fin 6
3. Exemple: calcul arithmétique 3. Exemple: calcul arithmétique
Algorithme
Une application courante des Piles se fait dans le calcul arithmétique: l’ordre dans
1. Initialiser la Pile à vide
la Pile permet d’éviter l’usage des parenthèses. La notation Postfixe permet de
2. Tant que ce n’est pas la fin de l’expression postfixe
placer les opérandes devant l’opérateur. Exemple, (3+5)*2 s’écrira en Postfixe 3
prendre l’élément prochain de postfixe
5+2*
si l’élément est une valeur alors
Considérons l’expression en postfixe suivante: empiler
6 5 2 3 + 8 * + 3 + * = ((((((2+3)*8)+5)+) 3 * ) 6) sinon si l’élément est un opérateur binaire alors
=((((( 5*8)+5)+)3*)6) dépiler dans x
= (((( 40+5)+)3*)6) dépiler dans y
effectuer l’opération (y opérateur x)
= ((( 45+3)*)6)
empiler le résultat obtenu
= (( 48*)6) sinon si l’élément est un opérateur unaire
= ( 48*6) dépiler dans x
=288 effectuer l’opération opérateur(x)
On cherche à écrire l’algorithme formel permettant de calculer le empiler le résultat obtenu
finsi
résultat final. 7 8
finTQ
1. Présentation des Piles 1. Présentation des Piles
1.1. Définition:
Toutes les opérations sont effectuées sur la même
Une pile est une suite de cellules allouées dynamiquement (liste) où
l’insertion et la suppression d’un élément se font toujours en
extrémités: on parle de structure en LIFO (LAST IN
tête de liste, par exemple une pile d’assiettes. FIRST OUT: dernier arrivé, premier sorti)
in
Avec les Piles, on autorise seulement 4 opérations: out
Consulter le dernier élément de la pile
Tester si la pile est vide
Empiler un élément, le mettre au sommet de la pile (PUSH)
Dépiler un élément par le sommet (POP)
1 Figure 1: Structure d’une PILE 2
1. Présentation des Piles 2. Manipulation d’une Pile
1.2. Déclaration: Pour cela, on peut utiliser les procédures et les fonctions suivantes
L’utilisation de la pile s’impose lorsqu’on mémorise des ayant pour tâches:
informations qui devront être traitées dans l’ordre inverse de leur
arrivée. 2.1. Création d’une Pile vide:
Procédure initialiser(Var P:Pile)
Début
En supposant que les éléments de la pile sont des entiers, celles-ci se P←Nil
déclare de la façon suivante: Fin
Types Pile= pointeur sur element 2.2. Vérification si la pile P est vide:
element =Structure Fonction Pile_Vide(P:Pile): booléen
donnee: entier //valeur à stocker Début
suivant: Pile retourner (P=Nil) //renvoie vrai si P est NIL
FinStructure Fin
Variables P: Pile 3 4
, 2. Manipulation d’une Pile 2. Manipulation d’une Pile
2.4. Supprimer un élément de la Pile:
2.3. Ajouter un élément X au sommet de la Pile:
Procédure Dépiler(var X: entier, VAR P:Pile)
Variable
Procédure Empiler(X: entier, VAR P:Pile)
O: Pile
Variable
Début
O: Pile
si ( non Pile_Vide(P)) alors
Début
X ← P^.donnee
Allouer (O)
O←P
O^.donnee ←X
P←P^.suivant
O^.suivant←P
libérer (O)
P←O
sinon écrire (impossible de supprimer, Pile vide »)
Fin
finsi
5 Fin 6
3. Exemple: calcul arithmétique 3. Exemple: calcul arithmétique
Algorithme
Une application courante des Piles se fait dans le calcul arithmétique: l’ordre dans
1. Initialiser la Pile à vide
la Pile permet d’éviter l’usage des parenthèses. La notation Postfixe permet de
2. Tant que ce n’est pas la fin de l’expression postfixe
placer les opérandes devant l’opérateur. Exemple, (3+5)*2 s’écrira en Postfixe 3
prendre l’élément prochain de postfixe
5+2*
si l’élément est une valeur alors
Considérons l’expression en postfixe suivante: empiler
6 5 2 3 + 8 * + 3 + * = ((((((2+3)*8)+5)+) 3 * ) 6) sinon si l’élément est un opérateur binaire alors
=((((( 5*8)+5)+)3*)6) dépiler dans x
= (((( 40+5)+)3*)6) dépiler dans y
effectuer l’opération (y opérateur x)
= ((( 45+3)*)6)
empiler le résultat obtenu
= (( 48*)6) sinon si l’élément est un opérateur unaire
= ( 48*6) dépiler dans x
=288 effectuer l’opération opérateur(x)
On cherche à écrire l’algorithme formel permettant de calculer le empiler le résultat obtenu
finsi
résultat final. 7 8
finTQ
