Comment un centre d'appel arrive-t-il à gérer un surplus de clients ? Imaginons que tous les opérateurs téléphoniques du centre sont actuellement occupés et que 42 autres clients appellent dans la minute qui suit. Comment savoir quel client prendre en premier une fois un opérateur libre ? Comment faire pour garder un ordre logique si un client raccroche finalement, ou si d'autres appellent à leur tour ? Il nous faut donc une structure de données souple, permettant de résoudre nos problèmes de file d'attente, et cette structure s'appelle justement : la file.
Une file (queue en anglais) est une structure de données de type FIFO (First In First Out, premier entré premier sorti). Elle fonctionne exactement comme une file d’attente dans un magasin :
Voici comment on pourrait représenter une file :
L’action d’ajouter un élément dans la file est appelée : enfiler (ou enqueue en anglais) :
L’action d’enlever un élément de la file est appelée : défiler (ou dequeue en anglais) :
Comme la fin de la file est située "à gauche", notre premier élément
pointera vers NULL pour indiquer le début de la file (et
non la fin comme pour une liste chaînée, ou une pile).
Pour représenter une file, on peut utiliser une liste chaînée car les tableaux ne sont pas du tout adaptés à ce genre de structure de données (soit on gaspille de la mémoire, soit on réalise plus d'opérations que nécessaires). Cependant, on peut encore améliorer l'implémentation de notre file, en utilisant une liste doublement chaînée. En effet, si l'on utilise une liste simplement chaînée, il faut parcourir la liste pour défiler un élément, alors qu'avec une liste doublement chaînée et deux pointeurs (un vers le début et un vers la fin), on peut enfiler et défiler en temps constant.
Des fonctions de base sont nécessaires afin de bien manipuler une file.
créerFile :
Initialiser les pointeurs de début et de fin à NULL
supprimerFile :
Pour chaque élément de la file
Supprimer l'élément actuel
enfiler (élément) :
Faire pointer l'élément suivant du nouvel élément vers la fin
Faire pointer l'élément précédent du nouvel élément vers NULL
Mettre à jour le pointeur de fin
défiler :
Sauvegarder les données de l'élément en début de file
Supprimer cet élément
Faire pointer l'élément suivant du nouveau premier élément vers NULL
Mettre à jour le pointeur de début
Retourner les données sauvegardées
estVide :
Si les deux pointeurs de début et de fin pointent vers NULL
Retourner vrai
Sinon
Retourner fauxSoit \(N\) le nombre d'éléments de la file.
créerFile : \(O(1)\)supprimerFile : \(O(N)\)enfiler : \(O(1)\)défiler : \(O(1)\)estVide : \(O(1)\)Une implémentation en C d’une file :
#include <stdio.h>
#include <stdlib.h>
typedef struct Noeud Noeud;
struct Noeud
{
int donnee;
Noeud *suivant;
Noeud *precedent;
};
typedef struct File File;
struct File
{
Noeud *debut;
Noeud *fin;
};
int estVide(File *file);
void creerFile(File *file)
{
file->debut = NULL;
file->fin = NULL;
}
void supprimerFile(File *file)
{
Noeud *iFile;
for(iFile = file->fin; iFile != NULL; ) {
Noeud *temp;
temp = iFile->suivant;
free(iFile);
iFile = temp;
}
}
void enfiler(File *file, int donnee)
{
Noeud *nouveau;
nouveau = malloc(sizeof(Noeud));
nouveau->suivant = file->fin;
nouveau->precedent = NULL;
nouveau->donnee = donnee;
if(estVide(file)) {
file->debut = file->fin = nouveau;
return;
}
else {
file->fin->precedent = nouveau;
file->fin = nouveau;
}
}
int defiler(File *file)
{
Noeud *temp;
int donnee;
temp = file->debut->precedent;
donnee = file->debut->donnee;
free(file->debut);
file->debut = temp;
file->debut->suivant = NULL;
return donnee;
}
int estVide(File *file)
{
if(file->debut == NULL && file->fin == NULL)
return 1;
else
return 0;
}
int main(void)
{
File file;
creerFile(&file);
enfiler(&file, 42);
// 42
enfiler(&file, 9);
// 9 42
int retour = defiler(&file);
// retour = 42
supprimerFile(&file);
return 0;
}Si vous programmez en C++, la STL (Standard Template Library) fournit une implémentation et des fonctions permettant de manipuler une file : http://www.cplusplus.com/reference/queue/queue/
Une file à priorité (priority queue en anglais), est sans doute la variante de la file la plus utilisée. On la retrouve notamment dans l'algorithme de Dijkstra pour trouver le plus court chemin entre deux nœuds d'un graphe pondéré positivement. Chaque élément se voit attribuer une clé, permettant d'organiser la file (d'où le nom de file à priorité). On peut ensuite rapidement récupérer l'élément avec la priorité la plus élevée.
On implémente une file à priorité grâce à un tas (max ou min en fonction des besoins), et si vous programmez en C++ la STL fournit aussi une implémentation : http://www.cplusplus.com/reference/queue/priority_queue/.
Notez qu'il ne faut pas confondre file à priorité et tas. En effet, même si les deux notions semblent exactement pareil en pratique, en théorie une file à priorité est un type de donnée abstrait, alors que le tas est une structure de données réelle et concrète.
La file permet donc d'implémenter un comportement de file d'attente, qui est pratique dans de nombreuses situations :