PILE :
elle est une suite de cellules allouées dynamiquement (liste chaînée) où l’insertion et la suppression d’un élément se font toujours en tête de liste. L’image intuitive d’une pile peut être donnée par une pile d’assiettes, ou une pile de dossiers à condition de supposer qu’on prend un seul élément à la fois (celui du sommet). On peut résumer les contraintes d’accès par le principe « dernier arrivé, premier sorti » qui se traduit en anglais par : Last In First Out.
La structuration d’un objet en pile s’impose lorsqu’on mémorise des informations qui devront être traitées dans l’ordre inverse de leur arrivée. C’est le cas, par exemple, de la gestion des adresses de retour dans
l’exécution d’un programme récursif. En supposant que les éléments de la pile sont des entiers, celle-ci se
déclare de la façon suivante :
Types
Pile = ^Cellule
Cellule = Struct
Elem : Entier
Suiv : Pile
FinStruct
Var
P : Pile
Manipulation d’une pile
Du point de vue manipulation, les contraintes d’accès sont matérialisées par les procédures et les fonctions suivantes :
· Procédure Initialiser(Var P : Pile) : crée une pile vide P
· Fonction Pile_Vide (P : Pile) : Booléen : Renvoie la valeur vrai si la pile est vide.
· Procédure Empiler(x : Entier ; Var P : Pile) : ajoute l’élément x au sommet de la pile
Procédure Initialiser(Var P : Pile)
Début
P ¬ Nil
Fin
Fonction Pile_Vide(P : Pile) : Booléen
Début
Pile_Vide ¬ (P = Nil)
Fin
Procédure Empiler(x : Entier ; Var P : Pile)
Variables
Q : Liste
Début
Allouer(Q)
Q^.Elem ¬ x
Q^.Suiv ¬ P
P ¬ Q
Fin
Procédure Dépiler (Var x : Entier ; Var P : Pile) : dépile le sommet de la pile et le met dans la variable x
Procédure Dépiler(Var x : Entier ; Var P : Pile)
Début
Si NON(Pile_Vide(P)) Alors
x ¬ P^.Elem
Q ¬ P
P ¬ P^.Suiv
Libérer(Q)
Sinon
Ecrire(”impossible, la pile est vide”)
FinSi
Fin
FILE : Une file est une suite de cellules allouées dynamiquement (liste chaînée) dont les contraintes d’accès sont définies comme suit :
- On ne peut ajouter un élément qu’en dernier rang de la suite
- On ne peut supprimer que le premier élément.
L’image intuitive d’une file peut être donnée par la queue à un guichet lorsqu’il n’y a pas de resquilleurs. On peut résumer les contraintes d’accès par le principe « premier arrivé, premier sorti » qui se traduit en
anglais par : Fast In First Out.
La structuration d’un objet en file s’impose en particulier lorsqu’une ressource doit être partagée par plusieurs utilisateurs : il y a formation d’une file d’attente. Un exemple est donné par le spooler d’impression qui est un programme qui reçoit, traite, planifie et distribue les documents à imprimer dans un système multiprogrammé. En supposant que les éléments de la file sont des entiers, celle-ci se
déclare de la façon suivante :
Types
Liste = ^Cellule
Cellule = Struct
Elem : Entier
Suiv : Liste
FinStruct
File = Struct
Tête : Liste
Queue : Liste
FinStruct
Variables
F : File
Manipulation d’une file
Du point de vue manipulation, les contraintes d’accès sont matérialisées par les procédures et les fonctions suivantes :
· Procédure Initialiser(Var F : File) : crée une file vide F
· Procédure Ajouter(x : Entier ; Var F : File) : ajoute l’élément x à la fin de la file
· Procédure Extraire (Var x : Entier ; Var F : File) : extrait le sommet de la file et le met dans la variable x.
Procédure Initialiser(Var F : File)
Début
F.Tête ¬ Nil
F.Queue ¬ Nil
Fin
Procédure Ajouter(x : Entier ; Var F : File)
Variables
P : Liste
Début
Allouer(P)
P^.Elem ¬ x
P^.Suiv ¬ Nil
Si (F.Queue # Nil) Alors
F.Queue^.Suiv ¬ P
Sinon
F.Tête ¬ P
FinSi
F.Queue ¬ P
Fin
Dans le cas où la file est vide, comme la queue, la tête de la file doit également pointer vers le nouvel élément.
Procédure Extraire(Var x : Entier ; Var F : File)
Variables
P : Liste
Début
Si (F.Tête = Nil) Alors
Ecrire(”impossible, la file est vide”)
Sinon
P ¬ F.Tête
x ¬ F.Tête^.Elem
F.Tête ¬ F.Tête^.Suiv
Libérer(P)
FinSi
Fin