Les types abstraits de données (TAD)

Les Piles & Les Files

Modélisation & Algorithmique
 La Pile (Stack) LIFO : last in, first out

Le profil de l’opération Spécification de l’opération

Opération Paramètres domaine co-domaine prés-conditions post-condition
Sommet : (P : Pile) : valeur Pile non vide - valeur du sommet de la Pile,
Pile → valeur Push (2) Pop ()
Empiler (2) Dépiler ()
(Top) Fonction
Empiler : (var P : Pile, x : valeur) Pile non pleine - Pile résultat : pile donnée +
Pile, valeur → Pile valeur comme sommet, Top
(Push) Procédure Sommet 2
Dépiler : (var P : Pile) : valeur Pile non vide - Pile résultat : pile donnée sans 4
Pile → Pile, valeur sommet,
(Pop) Fonction 1
Inaccessible
- Valeur du sommet, 7
Vide : (P : Pile) : booléen - Vrai si la pile et vide,
Pile → booléen ~~ 8
(Empty) Fonction - Faux si la pile et pleine,
 La File (Queue) FIFO: first in, first out

Le profil de l’opération Spécification de l’opération

Opération Paramètres domaine co-domaine prés-conditions post-condition
Avant : (F : File) : valeur File non vide - Valeur de l’avant de la file
File → valeur
(Front) Fonction
Arrière : (F : File) : valeur File non vide - Valeur de l’arrière de la file Dequeue ()
File → valeur Défiler ()
(Rear) Fonction Front
Enfiler : (var F : File, x : valeur) File non pleine - File résultat : File donnée + valeur Avant 2
File, valeur → File comme arrière de la file 4
(Enqueue) Procédure
Défiler : (var F : File) : valeur File non vide - File résultat : File donnée sans la 1
Inaccessible
File → File, valeur valeur avant de la File
(Dequeue) Fonction 7
- Valeur de l’avant de la File Rear
8 Arrière
Vide : (F : File) : booléen - Vrai si la file et vide,
File → booléen ~~ Enqueue (8)
Enfiler (8)
(Empty) Fonction - Faux si la file et pleine,
Exercice 1
Reconnaissance de chaîne
Exercice 1. (Reconnaissance de chaîne)
On se propose de reconnaître les chaînes de caractères définies par la règle suivante :
Une chaîne quelconque S suivie du caractère *, suivie de la chaîne S inversée. La chaîne
se termine par le marqueur fin de ligne. On suppose que S ne contient pas le caractère
'*'.
Exemple : ab2c*c2ba
Ecrire un algorithme qui vérifie si une chaîne est valide ou pas, en utilisant une pile.
Exercice 1. (Reconnaissance de chaîne)
Fonction Reconnaissance_chaîne (Ch : Chaîne) : Booléen
Var P : Pile; i, m : entier; valid : Booléen
Début
i := 1
Tant que [Link][i] <> * faire
Empiler (P, [Link](i))
i := i + 1
Fait
i := i + 1
valid := Vrai
Tant que i <= [Link] et Non(vide(P)) et valid faire
Si [Link](i) = Dépiler(P) alors
i := i + 1
Sinon
valid := Faux
Fsi
Fait
Reconnaissance_chaîne := (valid et vide(P) et i>
[Link] )
Fin
Exercice 2
Palindrome
Exercice 2. (Palindrome)
Un palindrome est un mot qui se lit de la même façon de gauche à droite et de droite
à gauche.
Exemple : RADAR, ELLE , 1991, ETE , ..
Ecrire un algorithme qui vérifie si un mot donné est un palindrome ou non, en
utilisant une pile.
Exercice 2. (Palindrome) Version 1 : empiler la chaîne entière

Fonction Palindrome (Ch : Chaîne) : Booléen

Var P : Pile; i, m : entier; valid : Booléen
Début
pour i de 1 à [Link] faire
Empiler (P, [Link](i))
FinPour
i := 1
valid := Vrai
Tant que i <= [Link] et valid faire
Si [Link](i) = Dépiler(P) alors
i := i + 1
Sinon
valid := Faux
Fsi
Fait
Palindrome := valid
Fin
Exercice 2. (Palindrome) Version 2 : empiler la moitié de la chaîne
Fonction Palindrome (Ch : Chaîne) : Booléen
Var P : Pile; i, m : entier; valid : Booléen
Début
m := [Link] div 2; i := 1
pour i de 1 à m faire
Empiler (P, [Link](i))
FinPour
i := i + 1
Si [Link] mod 2 <>0 alors
i  i + 1
Fsi
valid := Vrai
Tant que i <= [Link] et valid faire
Si [Link](i) = Dépiler(P) alors
i := i + 1
Sinon
valid := Faux
Fsi
Fait
Palindrome := valid
Exercice 3
Editeur de texte
Exercice 3. (Editeur de texte) e
s
a e
Un éditeur de texte doit mémoriser le texte sur lequel il travaille ainsi B t
que l'emplacement du curseur. L'ensemble texte-curseur est parfois
e S
représenté à l'aide de deux piles G et D : d t
- G contient les caractères situés en début de texte (avant le r
e u
curseur), le dernier étant en sommet de la pile, u c
- D contient les caractères de fin de texte, le premier en sommet q t
i u
de pile. m r
h e
On suppose de plus que l'on dispose d'un caractère de fin de ligne, soit t s
$ ce caractère. i
r d
Algorithmique de Bas│e et Structures de D o e
g
En utilisant les opérations du type abstrait pile (sommet, empiler, l D
A $
dépiler, est_vide), décrivez les opérations suivantes :
G D
Exercice 3. (Editeur de texte) e
s
a e
B t
1. Insérer un caractère C et positionner le curseur après le caractère
e S
inséré, d t
r
Empiler (G, C) e u
u c
2. Effacer le caractère qui suit le curseur, q t
i u
Dépiler (D) m r
h e
3. Avancer (vers la droite) le curseur d'un caractère, t s
i
Empiler (G, Dépiler (D)) r d
o e
g
4. Reculer (vers la gauche) le curseur d'un caractère,
l D
Empiler (D, Dépiler (G)) A $

G D
Exercice 3. (Editeur de texte) e
s
a e
B t
5. Rechercher la première occurrence d'un caractère donné C à partir e S
de la position courante, et positionner le curseur juste après cette d t
r
occurrence si elle existe, et en fin de texte sinon, e u
u c
Procédure Recherche (D, G : Pile, C : caractère) q t
Var i u
Début m r
Arret := faux h e
t s
Tant que Sommet(D) <> ‘$’ et NON Arret faire
i
x := Dépiler(D) r d
Empiler (G, x) o e
si x = C alors g
Arret  vrai l D
fsi A $
Fait
Fin G D
Exercice 3. (Editeur de texte) e
s
a e
B t
6. Aller au début de la ligne (curseur devant le premier caractère de la e S
ligne), d t
r
e u
u c
q t
Procédure Debut_Ligne (D, G : Pile) i u
Var m r
h e
Début t s
Tant que NON pile_vide (G) faire i
r d
Empiler (D, Dépiler(G))
o e
Fait g
Fin l D
A $

G D
Exercice 3. (Editeur de texte) e
s
a e
B t
7. de plus, lorsqu'on utilise un éditeur de texte, on dispose d'une e S
touche qui permet d'effacer le caractère que l'on vient de frapper d t
r
(par exemple "BackSpace"). Notons '#' ce caractère. e u
u c
Une autre touche permet de tout effacer jusqu'au début de la ligne. q t
Notons '%' ce caractère. i u
m r
La fin d'une ligne sera indiquée par le caractère '$'. h e
t s
Exemple : "Jem# m'euh%Je m'#euh## suit#s trop#mp&#é$" i
r d
sera lu comme : "Je me suis trompé" o e
g
Ecrire un algorithme qui permet de lire une ligne de texte avec ce l D
mécanisme et affiche la ligne réelle (sans les caractères A $
d’effacement).
Indication : On utilisera une pile pour traiter la chaîne au fur et à D G
mesure de sa lecture,
Exercice 3. (Editeur de texte)
PROGRAMME Edit
Var P : Pile; C : caractère
Début
Lire (C)
Tant que C <> ‘$’ faire Procédure supp_car(P : Pile)
Si C = ‘#’ alors Début
supp_car(P) si NON pile_vide(P) alors
Sinon
Dépiler (P)
Si C = ‘%’ alors
supp_ligne(P) fsi
Sinon Fin
Empiler (P, C)
Fsi
Fsi
Lire (C)
Fait Procédure supp_ligne(P : Pile)
Tant que NON pile_vide(P) faire Début
Empiler (R, Dépiler(P))
tant que NON pile_vide(P) faire
Fait
Tant que NON pile_vide(R) faire Dépiler (P)
Ecrire (Dépiler(R)) fait
Fait Fin
Fin
 Exercice 4
Evaluation d’une expression Arithmétique
Exercice 4. (Evaluation d’une expression Arithmétique)

Etant donnée une expression arithmétique représentée par une chaîne de caractères.
1) Ecrire une procédure qui permet le passage de la forme infixée à la forme postfixée.
Exemple : l'expression "3*7" → "3 7 *"
"3*7+2*(9-6)" → "3 7 * 2 9 6 - * +"

Indication : L’ordre des opérandes est le même dans les deux notations, donc on peut
les écrire directement. Tandis que pour les opérateurs et les parenthèses, il faudra les
stocker dans la pile jusqu’au moment opportun pour les dépiler et les afficher.
Exercice 4. (Evaluation d’une expression Arithmétique)

Exemple :

a+b-c ab+c-
A*b/c ab*c/

a+b*c abc*+
a+b*c-d abc*+d-
Exercice 4. (Evaluation d’une expression Arithmétique)

Exemple :
(a-b)/c*(d+e-f/g) *

/ -

- c + /

a b d e f g

a b - c / d e + f g / - *
Exercice 4. (Evaluation d’une expression Arithmétique)

Exemple :
(a-b)/c*(d+e-f/g)

+ - / *(opérateur) 
1) Tant qu’il y a un opérateur sur le sommet de la pile et qu’il soit
prioritaire :
 dépiler les opérateurs dans la Postfix
2)  Empiler l’opérateur o2 de la Infixée dans la pile,
Exercice 4. (Evaluation d’une expression Arithmétique)

Exemple :
(a-b)/c*(d+e-f/g)
a, b, c, d, … (opérande) 
1) Ajouter le caractère à la Postfix.
Exercice 4. (Evaluation d’une expression Arithmétique)

Exemple :
(a-b)/c*(d+e-f/g)

( [parenthèse ouvrante] 
1) Ajouter le caractère ( sur la pile.
Exercice 4. (Evaluation d’une expression Arithmétique)

Exemple :
(a-b)/c*(d+e-f/g)

) [parenthèse fermante] 
1) Tant qu’il y a un opérateur sur le sommet de la pile :
 dépiler l’opérateur dans la Postfix
2) Si le sommet de la pile est une parenthèse ouvrante :
 dépiler l’opérateur (non dans la Postfix)

, si toute la pile est dépilée sans trouver de parenthèse gauche

c’est qu’il y a un mauvais parenthésage.
Exercice 4. (Evaluation d’une expression Arithmétique)

Exemple :
(a-b)/c*(d+e-f/g)

pile des
opérateurs
+
Postfix chaîne de sortie post-fixé
parenthèses
ouvrantes

P
Exercice 4. (Evaluation d’une expression Arithmétique)

Exemple :
(a-b)/c*(d+e-f/g)

Ajouter la ( sur la pile

pile des
opérateurs
+
Postfix chaîne de sortie post-fixé
parenthèses
ouvrantes

P
Exercice 4. (Evaluation d’une expression Arithmétique)

Exemple :
(a-b)/c*(d+e-f/g)

Ajouter l’opérande à la chaîne Postfix

pile des
opérateurs
+
Postfix chaîne de sortie post-fixé
parenthèses
ouvrantes

(
P
Exercice 4. (Evaluation d’une expression Arithmétique)

Exemple :
(a-b)/c*(d+e-f/g)

• Dépiler les opérateurs prioritaire de la pile vers la chaîne Postfix,

jusqu’à plie vide ou (
• Empiler l’opérateur dans la pile, pile des
opérateurs
+
Postfix chaîne de sortie post-fixé
parenthèses
ouvrantes

a (
P
Exercice 4. (Evaluation d’une expression Arithmétique)

Exemple :
(a-b)/c*(d+e-f/g)

Ajouter l’opérande à la chaîne Postfix

pile des
opérateurs
+
Postfix chaîne de sortie post-fixé - parenthèses
ouvrantes

a (
P
Exercice 4. (Evaluation d’une expression Arithmétique)

Exemple :
(a-b)/c*(d+e-f/g)

• Dépiler les opérateurs de la pile vers la chaîne Postfix,

jusqu’à (
• Dépiler la ( non pas dans la chaîne Postfix pile des
opérateurs
+
Postfix chaîne de sortie post-fixé - parenthèses
ouvrantes

ab (
P
Exercice 4. (Evaluation d’une expression Arithmétique)

Exemple :
(a-b)/c*(d+e-f/g)

• Dépiler les opérateurs prioritaire de la pile vers la chaîne Postfix,

jusqu’à plie vide ou (
• Empiler l’opérateur dans la pile, pile des
opérateurs
+
Postfix chaîne de sortie post-fixé
parenthèses
ouvrantes

ab-
P
Exercice 4. (Evaluation d’une expression Arithmétique)

Exemple :
(a-b)/c*(d+e-f/g)

Ajouter l’opérande à la chaîne Postfix

pile des
opérateurs
+
Postfix chaîne de sortie post-fixé
parenthèses
ouvrantes

ab- /
P
Exercice 4. (Evaluation d’une expression Arithmétique)

Exemple :
(a-b)/c*(d+e-f/g)

• Dépiler les opérateurs prioritaire de la pile vers la chaîne Postfix,

jusqu’à plie vide ou (
• Empiler l’opérateur dans la pile, pile des
opérateurs
+
Postfix chaîne de sortie post-fixé
parenthèses
ouvrantes

ab-c /
P
Exercice 4. (Evaluation d’une expression Arithmétique)

Exemple :
(a-b)/c*(d+e-f/g)

Ajouter la ( sur la pile

pile des
opérateurs
+
Postfix chaîne de sortie post-fixé
parenthèses
ouvrantes

ab-c/ *
P
Exercice 4. (Evaluation d’une expression Arithmétique)

Exemple :
(a-b)/c*(d+e-f/g)

Ajouter l’opérande à la chaîne Postfix

pile des
opérateurs
+
Postfix chaîne de sortie post-fixé ( parenthèses
ouvrantes

ab-c/ *
P
Exercice 4. (Evaluation d’une expression Arithmétique)

Exemple :
(a-b)/c*(d+e-f/g)

• Dépiler les opérateurs prioritaire de la pile vers la chaîne Postfix,

jusqu’à plie vide ou (
• Empiler l’opérateur dans la pile, pile des
opérateurs
+
Postfix chaîne de sortie post-fixé ( parenthèses
ouvrantes

ab-c/d *
P
Exercice 4. (Evaluation d’une expression Arithmétique)

Exemple :
(a-b)/c*(d+e-f/g)

Ajouter l’opérande à la chaîne Postfix

pile des
+ opérateurs
+
Postfix chaîne de sortie post-fixé ( parenthèses
ouvrantes

ab-c/d *
P
Exercice 4. (Evaluation d’une expression Arithmétique)

Exemple :
(a-b)/c*(d+e-f/g)

• Dépiler les opérateurs prioritaire de la pile vers la chaîne Postfix,

jusqu’à plie vide ou (
• Empiler l’opérateur dans la pile, pile des
+ opérateurs
+
Postfix chaîne de sortie post-fixé ( parenthèses
ouvrantes

ab-c/de *
P
Exercice 4. (Evaluation d’une expression Arithmétique)

Exemple :
(a-b)/c*(d+e-f/g)

Ajouter l’opérande à la chaîne Postfix

pile des
- opérateurs
+
Postfix chaîne de sortie post-fixé ( parenthèses
ouvrantes

ab-c/de+ *
P
Exercice 4. (Evaluation d’une expression Arithmétique)

Exemple :
(a-b)/c*(d+e-f/g)

• Dépiler les opérateurs prioritaire de la pile vers la chaîne Postfix,

jusqu’à plie vide ou (
• Empiler l’opérateur dans la pile, pile des
- opérateurs
+
Postfix chaîne de sortie post-fixé ( parenthèses
ouvrantes

ab-c/de+f *
P
Exercice 4. (Evaluation d’une expression Arithmétique)

Exemple :
(a-b)/c*(d+e-f/g)

Ajouter l’opérande à la chaîne Postfix

/
pile des
- opérateurs
+
Postfix chaîne de sortie post-fixé ( parenthèses
ouvrantes

ab-c/de+f *
P
Exercice 4. (Evaluation d’une expression Arithmétique)

Exemple :
(a-b)/c*(d+e-f/g)

• Dépiler les opérateurs de la pile vers la chaîne Postfix,

jusqu’à ( /
• Dépiler la ( non pas dans la chaîne Postfix pile des
- opérateurs
+
Postfix chaîne de sortie post-fixé ( parenthèses
ouvrantes

ab-c/de+fg *
P
Exercice 4. (Evaluation d’une expression Arithmétique)

Exemple :
(a-b)/c*(d+e-f/g)

• Dépiler les opérateurs restant de la pile vers la chaîne Postfix,

jusqu’à pile vide !!!
pile des
opérateurs
+
Postfix chaîne de sortie post-fixé
parenthèses
ouvrantes

ab-c/de+fg/- *
P
Exercice 4. (Evaluation d’une expression Arithmétique)

Exemple :
(a-b)/c*(d+e-f/g)

• Fin de traitement de la chaîne infixée !!!

pile des
opérateurs
+
Postfix chaîne de sortie post-fixé
parenthèses
ouvrantes

ab-c/de+fg/-*
P
Infix_Postfix (Infix : Chaîne) : Chaîne
Vartmp : caractère # tompon pour le dépilement de la pile
Postfix : chaîne # chaîne de sortie post-fixé
pl : pile # pile des opérateurs + parenthèses ouvrantes
i : entier # compteur : parcoure de la chaîne in-fixée
Début
pour i de 1 à [Link] faire
si Opérateur([Link][i]) alors
Tant que (non vide(pl) et top(pl) <> ‘(‘ et Prioritaire(top(pl), [Link][i])) faire
Ajouter_ch(Postfix, Dépiler(pl))
FinTanque
Empiler(pl, [Link][i])
Sinon si Opérande([Link][i]) alors
Ajouter_ch(Postfix, [Link][i])
Sinon si [Link][i] = ‘(‘ alors
Empiler(pl, [Link][i])
Sinon si [Link][i] = ‘)‘ alors
Tant que (non vide(pl)) et (top(pl) <> ‘(‘) faire
Ajouter_ch(Postfix, Dépiler(pl))
FinTanque
Si top(pl) = ‘(‘ alors
tmp := Dépiler(pl)
sinon
Message erreur "mauvais parenthèsage"
FinSi
FinSi
FinPour
Tant que (non vide(pl)) faire
Infix_Postfix (Infix : Chaîne) : Chaîne
Vartmp : caractère # tompon pour le dépilement de la pile
Postfix : chaîne # chaîne de sortie post-fixé
pl : pile # pile des opérateurs + parenthèses ouvrantes
i : entier # compteur : parcoure de la chaîne in-fixée
Début
pour i de 1 à [Link] faire
si Opérateur([Link][i]) alors
Tant que (non vide(pl) et top(pl) <> ‘(‘ et Prioritaire(top(pl), [Link][i])) faire
Ajouter_ch(Postfix, Dépiler(pl))
FinTanque
Empiler(pl, [Link][i])
Sinon si Opérande([Link][i]) alors
Ajouter_ch(Postfix, [Link][i])
Sinon si [Link][i] = ‘(‘ alors
Empiler(pl, [Link][i])
Sinon si [Link][i] = ‘)‘ alors
Tant que (non vide(pl)) et (top(pl) <> ‘(‘) faire
Ajouter_ch(Postfix, Dépiler(pl))
FinTanque
Si top(pl) = ‘(‘ alors
tmp := Dépiler(pl)
sinon
Message erreur "mauvais parenthèsage"
FinSi
FinSi
FinPour
Tant que (non vide(pl)) faire
Infix_Postfix (Infix : Chaîne) : Chaîne
Vartmp : caractère # tompon pour le dépilement de la pile
Postfix : chaîne # chaîne de sortie post-fixé
pl : pile # pile des opérateurs + parenthèses ouvrantes
i : entier # compteur : parcoure de la chaîne in-fixée
Début
pour i de 1 à [Link] faire
si Opérateur([Link][i]) alors
Tant que (non vide(pl) et top(pl) <> ‘(‘ et Prioritaire(top(pl), [Link][i])) faire
Ajouter_ch(Postfix, Dépiler(pl))
FinTanque
Empiler(pl, [Link][i])
Sinon si Opérande([Link][i]) alors
Ajouter_ch(Postfix, [Link][i])
Sinon si [Link][i] = ‘(‘ alors
Empiler(pl, [Link][i])
Sinon si [Link][i] = ‘)‘ alors
Tant que (non vide(pl)) et (top(pl) <> ‘(‘) faire
Ajouter_ch(Postfix, Dépiler(pl))
FinTanque
Si top(pl) = ‘(‘ alors
tmp := Dépiler(pl)
sinon
Message erreur "mauvais parenthèsage"
FinSi
FinSi
FinPour
Tant que (non vide(pl)) faire
Infix_Postfix (Infix : Chaîne) : Chaîne
Vartmp : caractère # tompon pour le dépilement de la pile
Postfix : chaîne # chaîne de sortie post-fixé
pl : pile # pile des opérateurs + parenthèses ouvrantes
i : entier # compteur : parcoure de la chaîne in-fixée
Début
pour i de 1 à [Link] faire
si Opérateur([Link][i]) alors
Tant que (non vide(pl) et top(pl) <> ‘(‘ et Prioritaire(top(pl), [Link][i])) faire
Ajouter_ch(Postfix, Dépiler(pl))
FinTanque
Empiler(pl, [Link][i])
Sinon si Opérande([Link][i]) alors
Ajouter_ch(Postfix, [Link][i])
Sinon si [Link][i] = ‘(‘ alors
Empiler(pl, [Link][i])
Sinon si [Link][i] = ‘)‘ alors
Tant que (non vide(pl)) et (top(pl) <> ‘(‘) faire
Ajouter_ch(Postfix, Dépiler(pl))
FinTanque
Si top(pl) = ‘(‘ alors
tmp := Dépiler(pl)
sinon
Message erreur "mauvais parenthèsage"
FinSi
FinSi
FinPour
Tant que (non vide(pl)) faire
Infix_Postfix (Infix : Chaîne) : Chaîne
Vartmp : caractère # tompon pour le dépilement de la pile
Postfix : chaîne # chaîne de sortie post-fixé
pl : pile # pile des opérateurs + parenthèses ouvrantes
i : entier # compteur : parcoure de la chaîne in-fixée
Début
pour i de 1 à [Link] faire
si Opérateur([Link][i]) alors
Tant que (non vide(pl) et top(pl) <> ‘(‘ et Prioritaire(top(pl), [Link][i])) faire
Ajouter_ch(Postfix, Dépiler(pl))
FinTanque
Empiler(pl, [Link][i])
Sinon si Opérande([Link][i]) alors
Ajouter_ch(Postfix, [Link][i])
Sinon si [Link][i] = ‘(‘ alors
Empiler(pl, [Link][i])
Sinon si [Link][i] = ‘)‘ alors
Tant que (non vide(pl)) et (top(pl) <> ‘(‘) faire
Ajouter_ch(Postfix, Dépiler(pl))
FinTanque
Si top(pl) = ‘(‘ alors
tmp := Dépiler(pl)
sinon
Message erreur "mauvais parenthèsage"
FinSi
FinSi
FinPour
Tant que (non vide(pl)) faire
Infix_Postfix (Infix : Chaîne) : Chaîne
Vartmp : caractère # tompon pour le dépilement de la pile
Postfix : chaîne # chaîne de sortie post-fixé
pl : pile # pile des opérateurs + parenthèses ouvrantes
i : entier # compteur : parcoure de la chaîne in-fixée
Début
pour i de 1 à [Link] faire
si Opérateur([Link][i]) alors
Tant que (non vide(pl) et top(pl) <> ‘(‘ et Prioritaire(top(pl), [Link][i])) faire
Ajouter_ch(Postfix, Dépiler(pl))
FinTanque
Empiler(pl, [Link][i])
Sinon si Opérande([Link][i]) alors
Ajouter_ch(Postfix, [Link][i])
Sinon si [Link][i] = ‘(‘ alors
Empiler(pl, [Link][i])
Sinon si [Link][i] = ‘)‘ alors
Tant que (non vide(pl)) et (top(pl) <> ‘(‘) faire
Ajouter_ch(Postfix, Dépiler(pl))
FinTanque
Si top(pl) = ‘(‘ alors
tmp := Dépiler(pl)
sinon
Message erreur "mauvais parenthèsage"
FinSi
FinSi
FinPour
Tant que (non vide(pl)) faire
Infix_Postfix (Infix : Chaîne) : Chaîne
Vartmp : caractère # tompon pour le dépilement de la pile
Postfix : chaîne # chaîne de sortie post-fixé
pl : pile # pile des opérateurs + parenthèses ouvrantes
i : entier # compteur : parcoure de la chaîne in-fixée
Début
pour i de 1 à [Link] faire
si Opérateur([Link][i]) alors
Tant que (non vide(pl) et top(pl) <> ‘(‘ et Prioritaire(top(pl), [Link][i])) faire
Ajouter_ch(Postfix, Dépiler(pl))
FinTanque
Empiler(pl, [Link][i])
Sinon si Opérande([Link][i]) alors
Ajouter_ch(Postfix, [Link][i])
Sinon si [Link][i] = ‘(‘ alors
Empiler(pl, [Link][i])
Sinon si [Link][i] = ‘)‘ alors
Tant que (non vide(pl)) et (top(pl) <> ‘(‘) faire
Ajouter_ch(Postfix, Dépiler(pl))
FinTanque
Si top(pl) = ‘(‘ alors
tmp := Dépiler(pl)
sinon
Message erreur "mauvais parenthèsage"
FinSi
FinSi
FinPour
Tant que (non vide(pl)) faire
Infix_Postfix (Infix : Chaîne) : Chaîne
Vartmp : caractère # tompon pour le dépilement de la pile
Postfix : chaîne # chaîne de sortie post-fixé
pl : pile # pile des opérateurs + parenthèses ouvrantes
i : entier # compteur : parcoure de la chaîne in-fixée
Début
pour i de 1 à [Link] faire
si Opérateur([Link][i]) alors
Tant que (non vide(pl) et top(pl) <> ‘(‘ et Prioritaire(top(pl), [Link][i])) faire
Ajouter_ch(Postfix, Dépiler(pl))
FinTanque
Empiler(pl, [Link][i])
Sinon si Opérande([Link][i]) alors
Ajouter_ch(Postfix, [Link][i])
Sinon si [Link][i] = ‘(‘ alors
Empiler(pl, [Link][i])
Sinon si [Link][i] = ‘)‘ alors
Tant que (non vide(pl)) et (top(pl) <> ‘(‘) faire
Ajouter_ch(Postfix, Dépiler(pl))
FinTanque
Si top(pl) = ‘(‘ alors
tmp := Dépiler(pl)
sinon
Message erreur "mauvais parenthèsage"
FinSi
FinSi
FinPour
Tant que (non vide(pl)) faire
Si top(pl) = ‘(‘ alors
Message erreur "mauvais parenthèsage"
Sinon
Ajouter_ch(Postfix, Dépiler(pl))
FinSi
FinTantque
Infix_Postfix := Postfix
FIN
Infix_Postfix (Infix : Chaîne) : Chaîne
Vartmp : caractère # tompon pour le dépilement de la pile
Postfix : chaîne # chaîne de sortie post-fixé
pl : pile # pile des opérateurs + parenthèses ouvrantes
i : entier # compteur : parcoure de la chaîne in-fixée
Début
pour i de 1 à [Link] faire
si Opérateur([Link][i]) alors
Tant que (non vide(pl) et top(pl) <> ‘(‘ et Prioritaire(top(pl), [Link][i])) faire
Ajouter_ch(Postfix, Dépiler(pl))
FinTanque
Empiler(pl, [Link][i])
Sinon si Opérande([Link][i]) alors
Ajouter_ch(Postfix, [Link][i])
Sinon si [Link][i] = ‘(‘ alors
Empiler(pl, [Link][i])
Sinon si [Link][i] = ‘)‘ alors
Tant que (non vide(pl)) et (top(pl) <> ‘(‘) faire
Ajouter_ch(Postfix, Dépiler(pl))
FinTanque
Si top(pl) = ‘(‘ alors
tmp := Dépiler(pl)
sinon
Message erreur "mauvais parenthèsage"
FinSi
FinSi
FinPour
Tant que (non vide(pl)) faire
Si top(pl) = ‘(‘ alors
Message erreur "mauvais parenthèsage"
Sinon
Ajouter_ch(Postfix, Dépiler(pl))
FinSi
FinTantque
Infix_Postfix := Postfix
FIN
Infix_Postfix (Infix : Chaîne) : Chaîne
Vartmp : caractère # tompon pour le dépilement de la pile
Postfix : chaîne # chaîne de sortie post-fixé
pl : pile # pile des opérateurs + parenthèses ouvrantes
i : entier # compteur : parcoure de la chaîne in-fixée
Début
pour i de 1 à [Link] faire
si Opérateur([Link][i]) alors
Tant que (non vide(pl) et top(pl) <> ‘(‘ et Prioritaire(top(pl), [Link][i])) faire
Ajouter_ch(Postfix, Dépiler(pl))
FinTanque
Empiler(pl, [Link][i])
Sinon si Opérande([Link][i]) alors
Ajouter_ch(Postfix, [Link][i])
Sinon si [Link][i] = ‘(‘ alors
Empiler(pl, [Link][i])
Sinon si [Link][i] = ‘)‘ alors
Tant que (non vide(pl)) et (top(pl) <> ‘(‘) faire
Ajouter_ch(Postfix, Dépiler(pl))
FinTanque
Si top(pl) = ‘(‘ alors
tmp := Dépiler(pl)
sinon
Message erreur "mauvais parenthèsage"
FinSi
FinSi
FinPour
Tant que (non vide(pl)) faire
Si top(pl) = ‘(‘ alors
Message erreur "mauvais parenthèsage"
Sinon
Ajouter_ch(Postfix, Dépiler(pl))
FinSi
FinTantque
Infix_Postfix := Postfix
FIN
Infix_Postfix (Infix : Chaîne) : Chaîne
Var tmp : caractère # tompon pour le dépilement de la pile
Postfix : chaîne # chaîne de sortie post-fixé
pl : pile # pile des opérateurs + parenthèses ouvrantes
i : entier # compteur : parcoure de la chaîne in-fixée
Début
pour i de 1 à [Link] faire
si Opérateur([Link][i]) alors
Tant que (non vide(pl) et top(pl) <> ‘(‘ et Prioritaire(top(pl), [Link][i])) faire
Ajouter_ch(Postfix, Dépiler(pl))
FinTanque
Empiler(pl, [Link][i])
Sinon si Opérande([Link][i]) alors
Ajouter_ch(Postfix, [Link][i])
Sinon si [Link][i] = ‘(‘ alors
Empiler(pl, [Link][i])
Sinon si [Link][i] = ‘)‘ alors
Tant que (non vide(pl)) et (top(pl) <> ‘(‘) faire
Ajouter_ch(Postfix, Dépiler(pl))
FinTanque
(a-b)/c*(d+e-f/g)
Si top(pl) = ‘(‘ alors
tmp := Dépiler(pl)
sinon
Message erreur "mauvais parenthèsage" ab-c/de+fg/-*
FinSi
FinSi
FinPour
Tant que (non vide(pl)) faire
Si top(pl) = ‘(‘ alors
Message erreur "mauvais parenthèsage"
Sinon
Ajouter_ch(Postfix, Dépiler(pl))
FinSi
FinTantque
Infix_Postfix := Postfix
FIN
Exercice 4. (Evaluation d’une expression Arithmétique)

Etant donnée une expression arithmétique représentée par une chaîne de caractères.
1) Ecrire une procédure qui permet le passage de la forme infixée à la forme postfixée.
Exemple : l'expression "3*7" → "3 7 *"
"3*7+2*(9-6)" → "3 7 * 2 9 6 - * +"
2) Ecrire une procédure qui permet d’évaluer une expression postfixée
Exercice 4. (Evaluation d’une expression Arithmétique)

Exemple :
ab-c/de+fg/-*

a, b, c, d, … (opérande) 
1) ajout de l’expression a la pile des opérandes,
Exercice 4. (Evaluation d’une expression Arithmétique)

Exemple :
ab-c/de+fg/-*

+ - / * (opérateur) 
1) récupération des deux opérandes (x, y) sur la pile,
2) calcul de l’expression avec l’opérateur sur la chaîne post-fixée,
3) ajout du résultat a la pile des opérandes,
Exercice 4. (Evaluation d’une expression Arithmétique)

Exemple :
ab-c/de+fg/-*

• ajout de l’expression a la pile des opérandes

opérande opérande expression pile des

opérandes

O1 O2 Calcul
P
Exercice 4. (Evaluation d’une expression Arithmétique)

Exemple :
ab-c/de+fg/-*

• ajout de l’expression a la pile des opérandes

opérande opérande expression pile des

opérandes

O1 O2 Calcul
P
Exercice 4. (Evaluation d’une expression Arithmétique)

Exemple :
ab-c/de+fg/-*

• ajout de l’expression a la pile des opérandes

opérande opérande expression pile des

a opérandes

O1 O2 Calcul
P
Exercice 4. (Evaluation d’une expression Arithmétique)

Exemple :
ab-c/de+fg/-*

• récupération des deux opérandes (x, y) sur la pile,

• calcul de l’expression avec l’opérateur sur la chaîne post-fixée,
• ajout du résultat a la pile des opérandes,

a b a – b = r1
opérande opérande expression
b pile des
a opérandes

O1 O2 Calcul
P
Exercice 4. (Evaluation d’une expression Arithmétique)

Exemple :
ab-c/de+fg/-*

• ajout de l’expression a la pile des opérandes

opérande opérande expression pile des

r1 opérandes

O1 O2 Calcul
P
Exercice 4. (Evaluation d’une expression Arithmétique)

Exemple :
ab-c/de+fg/-*

• récupération des deux opérandes (x, y) sur la pile,

• calcul de l’expression avec l’opérateur sur la chaîne post-fixée,
• ajout du résultat a la pile des opérandes,

r1 c r1 / c = r2
opérande opérande expression
c pile des
r1 opérandes

O1 O2 Calcul
P
Exercice 4. (Evaluation d’une expression Arithmétique)

Exemple :
ab-c/de+fg/-*

• ajout de l’expression a la pile des opérandes

opérande opérande expression pile des

r2 opérandes

O1 O2 Calcul
P
Exercice 4. (Evaluation d’une expression Arithmétique)

Exemple :
ab-c/de+fg/-*

• ajout de l’expression a la pile des opérandes

opérande opérande expression

d pile des
r2 opérandes

O1 O2 Calcul
P
Exercice 4. (Evaluation d’une expression Arithmétique)

Exemple :
ab-c/de+fg/-*

• récupération des deux opérandes (x, y) sur la pile,

• calcul de l’expression avec l’opérateur sur la chaîne post-fixée,
• ajout du résultat a la pile des opérandes,

e
d e d + e = r3
opérande opérande expression
d pile des
r2 opérandes

O1 O2 Calcul
P
Exercice 4. (Evaluation d’une expression Arithmétique)

Exemple :
ab-c/de+fg/-*

• ajout de l’expression a la pile des opérandes

opérande opérande expression

r3 pile des
r2 opérandes

O1 O2 Calcul
P
Exercice 4. (Evaluation d’une expression Arithmétique)

Exemple :
ab-c/de+fg/-*

• ajout de l’expression a la pile des opérandes

f
opérande opérande expression
r3 pile des
r2 opérandes

O1 O2 Calcul
P
Exercice 4. (Evaluation d’une expression Arithmétique)

Exemple :
ab-c/de+fg/-*

• récupération des deux opérandes (x, y) sur la pile,

• calcul de l’expression avec l’opérateur sur la chaîne post-fixée,
• ajout du résultat a la pile des opérandes,
g
f
f g f / g = r4
opérande opérande expression
r3 pile des
r2 opérandes

O1 O2 Calcul
P
Exercice 4. (Evaluation d’une expression Arithmétique)

Exemple :
ab-c/de+fg/-*

• récupération des deux opérandes (x, y) sur la pile,

• calcul de l’expression avec l’opérateur sur la chaîne post-fixée,
• ajout du résultat a la pile des opérandes,

r4
r3 r4 r3 - r4 = r5
opérande opérande expression
r3 pile des
r2 opérandes

O1 O2 Calcul
P
Exercice 4. (Evaluation d’une expression Arithmétique)

Exemple :
ab-c/de+fg/-*

• récupération des deux opérandes (x, y) sur la pile,

• calcul de l’expression avec l’opérateur sur la chaîne post-fixée,
• ajout du résultat a la pile des opérandes,

r2 r5 r2 * r5 = r6
opérande opérande expression
r5 pile des
r2 opérandes

O1 O2 Calcul
P
Exercice 4. (Evaluation d’une expression Arithmétique)

Exemple :
ab-c/de+fg/-*

• récupération du résultat final de la pile des opérandes,

opérande opérande expression pile des

r6 opérandes

O1 O2 Calcul
P
Fonction Evaluer_Postfix (postfix : Chaîne) : Réel
Var pl : pile # pile d’opérande
i : entier # compteur : parcoure de la chaîne post-fixée
x, y, z : Réel # tmp. de calcul
Début
pour i de 1 à [Link] faire
si Opérateur([Link][i]) alors
x := Dépiler(pl)
y := Dépiler(pl)
z := Calcul([Link][i], x, y)
Empiler(pl, z)
Sinon si Opérande([Link][i]) alors
Empiler(pl, [Link][i])
FinSi
FinPour
Evaluer_Infix_Postfix := Dépiler(pl)
FIN
Fonction Evaluer_Postfix (postfix : Chaîne) : Réel
Var pl : pile # pile d’opérande
i : entier # compteur : parcoure de la chaîne post-fixée
x, y, z : Réel # tmp. de calcul
Début
pour i de 1 à [Link] faire
si Opérateur([Link][i]) alors
x := Dépiler(pl)
y := Dépiler(pl)
z := Calcul([Link][i], x, y)
Empiler(pl, z)
Sinon si Opérande([Link][i]) alors
Empiler(pl, [Link][i])
FinSi
FinPour
Evaluer_Infix_Postfix := Dépiler(pl)
FIN
Fonction Evaluer_Postfix (postfix : Chaîne) : Réel
Var pl : pile # pile d’opérande
i : entier # compteur : parcoure de la chaîne post-fixée
x, y, z : Réel # tmp. de calcul
Début
pour i de 1 à [Link] faire
si Opérateur([Link][i]) alors
x := Dépiler(pl)
y := Dépiler(pl)
z := Calcul([Link][i], x, y)
Empiler(pl, z)
Sinon si Opérande([Link][i]) alors
Empiler(pl, [Link][i])
FinSi
FinPour
Evaluer_Infix_Postfix := Dépiler(pl)
FIN
Fonction Evaluer_Postfix (postfix : Chaîne) : Réel
Var pl : pile # pile d’opérande
i : entier # compteur : parcoure de la chaîne post-fixée
x, y, z : Réel # tmp. de calcul
Début
pour i de 1 à [Link] faire
si Opérateur([Link][i]) alors
x := Dépiler(pl)
y := Dépiler(pl)
z := Calcul([Link][i], x, y)
Empiler(pl, z)
Sinon si Opérande([Link][i]) alors
Empiler(pl, [Link][i])
FinSi
FinPour
Evaluer_Infix_Postfix := Dépiler(pl)
FIN
Fonction Evaluer_Postfix (postfix : Chaîne) : Réel
Var pl : pile # pile d’opérande
i : entier # compteur : parcoure de la chaîne post-fixée
x, y, z : Réel # tmp. de calcul
Début
pour i de 1 à [Link] faire
si Opérateur([Link][i]) alors
x := Dépiler(pl)
y := Dépiler(pl)
z := Calcul([Link][i], x, y)
Empiler(pl, z)
Sinon si Opérande([Link][i]) alors
Empiler(pl, [Link][i])
FinSi
FinPour
Evaluer_Infix_Postfix := Dépiler(pl)
FIN
Exercice 5
Application File : Tri FIFO
Exercice 5. (Application File : Tri FIFO)

On veut trier une suite de nombres entiers de la façon suivante :

1. Au départ, chaque nombre est mis dans une liste ne contenant que lui.
Toutes ces listes sont mises dans une file (FIFO).
2. On fait sortir deux listes de la file, on les fusionne en une liste croissante.
3. On fait rentrer la liste résultat dans la file.
• On répète (2) et (3) jusqu’à ce que la file ne contienne plus qu’une seule
liste, ça sera alors la suite ordonnée.

Exemple : Soit à trier la suite 4, 1, 8, 2, 3, 7, 9, 5, 6

Exercice 5. (Application File : Tri FIFO)

Exemple : Soit à trier la suite 4, 1, 8, 2, 3, 7, 9, 5, 6

Etape 1 :
4 1 8 2 3 7 9 5 6

Au départ, chaque nombre

est mis dans une liste ne
contenant que lui,
Toutes ces listes sont mises
dans une file (FIFO),
Exercice 5. (Application File : Tri FIFO)

Exemple : Soit à trier la suite 4, 1, 8, 2, 3, 7, 9, 5, 6

Etape 1 :
4 1 8 2 3 7 9 5 6

Au départ, chaque nombre

est mis dans une liste ne
contenant que lui,
Toutes ces listes sont mises
dans une file (FIFO),
Exercice 5. (Application File : Tri FIFO)

Exemple : Soit à trier la suite 4, 1, 8, 2, 3, 7, 9, 5, 6

Etape 2 :
4 1 8 2 3 7 9 5 6

On fait sortir les deux 1er

listes de la file, on les
fusionne en une liste
croissante
Exercice 5. (Application File : Tri FIFO)

Exemple : Soit à trier la suite 4, 1, 8, 2, 3, 7, 9, 5, 6

Etape 2 :
8 2 3 7 9 5 6

On fait sortir les deux 1er 1 4

listes de la file, on les
fusionne en une liste
croissante
Exercice 5. (Application File : Tri FIFO)

Exemple : Soit à trier la suite 4, 1, 8, 2, 3, 7, 9, 5, 6

Etape 3 :
8 2 3 7 9 5 6 1

insérer la liste 4
fusionnée dans la file
Exercice 5. (Application File : Tri FIFO)

Exemple : Soit à trier la suite 4, 1, 8, 2, 3, 7, 9, 5, 6

Etape 2 :
8 2 3 7 9 5 6 1

On fait sortir les deux 1er 4

listes de la file, on les
fusionne en une liste
croissante
Exercice 5. (Application File : Tri FIFO)

Exemple : Soit à trier la suite 4, 1, 8, 2, 3, 7, 9, 5, 6

Etape 2 :
3 7 9 5 6 1

On fait sortir les deux 1er 4 2 8

listes de la file, on les
fusionne en une liste
croissante
Exercice 5. (Application File : Tri FIFO)

Exemple : Soit à trier la suite 4, 1, 8, 2, 3, 7, 9, 5, 6

Etape 3 :
3 7 9 5 6 1 2

insérer la liste 4 8
fusionnée dans la file
Exercice 5. (Application File : Tri FIFO)

Exemple : Soit à trier la suite 4, 1, 8, 2, 3, 7, 9, 5, 6

Etape 2 :
3 7 9 5 6 1 2

On fait sortir les deux 1er 4 8

listes de la file, on les
fusionne en une liste
croissante
Exercice 5. (Application File : Tri FIFO)

Exemple : Soit à trier la suite 4, 1, 8, 2, 3, 7, 9, 5, 6

Etape 2 :
9 5 6 1 2

On fait sortir les deux 1er 4 8 3 7

listes de la file, on les
fusionne en une liste
croissante
Exercice 5. (Application File : Tri FIFO)

Exemple : Soit à trier la suite 4, 1, 8, 2, 3, 7, 9, 5, 6

Etape 3 :
9 5 6 1 2 3

insérer la liste 4 8 7
fusionnée dans la file
Exercice 5. (Application File : Tri FIFO)

Exemple : Soit à trier la suite 4, 1, 8, 2, 3, 7, 9, 5, 6

Etape 2 :
9 5 6 1 2 3

On fait sortir les deux 1er 4 8 7

listes de la file, on les
fusionne en une liste
croissante
Exercice 5. (Application File : Tri FIFO)

Exemple : Soit à trier la suite 4, 1, 8, 2, 3, 7, 9, 5, 6

Etape 2 :
6 1 2 3

On fait sortir les deux 1er 4 8 7 5 9

listes de la file, on les
fusionne en une liste
croissante
Exercice 5. (Application File : Tri FIFO)

Exemple : Soit à trier la suite 4, 1, 8, 2, 3, 7, 9, 5, 6

Etape 3 :
6 1 2 3 5

insérer la liste 4 8 7 9
fusionnée dans la file
Exercice 5. (Application File : Tri FIFO)

Exemple : Soit à trier la suite 4, 1, 8, 2, 3, 7, 9, 5, 6

Etape 2 :
6 1 2 3 5

On fait sortir les deux 1er 4 8 7 9

listes de la file, on les
fusionne en une liste
croissante
Exercice 5. (Application File : Tri FIFO)

Exemple : Soit à trier la suite 4, 1, 8, 2, 3, 7, 9, 5, 6

Etape 2 :
2 3 5

On fait sortir les deux 1er 8 7 9 1 4 6

listes de la file, on les
fusionne en une liste
croissante
Exercice 5. (Application File : Tri FIFO)

Exemple : Soit à trier la suite 4, 1, 8, 2, 3, 7, 9, 5, 6

Etape 3 :
2 3 5 1

insérer la liste 8 7 9 4
fusionnée dans la file 6
Exercice 5. (Application File : Tri FIFO)

Exemple : Soit à trier la suite 4, 1, 8, 2, 3, 7, 9, 5, 6

Etape 2 :
2 3 5 1

On fait sortir les deux 1er 8 7 9 4

listes de la file, on les 6
fusionne en une liste
croissante
Exercice 5. (Application File : Tri FIFO)

Exemple : Soit à trier la suite 4, 1, 8, 2, 3, 7, 9, 5, 6

Etape 2 :
5 1

On fait sortir les deux 1er 9 4 2 3 7 8

listes de la file, on les 6
fusionne en une liste
croissante
Exercice 5. (Application File : Tri FIFO)

Exemple : Soit à trier la suite 4, 1, 8, 2, 3, 7, 9, 5, 6

Etape 3 :
5 1 2

insérer la liste 9 4 3
fusionnée dans la file 6 7

8
Exercice 5. (Application File : Tri FIFO)

Exemple : Soit à trier la suite 4, 1, 8, 2, 3, 7, 9, 5, 6

Etape 2 :
5 1 2

On fait sortir les deux 1er 9 4 3

listes de la file, on les 6 7
fusionne en une liste
croissante 8
Exercice 5. (Application File : Tri FIFO)

Exemple : Soit à trier la suite 4, 1, 8, 2, 3, 7, 9, 5, 6

Etape 2 :
2

On fait sortir les deux 1er 3 1 4 5 6 9

listes de la file, on les 7
fusionne en une liste
croissante 8
Exercice 5. (Application File : Tri FIFO)

Exemple : Soit à trier la suite 4, 1, 8, 2, 3, 7, 9, 5, 6

Etape 3 :
2 1
insérer la liste fusionnée 3 4
dans la file
7 5

8 6

9
Exercice 5. (Application File : Tri FIFO)

Exemple : Soit à trier la suite 4, 1, 8, 2, 3, 7, 9, 5, 6

Etape 2 :
2 1

On fait sortir les deux 1er 3 4

listes de la file, on les 7 5
fusionne en une liste
croissante 8 6

9
Exercice 5. (Application File : Tri FIFO)

Exemple : Soit à trier la suite 4, 1, 8, 2, 3, 7, 9, 5, 6

Etape 2 :

On fait sortir les deux 1er 1 2 3 4 5 6 7 8 9

listes de la file, on les
fusionne en une liste
croissante
Exercice 5. (Application File : Tri FIFO)

Exemple : Soit à trier la suite 4, 1, 8, 2, 3, 7, 9, 5, 6

Etape 3 :
1
insérer la liste fusionnée 2
dans la file
3

9
Exercice 5. (Application File : Tri FIFO)

Écrire l’algorithme de ce tri, en utilisant les opérations de base sur la file :

• Init_file (F) : retourne une file vide F
• Enfiler (F, e) : ajoute l’élément e à la file F
• Défiler (F) : supprime un élément de la file F et retourne l’élément supprimé

Exemple : Soit à trier la suite 4, 1, 8, 2, 3, 7, 9, 5, 6

Tri_FIFO (T : tab_entier, N : entier)
Var F : File
i : entier 1. Au départ, chaque nombre est mis dans une
L,L1,L2 : LS1 liste ne contenant que lui.
Début
Init_file(F) Toutes ces listes sont mises dans une file
Pour i de 1 à N faire (FIFO)
L := new_liste(T[i])
enfiler(F,L)
Fpour
2. On fait sortir deux listes de la file, on les
Tant que NON Vide(F) faire fusionne en une liste croissante
L1 := défiler(F)
Si NON Vide(F) Alors 3. On fait rentrer la liste résultat dans la file.
L2 := défiler(F) • On répète (2) et (3) jusqu’à ce que la file ne
L := Fusion(L1,L2)
contienne plus qu’une seule liste, ça sera alors la
enfiler(F,L)
fsi suite ordonnée
Fait

Pour i de 1 à N faire 4. Récupération des éléments de la liste dans le

T[i] := supprime_tête(L1) tableau T
Fpour
FIN
Tri_FIFO (T : tab_entier, N : entier)
Var F : File
i : entier 1. Au départ, chaque nombre est mis dans une
L,L1,L2 : LS1 liste ne contenant que lui.
Début
Init_file(F) Toutes ces listes sont mises dans une file
Pour i de 1 à N faire (FIFO)
L := new_liste(T[i])
enfiler(F,L)
Fpour
2. On fait sortir deux listes de la file, on les
Tant que NON Vide(F) faire fusionne en une liste croissante
L1 := défiler(F)
Si NON Vide(F) Alors 3. On fait rentrer la liste résultat dans la file.
L2 := défiler(F) • On répète (2) et (3) jusqu’à ce que la file ne
L := Fusion(L1,L2)
contienne plus qu’une seule liste, ça sera alors la
enfiler(F,L)
fsi suite ordonnée
Fait

Pour i de 1 à N faire 4. Récupération des éléments de la liste dans le

T[i] := supprime_tête(L1) tableau T
Fpour
FIN
Tri_FIFO (T : tab_entier, N : entier)
Var F : File
i : entier 1. Au départ, chaque nombre est mis dans une
L,L1,L2 : LS1 liste ne contenant que lui.
Début
Init_file(F) Toutes ces listes sont mises dans une file
Pour i de 1 à N faire (FIFO)
L := new_liste(T[i])
enfiler(F,L)
Fpour
2. On fait sortir deux listes de la file, on les
Tant que NON Vide(F) faire fusionne en une liste croissante
L1 := défiler(F)
Si NON Vide(F) Alors 3. On fait rentrer la liste résultat dans la file.
L2 := défiler(F) • On répète (2) et (3) jusqu’à ce que la file ne
L := Fusion(L1,L2)
contienne plus qu’une seule liste, ça sera alors la
enfiler(F,L)
fsi suite ordonnée
Fait

Pour i de 1 à N faire 4. Récupération des éléments de la liste dans le

T[i] := supprime_tête(L1) tableau T
Fpour
FIN
Tri_FIFO (T : tab_entier, N : entier)
Var F : File
i : entier 1. Au départ, chaque nombre est mis dans une
L,L1,L2 : LS1 liste ne contenant que lui.
Début
Init_file(F) Toutes ces listes sont mises dans une file
Pour i de 1 à N faire (FIFO)
L := new_liste(T[i])
enfiler(F,L)
Fpour
2. On fait sortir deux listes de la file, on les
Tant que NON Vide(F) faire fusionne en une liste croissante
L1 := défiler(F)
Si NON Vide(F) Alors 3. On fait rentrer la liste résultat dans la file.
L2 := défiler(F) • On répète (2) et (3) jusqu’à ce que la file ne
L := Fusion(L1,L2)
contienne plus qu’une seule liste, ça sera alors la
enfiler(F,L)
fsi suite ordonnée
Fait

Pour i de 1 à N faire 4. Récupération des éléments de la liste dans le

T[i] := supprime_tête(L1) tableau T
Fpour
FIN
Tri_FIFO (T : tab_entier, N : entier)
Var F : File
i : entier 1. Au départ, chaque nombre est mis dans une
L,L1,L2 : LS1 liste ne contenant que lui.
Début
Init_file(F) Toutes ces listes sont mises dans une file
Pour i de 1 à N faire (FIFO)
L := new_liste(T[i])
enfiler(F,L)
Fpour
2. On fait sortir deux listes de la file, on les
Tant que NON Vide(F) faire fusionne en une liste croissante
L1 := défiler(F)
Si NON Vide(F) Alors 3. On fait rentrer la liste résultat dans la file.
L2 := défiler(F) • On répète (2) et (3) jusqu’à ce que la file ne
L := Fusion(L1,L2)
contienne plus qu’une seule liste, ça sera alors la
enfiler(F,L)
fsi suite ordonnée
Fait

Pour i de 1 à N faire 4. Récupération des éléments de la liste dans le

T[i] := supprime_tête(L1) tableau T
Fpour
FIN