Structure de données

Piles et Files

Zakaria sawadogo
 Contenu

❏ Définition de Pile
❏ Définition et déclaration de Pile
❏ Opérations sur les Piles
❏ Définition de File
❏ Définition et déclaration de File
❏ Opérations sur les Files
❏ Cas implémentation statique d’une pile et
File
Zakaria sawadogo
 Pile
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.

Zakaria sawadogo
 Pile
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.

Zakaria sawadogo
 Définition et déclaration d’une Pile

▪ Le sommet de la pile est le premier élément et le pointeur de tête pointe sur ce

sommet.
▪ Il faut commencer par définir un type de variable pour chaque élément de la
pile. La déclaration est identique à celle d'une liste chaînée, par exemple pour
une pile de chaînes de caractères :

Type Pile = ^Element

Type Element = Structure
Info : chaîne de caractères
Suivant : Pile
Fin Structure

Zakaria sawadogo
 Opérations autorisées

Les opérations autorisées avec une pile sont :

▪ 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.

Une pile peut être implémentée dans un tableau (pile statique) ou dans
une liste chaînée (pile dynamique).

Zakaria sawadogo
 Empiler
Empiler un élément revient à faire une insertion en tête dans la liste chaînée.

Procedure Empiler (Entrée/Sortie Tête : Pile, Entrée Valeur : chaîne de

caractères)
/* Ajout d'un élément dans une pile passée en paramètre */
Variable locale
P : Pile /* pointeur auxiliaire */
DEBUT
Allouer(P) /* Réserve un espace mémoire pour le nouvel élément */
P^.Info = Valeur /* stocke dans l'Info de l'élément pointé par P la valeur
passée en paramètre *
P^.Suivant = Tête /*stocke dans l'adresse du Suivant l'adresse de Tête */
Tête <=P /* Tête pointe maintenant sur le nouvel élément */
FIN

Zakaria sawadogo
 Dépiler
Dépiler revient à faire une suppression en tête.
Procedure Dépiler (Entrée/Sortie Tête : Pile)
/* Suppression de l'élément au sommet de la pile passée en paramètre */
Variable locale
P : Pile /* Pointeur nécessaire pour libérer la place occupée par l'élément dépilé
*/
DEBUT
/* Vérifier si la pile est vide */
SI Tête <> NIL ALORS /* la pile n'est pas vide donc on peut dépiler */
P <=Tête /* on garde l'adresse du sommet pour désallouer */
Tête <=Tête^.Suivant /* P va pointer sur le 2ème élément de la pile
qui devient le sommet */
Désallouer(P)
FINSI
FIN

Zakaria sawadogo
 Dépiler
Si la pile ne contient qu'un élément, Tête prend la valeur Nil et la nouvelle pile
est vide.

Zakaria sawadogo
Procédures et fonctions de base d’une Pile

Procedure InitPile (Sortie Tête : Pile) Fonction PileVide (Tête : Pile) : booléen
/* Initialise la création d’une pile */ /* indique si la pile est vide ou non*/
DEBUT DEBUT
Tête <=Nil Retourner (Tête = Nil)
FIN FIN

Fonction SommetPile (Tête : Pile) : variant

/* renvoie la valeur du sommet si la pile n'est pas vide */
DEBUT
SommetPile <=Tête^.Info
FIN

Zakaria sawadogo
 Files

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.

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.

Zakaria sawadogo
Files

Zakaria sawadogo
 Files
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 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.

Zakaria sawadogo
 Déclaration et définition d’une File

▪ Le pointeur de tête pointe sur le premier élément de la file, et le pointeur

de queue sur le dernier.
▪ Il faut commencer par définir un type de variable pour chaque élément de
la file.
▪ La déclaration est identique à celle d'une liste chaînée, par exemple pour
une file de chaînes de caractères :

Type File = ^Element

Type Element = Structure
Info : Type ( entier etc)
Suivant : File
Fin Structure

Zakaria sawadogo
 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.

On peut implémenter une file dans un tableau (file statique) ou dans une
liste chaînée (file dynamique).

Zakaria sawadogo
 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é.
Procedure Enfiler (Entrée/Sortie : Tête, Queue : File, Entrée Valeur : variant)
/* Ajout d'un élément dans une file */
Variable locale
P : File /* Pointeur nécessaire pour allouer la place au nouvel élément */
DEBUT
Allouer(P) /* Réserve un espace mémoire pour le nouvel élément */
P^.Info <=Valeur /* stocke la valeur dans l'Info de l'élément pointé par P */
P^.Suivant <=Nil /*stocke Nil (ce sera le dernier de la file) dans Suivant */
SI Tête = Nil ALORS /* file vide */
Tête <=P /* Tête pointe maintenant sur l'élément unique */
SINON /* il y a au moins un élément */
Queue^.Suivant <=P /* le nouvel élément est ajouté au dernier */
FINSI
Queue <=P /* Queue pointe maintenant sur l'élément ajouté */
FIN

Zakaria sawadogo
 Défiler
Défiler est équivalent à dépiler et 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.

Procedure Défiler (Entrée/Sortie Tête, Queue : File, Sortie Valeur : chaîne de caractères)
/* Suppression de l'élément de tête de la file passée en paramètre */
Variable locale
P : File /* Pointeur nécessaire pour libérer la place de l'élément supprimé */
DEBUT
SI Tête <> NIL ALORS /* la liste n'est pas vide donc on peut défiler */
Valeur <=Tête^.info /* on récupère l'élément de tête */
P <=Tête /* on garde l'adresse du sommet pour désallouer */
Tête <=Tête^.Suivant /* P va pointer sur le 2ème élément de la pile qui devient le
sommet */
Désallouer(P)
Si Tête = Nil ALORS
Queue <=Nil /* la file a été vidée */
FINSI
FINSI
FIN
Zakaria sawadogo
Procédures et fonctions de base d’un File

Procedure InitFile (Sortie Tête : File) Fonction FileVide (Tête : File) : booléen
/* Initialise la création d’un File */ /* indique si le File est vide ou non*/
DEBUT DEBUT
Tête <=Nil Retourner (Tête = Nil)
FIN FIN

Fonction MaTeteFile (Tête : File) : variant

/* renvoie la valeur du sommet si le File n'est pas vide */
DEBUT
SommetFile <=Tête^.Info
FIN

Zakaria sawadogo
 Cas implémentation statique d’une
pile
▪ La pile est représentée par une structure contenant les
champs suivants :
+ L'indice du sommet de la pile: un entier
+ Un tableau des éléments de la pile

Zakaria sawadogo
Principe

Zakaria sawadogo
 Cas implémentation statique d’une
pile
Exercice (A faire) Réaliser l’implémentation statique de la
pile en utilisant les tableaux en redéfinissant les mêmes
fonctions de manipulations des piles vues pour le cas
dynamique.
InitPile()
PileVide(p : Pile)
PilePleine(p : Pile)
Sommet(p : Pile, x : entier)
Empiler (p : Pile, x : entier)
Depiler (p : Pile, x : entier)
Afficher (p : Pile)
 Cas implémentation statique d’une
file
La file est représentée par une structure contenant les
champs suivants :

+ L'indice de la tête de la file: un entier

+ L'indice de la queue de la file: un entier
+ Un tableau des éléments de la file

Zakaria sawadogo
Principe

Zakaria sawadogo
 Cas implémentation statique d’une file

Exercice. Réaliser l’implémentation statique de la file en

utilisant les tableaux en redéfinissant les mêmes fonctions de
manipulations des files vues pour le cas dynamique.

InitFile()
FileVide(File* f)
FilePleine(File* f)
Enfiler(int elem, File* f)
Defiler(File *f)
Afficher(File *f)

Zakaria sawadogo
Merci pour votre attention

Zakaria sawadogo