Files

Les files sont utilisées en programmation pour gérer des objets qui sont en attente d'un traitement ultérieur, par exemple des processus en attente d'une ressource du système, des sommets d'un graphe, des nombres entiers en cours d'examen de certaines de leur propriétés, etc ... Dans une file les éléments sont systématiquement ajoutés en queue et supprimés en tête, la valeur d'une file est par convention celle de l'élément de tête. En anglais, on parle de stratégie FIFO First In First Out, par opposition à la stratégie LIFO Last In First Out des piles. De façon plus formelle, on se donne un ensemble E, l'ensemble des files dont les éléments sont dans E est noté Fil(E), la file vide (qui ne contient aucun élément) est F₀, les opérations sur les files sont vide, ajouter, valeur, supprimer:

• estVide est une application de Fil(E) dans (vrai, faux), estVide(F) est égal à vrai si et seulement si la file F est vide.
  
• ajouter est une application de E × Fil(E) dans Fil(E), ajouter(x,F) est la file obtenue à partir de la file F en insérant l'élément x à la fin de celle-ci.
  
• valeur est une application de Fil(E) \ F₀ dans E qui à une file F non vide associe l'élément se trouvant en tête.
  
• supprimer est une application de Fil(E) \ F₀ dans Fil(E) qui associe à une file F non vide la file obtenue à partir de F en supprimant son premier élément.
  

Les opérations sur les files satisfont les relations suivantes

Pour F ¹ F₀

supprimer(ajouter(x,F)) = ajouter(x ,supprimer(F))

valeur(ajouter(x,F))= valeur(F)

Pour toute file F

estVide(ajouter(x,F)) = faux

Pour la file F₀

supprimer(ajouter (x,F0))= F0

valeur(ajouter(x,F0)) = x

estVide(F0) = vrai

Figure 3.3 : File gérée par un tableau circulaire

Une première idée de réalisation sous forme de programmes des opérations sur les files est empruntée à une technique mise en oeuvre dans des lieux où des clients font la queue pour être servis, il s'agit par exemple de certains guichets de réservation dans les gares, de bureaux de certaines administrations, ou des étals de certains supermarchés. Chaque client qui se présente obtient un numéro et les clients sont ensuite appelés par les serveurs du guichet en fonction croissante de leur numéro d'arrivée. Pour gérer ce système deux nombres doivent être connus par les gestionnaires: le numéro obtenu par le dernier client arrivé et le numéro du dernier client servi. On note ces deux nombres par fin et début respectivement et on gère le système de la façon suivante

• la file d'attente est vide si et seulement si début = fin,
  
• lorsqu'un nouveau client arrive on incrémente fin et on donne ce numéro au client,
  
• lorsque le serveur est libre et peut servir un autre client, si la file n'est pas vide, il incrémente début et appelle le possesseur de ce numéro.
  

Dans la suite, on a représenté toutes ces opérations en Java en optimisant la place prise par la file en utilisant la technique suivante: on réattribue le numéro 0 à un nouveau client lorsque l'on atteint un certain seuil pour la valeur de fin. On dit qu'on a un tableau (ou tampon) circulaire. class File {

final static int MaxF = 100;

int debut;
int fin;
boolean pleine, vide;
int contenu[];

File () {
debut = 0; fin = 0;
pleine = false; vide = true;
contenu = new int[MaxF];
}

static File vide () {
return new File();
}

static void faireVide (File f) {
f.debut = 0; f.fin = 0;
f.pleine = false; f.vide = true;
}

static boolean estVide(File f) {
return f.vide;
}

static boolean estPleine(File f) {
return f.pleine;
}

static int valeur (File f) {
if (f.vide)
erreur ("File Vide.");
return f.contenu[f.debut];
}

private static int Successeur(int i) {
return (i+1) % MaxF;
}

static void ajouter (int x, File f) {
if (f.pleine)
erreur ("File Pleine.");
f.contenu[f.fin] = x;
f.fin = Successeur(f.fin);
f.vide = false;
f.pleine = f.fin == f.debut;
}

static void supprimer (File f) {
if (f.vide)
erreur ("File Vide.");
f.debut = Successeur(f.debut);
f.vide = f.fin == f.debut;
f.pleine = false;
}
}
Une autre façon de gérer des files consiste à utiliser des listes chaînées gardées (voir page X) dans lesquelles on connaît à la fois l'adresse du premier et du dernier élément. Cela donne les opérations suivantes:

class File {

Liste debut;
Liste fin;

File (Liste a, Liste b) {
debut = a;
fin = b;
}

static File vide () {
Liste garde = new Liste();
return new File (garde, garde);
}

static void faireVide (File f) {
Liste garde = new Liste();
f.debut = f.fin = garde;
}

static boolean estVide (File f) {
return f.debut == f.fin;
}

static int valeur (File f) {
Liste b = f.debut.suivant;
return b.contenu;
}

static void ajouter (int x, File f) {
Liste a = new Liste (x, null);
f.fin.suivant = a;
f.fin = a;
}

static void supprimer (File f) {
if (estVide (f))
erreur ("File Vide.");
f.debut = f.debut.suivant;
}
}

Figure 3.4 : File d'attente implémentée par une liste

Nous avons deux réalisations possibles des files avec des tableaux ou des listes chaînées. L'écriture de programmes consiste à faire de tels choix pour représenter les structures de données. L'ensemble des fonctions sur les files peut être indistinctement un module manipulant des tableaux ou un module manipulant des listes. L'utilisation des files se fait uniquement à travers les fonctions vide, ajouter, valeur, supprimer. C'est donc l'interface des files qui importe dans de plus gros programmes, et non leurs réalisations. Les notions d'interface et de modules seront développées au chapitre 7.


3.3 Piles

La notion de pile intervient couramment en programmation, son rôle principal consiste à implémenter les appels de procédures. Nous n'entrerons pas dans ce sujet, plutôt technique, dans ce chapitre. Nous montrerons le fonctionnement d'une pile à l'aide d'exemples choisis dans l'évaluation d'expressions Lisp.


On peut imaginer une pile comme une boîte dans laquelle on place des objets et de laquelle on les retire dans un ordre inverse de celui dans lequel on les a mis: les objets sont les uns sur les autres dans la boîte et on ne peut accéder qu'à l'objet situé au ``sommet de la pile''. De façon plus formelle, on se donne un ensemble E, l'ensemble des piles dont les éléments sont dans E est noté Pil(E), la pile vide (qui ne contient aucun élément) est P₀, les opérations sur les piles sont vide, ajouter, valeur, supprimer comme sur les files. Cette fois, les relations satisfaites sont les suivantes (où P₀ dénote la pile vide)

supprimer(ajouter(x,P)) = P

estVide(ajouter(x,P)) = faux

valeur(ajouter(x,P)) = x

estVide(P0) = vrai

A l'aide de ces relations, on peut exprimer toute expression sur les piles faisant intervenir les 4 opérations précédentes à l'aide de la seule opération ajouter en partant de la pile P₀. Ainsi l'expression suivante concerne les piles sur l'ensemble des nombres entiers:

	supprimer (ajouter (	7 ,
		supprimer (	ajouter (	valeur (ajouter (5, ajouter (3, P0)))),
				ajouter (9, P0))))

Elle peut se simplifier en:

ajouter (9, P0)

La réalisation des opérations sur les piles peut s'effectuer en utilisant un tableau qui contient les éléments et un indice qui indiquera la position du sommet de la pile. par référence.

class Pile {

final static int maxP = 100;

int hauteur ;
Element contenu[];

Pile () {
hauteur = 0;
contenu = new Element[maxP];
}

static File vide () {
return new Pile();
}

static void faireVide (Pile p) {
p.hauteur = 0;
}

static boolean estVide (Pile p) {
return p.hauteur == 0;
}

static boolean estPleine (Pile p) {
return p.hauteur == maxP;
}

static void ajouter (Element x, Pile p)
throws ExceptionPile
{
if (estPleine (p))
throw new ExceptionPile("pleine");
p.contenu[p.hauteur] = x;
++ p.hauteur;
}

static Element valeur (Pile p)
throws ExceptionPile
{
if (estVide (p))
throw new ExceptionPile("vide");
return p.contenu [p.hauteur - 1];
}

static void supprimer (Pile p)
throws ExceptionPile
{
if (estVide (p))
throw new ExceptionPile ("vide");
-- p.hauteur;
}
}
où on suppose qu'une nouvelle classe définit les exceptions ExceptionPile:

class ExceptionPile extends Exception {
String nom;

public ExceptionPile (String x) {
nom = x;
}
}