Ecole Supérieure de Technologie et d’Informatique

Cours sur les Piles et les Files

Pour les classes IA1

Mai 2011

Structure de Donnée Avancée : Pile (Stack) I/ Définition Une pile est une liste d’éléments de même type où les ajouts, suppressions, et accès ne sont possibles que par rapport à un seul élément : LE SOMMET DE LA PILE. Le sommet (ou la tête) est le dernier élément qui a été ajouté à la pile. Une pile est une structure de données mettant en oeuvre le principe « dernier entré, premier sorti» (LIFO : Last-In, First-Out en anglais). L’élément ôté (supprimé) de l’ensemble par l’opération SUPPRESSION est spécifié à l’avance (et donc cette opération ne prend alors que l’ensemble comme argument) : l’élément supprimé est celui le plus récemment inséré. L’opération INSERTION dans une pile est communément appelée EMPILER, et l’opération SUPPRESSION : DÉPILER. Il est facile d’implémenter une pile au moyen d’un tableau. La seule difficulté dans cette implémentation est la gestion des débordements de pile qui interviennent quand on tente d’effecteur l’opération DÉPILER sur une pile vide et l’opération EMPILER sur un tableau codant la pile qui est déjà plein. Ce dernier problème n’apparaît pas lorsque l’on implémente les piles au moyen d’une structure de données dont la taille n’est pas fixée a priori (comme une liste chaînée). II/Mode de représentation contigüe II/1) Définition du type de données Pile : La structure de données comprend un tableau et le nombre d’éléments significatifs de ce tableau. Il est nécessaire de fixer dès le départ une valeur maximale du nombre total des éléments de la Pile. Nous obtenons la structure suivante #define MAX 100 Typedef struct pile {Type_element Tableau [Max] ; int sommet ; //compris entre 0 et MAX : c’est l’indice de la première case libre } Pile ; II/2) Implémentation des opérations appliquées aux Piles : II/2/1 Création de pile Pile CréerPileVide(){Pile P ; P.sommet=0 ; Return P ;} II/2/2 Test pile vide int EstPileVide() {Return (P.sommet = = 0) ; } II/2/3 Test pile pleine int EstPileVide() {Return (P.sommet = = Max) ;} II/2/4 Accès à la tête de la Pile Type_element tete (Pile P) {if ( !EstPileVide(P)) return (P.Tableau[p.Sommet-1]) else printf("Erreur : Pile vide ") ;} II/2/5 Empiler un élément Pile Empiler (Pile P, Type_element e) {if ( ! EstPilePleine(P)){ p.Tableau[p.Sommet] = e ; P.Sommet ++ ;} Else printf("Erreur : Pile pleine ") ; Return (P) ;}

II/2/6 Dépiler un élément Pile Depiler (Pile P) {if ( ! EstPileVide(P)) P.Sommet-- ; else printf("Erreur : Pile Vide ") ; return (P) ;} II/2/7 Test de pile vide int EstPileVide (Pile P) {return (P.Sommet = = 0) ;} II/2/8 Test de pile pleine int EstPilePleine (Pile P) {return (P.Sommet > MAX) ;} III Implémentation chaînée Pour implémenter une pile chaînée, nous allons reprendre la même structure de données que nous avons définie pour les listes chaînées.

Dans ce schéma une pile est une succession de cellules. Chaque cellule de la pile contient deux champs : • un champ pour l’information, • un champ pointeur sur l’élément suivant. L’identificateur de la pile (p) représente le sommet (tête) de la pile. Les éléments sont chaînés grâce au pointeur (suivant), le dernier élément de la pile (le premier qui a été inséré) est suivi par la valeur NULL. III/1 Définition chaînée du type de données Pile : La structure de données pile est la même que la structure de données liste.

Typedef struct cellule

{Type_element Val ;

Cellule * succ ;} Cellule ; Typedef Cellule * Pile ; III/2 Implémentation des opérations appliquées aux Piles : III/2/1 Création de pile Pile CréerPileVide() {Pile P ; P=NULL; Return P ;}

III/2/2 Test pile vide int EstPileVide() {Return (P==NULL) ;} III/2/3 Accès à la tête de la Pile Type_element tete (Pile P) {if ( !EstPileVide(P)) return (P→Val); else printf("Erreur : Pile vide ") ;} III/2/4 Empiler un élément Pile Empiler (Pile P, Type_element e) {Cellule * NC ; if(NC) {NC=(Cellule *)malloc(sizeof(NC)) ; NC→Val=e; NC→succ=P; P=NC;} Else printf("Erreur : mémoire insuffisante ") ; Return (P) ;} III/2/5 Dépiler un élément Pile Depiler (Pile P) {Cellule * NC ; if ( ! EstPileVide(P)) {NC=P; p=p→succ ; free(NC) ;} else printf("Erreur : Pile Vide ") ; return (P) ;} IV Conclusion Les piles sont des structures de données très fréquentes en informatique, l’un de leurs principaux intérêts est d’éviter d’écrire des algorithmes récursifs. L’inconvénient majeur de la récursivité, c’est qu’elle peut rendre les programmes très lents. Les piles permettent de résoudre ce problème. En effet l’emploi d’une pile permet de passer d’un algorithme récursif à un algorithme itératif. Une autre des applications des piles est l’évaluation d’expressions arithmétiques. Du point de vue implémentation des piles, et étant donné le type des opérations effectuées (ajout, suppression et accès au sommet), les représentations chaînée et contiguë sont équivalentes sur le plan de la complexité temporelle. Par contre le problème de limitation de la mémoire dans le cas d’une pile contigüe reste posé, ainsi que le problème de gestion de la mémoire dans le cas d’une pile chaînée : les pointeurs rendant cette gestion plus lourde.

Structure de Donnée Avancée : File (Queue) I/ Définition d’une File Une file est une structure linéaire où l’ajout d’un élément se fait en fin tandis que la lecture et la suppression se font au début. Les files suivent le principe F.I.F.O (First In First Out) : le premier arrivé est le premier à être servi. En informatique, la structure de file est une liste qui n’autorise que les opérations suivantes : • ajout en fin de la liste, • retrait au début de la liste, • accès à l’élément en début de liste.

Comme pour les listes et pour les piles, les deux modes de représentation chaînée et contigue sont utilisées pour implémenter une file. Pour bien comprendre l’implémentation utilisant la représentation contiguë, un exemple complet sera traité. En effet, il est possible d’implémenter les files en utilisant les tableaux de deux manières différentes : • Mode de représentation linéaire, • Mode de représentation circulaire Les tableaux gérés linéairement présentent un défaut, et les tableaux gérés circulairement permettent d’exploiter au mieux la capacité maximale en nombre d’éléments, et d’implémenter une file de façon optimale. II/1) Implémentation contiguë linéaire Dans une file l’ajout se fait à la fin, tandis que la lecture et la suppression se font au début. Si l’on utilise un tableau, cela va se traduire par un décalage de tous les éléments lors de la suppression (ou lors de l’ajout : cela dépend de comment on décide d’organiser les données dans la file). Etant donné que les suppressions ainsi que les ajouts sont fréquents, cette méthode n’est pas optimale. Pour supprimer un élément (ou l’ajouter) dans une file de n éléments, il faut à chaque fois faire n opérations de décalage. Etant donné que l’opération de suppression risque de se répéter plusieurs fois, cette méthode n’est pas avantageuse. II/2) Implémentation contiguë circulaire Il faut « circulariser » le tableau en raisonnant en terme de modulo MAX quand on incrémente les indices Tête et Queue. Dans ce cas nous allons considérer que le premier indice du tableau est égal à zéro (à cause du calcul fait en fonction de modulo MAX). Un tableau de capacité MAX n’accueillera en fait que MAX-1 éléments. Dans ce type d’implémentation : • si Tête = Queue alors la file est vide, cela se produit après la création d’une file ou après des défilements successifs. • si (Queue + 1) modulo MAX = Tête alors la file est pleine.

Le tableau a une capacité maximale de 8 éléments, • les éléments effectifs dans la file sont au nombre de 7, • l’indice Tête a pour valeur 5, • l’indice Queue a pour valeur 4,

• si on défile successivement 7 fois de la file, l’indice Tête va prendre comme valeur (5+7) modulo 8 = 4 qui est égal à Queue -> la file est à nouveau vide.

III/1)Définition contiguë du type de données File :

Le type file intègre dans une même structure : • le tableau des données de capacité MAX éléments, • l’indice correspondant à la tête de la file, • l’indice correspondant à la queue de la file. #define Max = 100 Typedef struct file {Type_element Tab[Max] ; int Tête ;int Queue ;}File ; III/2) Implémentation des opérations appliquées aux Files : III/2/1 Création d’une file File CréerFileVide () {File f ; f.Tête = 0 ; f.Queue = 0 ; return(f) ;} III/2/2 Est File vide int EstFileVide (File f) {return (f.Tête= = f.Queue) ;} III/2/3 Est File pleine Une file est pleine, si elle a atteint sa capacité maximale en nombre d’éléments. Int FilePleine (File f) {return ((f.Queue + 1) % Max == f.Tête) ;} III/2/4 Accès à un élément Type_element LireFile(File f) {if ( ! EstFileVide (f)) return (f.Tab[f.Tête]) else printf(“Erreur : File vide “);} III/2/5 Enfiler un élément Il faut vérifier que la file n’est pas pleine avant d’ajouter un élément. File Enfiler(type_element e, File f) {if ( ! EstFilePleine (f)) {f.Tab[f.Queue] = e ; f.Queue = (f.Queue + 1) % Max ;} else Printf( “Erreur File pleine “); return (f) ; } III/2/6 Défiler un élément File Défiler ( File f) {if ( ! EstFileVide (f)) {f.Tête= (f.Tête + 1) % Max ;} Else Printf( “Erreur File vide “); return(f) ;}

IV/ Implémentation chaînée Le choix de la structure de données dans ce cas est facile à faire, il suffit d’une liste chaînée et de deux pointeurs : • un pointeur pour indiquer la cellule de tête de la file, • et un pointeur pour indiquer la cellule de fin de la file. Le pointeur Queue permettra de faciliter les ajouts à la fin de la file. Au lieu de parcourir toute la file à la recherche du dernier élément, nous disposons d’un pointeur qui permet d’ajouter directement à cette adresse. Le pointeur Tête permettra d’accéder à la cellule de Tête pour lire la valeur qui s’y trouve ou pour défiler l’élément.

Typedef struct cellule {Type_Elément Valeur ; struct cellule * suivant ; }Cellule ; Typedef file {Cellule * Tête ; Cellule * Queue ;}File ; IV/1 Implémentation chaînée des opérations appliquées aux Files : IV/1/1 Création d’une file Pour créer une nouvelle file il suffit d’initialiser les pointeurs Tête et Queue à la valeur NULL. File CréerFileVide () {File f ; f.Tête = NULL ; f.Queue =NULL ; return (f) ;} IV/1/2 File vide int EstFileVide (file f) {Return (f.Tête= = NULL) ;} IV/1/3 Accès à un élément Type_Elément LireFile(f : File) { if ( ! EstFileVide (f)) return (f.Tête→valeur) ; else Printf( “Erreur File vide “);} IV/1/4 Enfiler un élément

Le schéma ci-dessus illustre l’enfilement d’un élément dans une file non vide, ainsi que la succession d’étapes à suivre. 1) allouer une nouvelle cellule NC, 2) renseigner la valeur ainsi que le suivant de NC à e et NULL, 3) mettre à jour le suivant du dernier élément de la file à NC, 5) mettre à jour le pointeur Queue à NC.

le cas d’enfilement d’un élément dans une file vide au départ : La tête et la queue étaient égales à NULL. Les étapes à suivre sont un peu différentes : 1) allouer NC, 2) renseigner la valeur et le suivant de NC à e et NULL, 4) mettre à jour le pointeur Tête à NC, 5) mettre à jour le pointeur Queue à NC. File Enfiler(Elément e, File f) {cellule * NC ; (1) NC=(Cellule*)malloc(sizeof(Cellule) ); if (NC) { (2) NC→valeur =e ; (2) NC→suivant = NULL ; if ( ! EstFileVide (f)) {(3) f.Queue→suivant = NC ;} Else (4) f.Tête = NC ; (5) f.Queue (cid:2) NC ;} Return (f) ;} IV/1/5 Défiler un élément Pour défiler un élément deux cas se présentent : • la file contient 2 ou plusieurs éléments,

• la file contient un seul élément, et devient vide suite au défilement.

File Défiler (File f) {Cellule*NC ; if ( ! EstFileVide (f)) {(1) NC = f.Tête ; (2) f.Tête = f.Tête→suivant ; (3) free (NC) ; if (f.Tête == NULL) (4) f.Queue = NULL ;} Else printf("Erreur File vide ") ; Return (f) ;}

V/ Conclusion Les files sont utilisées dans plusieurs domaines en informatique, nous avons parlé au début du chapitre de la gestion des événements par exemple. Les caractères tapés sur le clavier doivent être traités dans leur ordre d’arrivée, ils sont donc stockés dans une file. La file est une structure qui est très employée par les systèmes d’exploitation. Ces structures de données complexes sont utilisées pour parcourir les graphes ou les arbres. En résumé nous pouvons dire que les files et les piles servent surtout à stocker des données en attente d’un traitement, seule la priorité est différente : pour les files, le premier arrivé est prioritaire, tandis que pour les piles c’est le dernier qui l’est. Les deux types de représentation que nous avons étudiés, c'est-à-dire la représentation contiguë circulaire, et la représentation chaînée, sont comparées de la même manière que pour les listes et les piles. La représentation contiguë est très efficace du point de vue gestion de la mémoire, mais elle est limitée quant à l’utilisation de cet espace mémoire. La complexité des opérations pour cette représentation est optimale. Tandis que la représentation chaînée est très souple quant à l'emploi de la mémoire, il est possible d’ajouter autant d’éléments que possible. L’espace occupé est toutefois plus important. Le choix d’une méthode de représentation se fera donc nécessairement en fonction des besoins de l’application.

Exercice Ecrire un programme qui permet de comparer entre le contenu d’une pile et celui d’une file. Si les éléments de la pile de son sommet vers sa base, sont les mêmes que ceux de la file de sa tête vers sa queue, alors le programme retourne la valeur vrai, sinon il retourne faux. Donner une version itérative et une version récursive de ce programme.