Les piles

Prototype


Les arbres
Page Suivante
Peut-être plus encore que les piles, les files d’attente (ou simplement files) font partie de notre vie courante ; du moins en sommes-nous plus conscients, puisqu’il nous arrive quotidiennement de faire la queue devant un guichet. Une file est un type de données abstrait formé d’un nombre variable, éventuellement nul, de données, sur lequel on peut effectuer les opérations suivantes :
  • ajout d’une nouvelle donnée ;
  • test déterminant si la file est vide ou non ;
  • consultation de la première donnée ajoutée et non supprimée depuis (donc la plus ancienne) s’il y en a une ;
  • suppression de la donnée la plus ancienne.
    • Cette conception s’accorde bien avec la conception intuitive que l’on a d’une file d’attente.
    Les files d’attente ont une grande importance en informatique ; elles s’appliquent à deux types de problèmes :
    • la simulation de files réelles ; les techniques modernes de communication (terminaux reliés à un ou plusieurs centres de communication). Il est devenu courant d’écrire des programmes qui étudient les comportements de réseaux.
    • la résolution de problèmes purement informatiques, en particulier dans le domaine des systèmes d’exploitation.

      • Analyse fonctionnelle :

      La file est constituée
    • d’une suite d’éléments ordonnés a_{1}, a_{2}, \ldots, a_{n}, désignée ici par F, éventuellement vide.
    • des primitives suivantes :
    • creer(F) Cette fonction crée une file de nom F et retourne la valeur vrai si l’opération a pu s’effectuer sans problème, sinon elle retourne faux.
    • filevide(F) Cette fonction teste la vacuité de la file F et retourne vrai si la file est vide faux sinon.
    • enfiler(x, F) Cette fonction ajoute un élément en queue de file, renvoie faux s’il l’élément n’a pas pu être introduit, vrai sinon.
    • defiler(F) Cette primitive retire l’élément de tête de la file.
    • premier(F) Cette fonction renvoie la valeur de l’élément en tête de file, si la pile n’est pas vide, sinon retourne un code d’erreur.

Mise en œuvre d’une file dans un tableau

Implémentée dans un tableau, la file ne peut avoir qu’une taille maximale égale à la dimension du tableau, et peut être schématisée selon la figure ??
Notez que le fait de choisir les indices TETE et QUEUE comme nous l’avons fait, avec {TETE désignant la position passée de la tête de la file, n’influe pas sur le problème. Cette convention facilite uniquement l’écriture des fonctions vide et enfiler.

Rendered by QuickLaTeX.com

Un problème se pose : même si la taille de la file reste constamment en dessous du maximum permis n, la file « monte » inexorablement, puisque les défilages s’effectuent par le bas et les enfilages par le haut. Si l’on n’y prend garde, la file débordera du tableau au bout de n opérations enfiler.

Rendered by QuickLaTeX.com


Plusieurs solutions sont possibles :
  1. à chaque défilage, récupérer l’espace libéré en bas du tableau en « redescendant » toute la file d’un cran. C’est la solution simple à mettre en œuvre, mais coûteuse sur les grandes files.
  2. Laisser la file monter tant qu’il reste de la place pour effectuer les enfilages ; quand il n’y a plus de place et que l’on veut opérer un enfilage, on récupère d’un seul coup la place libérée par les défilages en « redescendant » la file de toute la hauteur possible. Cette solution est plus économique que la précédente, mais exige encore des transferts d’informations inutiles.
  3. Quand la queue atteint le haut du tableau, effectuer les enfilages suivants à partir du bas du tableau, qui prend l’aspect de la figure ??
L’intérêt de cette méthode est qu’elle ne nécessite aucun décalage. On parle d’une représentation par file circulaire, on peut représenter chacune des deux figures précédentes par un anneau.
La programmation de cette solution présente un piège : le test déterminant si la file est vide s’écrit maintenant TETE = QUEUE si la file à n éléments. Pour pouvoir distinguer entre ces deux cas (file vide et file pleine), on imposera à la file la capacité maximale n-1 (et non n). Dans ces conditions |TETE-QUEUE|\geq1 si la file n’est pas vide. \vspace{.5cm}

Une file générique

Il est aisé de former le type de données abstrait d’une file au moyen du code du type de la liste. Seul le fichier File.tda doit être écrit sur le modèle de Liste.tda ou Pile.tda. 
#ifndef LISTE_H
#include "Liste.h"
#endif
#define file(type_objet)                        \
typedef struct nom(type_objet, file)            \
{                                               \
     void     * rep ;                           \
     type_objet (*copier_objet)   (type_objet) ;\
     void       (*detruire_objet) ()           ;\
     void       (*afficher_objet) (type_objet) ;\
} * nom(type_objet, file) ;                     \
nom(type_objet, file) nom(type_objet,file_creer)\
    (type_objet (*cop) (type_objet),            \
     void       (*det) (),                      \
     void       (*aff) (type_objet))            \
{                                               \
    nom(type_objet, file) f ;                   \
    lier_liste () ;                             \
    f = (nom(type_objet, file)) malloc          \
      (sizeof (struct nom (type_objet, file))) ;\
    f->rep = (*Liste.creer) () ;                \
    f->afficher_objet = aff ;                   \
    f->detruire_objet = det ;                   \
    f->copier_objet = cop ;                     \
    return f ;                                  \
}                                               \
void nom(type_objet, file_afficher)             \
                  (nom(type_objet, file) p)     \
{                                               \
    if (p->afficher_objet) (*Liste.afficher)    \
     (p->rep, p->afficher_objet) ;              \
    else                                        \
     printf                                     \
 ("ERR : fonction d'affichage d'obj nulle\n") ; \
}                                               \
void nom(type_objet, file_enfiler)              \
    (nom(type_objet, file) p, type_objet obj)   \
{                                               \
    (*Liste.dernier) (p->rep) ;                 \
    (*Liste.insererapres)                       \
            (p->rep, (p->copier_objet) (obj)) ; \
}                                               \
void nom(type_objet, file_desenfiler)           \
  (nom(type_objet, file) p)                     \
{                                               \
    (*Liste.premier) (p->rep) ;                 \
    (*Liste.oter) (p->rep, p->detruire_objet) ; \
}                                               \
int nom(type_objet, file_nulle)                 \
                  (nom(type_objet, file) p)     \
{                                               \
    return ((*Liste.nulle) (p->rep)) ;          \
}
Les piles
Les arbres
Page Suivante