File d'attente en C++
Une file d'attente est une structure de données abstraite qui contient une collection d'éléments. La file d'attente implémente le mécanisme FIFO, c'est-à-dire que l'élément inséré en premier est également supprimé en premier. En d'autres termes, l'élément le moins récemment ajouté est supprimé en premier dans une file d'attente.
Une file de personnes attendant le bus dans une gare routière est une file d'attente ; une liste d'appels mis en attente pour être répondus par un opérateur téléphonique est une file d'attente, et une liste de travaux en attente d'être traités par un ordinateur est une file d'attente.
La figure ci-dessous montre deux représentations d'une file d'attente : l'une une file d'attente de personnes et l'autre une file d'attente d'éléments de données. Les personnes et les données entrent dans la file d'attente à l'arrière et progressent dans la file d'attente jusqu'à ce qu'elles arrivent à l'avant. Une fois qu'ils sont en tête de file, ils peuvent quitter la file d'attente.
Une file d'attente peut être implémentée sous forme de tableau ou de liste chaînée. Bien que l'implémentation du tableau soit plus simple, la taille du tableau doit être fixée au moment de la compilation. Une implémentation de liste chaînée permet à la taille de la file d'attente d'augmenter et de réduire dynamiquement. La figure ci-dessous montre comment nous implémentons une file d'attente en tant que liste chaînée.
Implémentation
L'implémentation de la file d’attente est assez similaire à l'implémentation de la liste chaînée, avec quelques petites modifications, Insertion à la fin et suppression de la tête.
La structure de données de la file d'attente comporte les opérations suivantes :
- Enfiler() : Ajoute un nouvel élément à la fin de la file d'attente.
- Défiler() : retire un élément du début de la file et retourne sa valeur.
- Premier() : retourne la valeur de l'élément au début de la file.
- Taille() : retourne le nombre d'éléments dans la file.
- estVide() : retourne 1 si la file est vide, sinon retourne 0.
Ajouter un nœud à la file
L'insertion est plus complexe, comme le montre la figure ci-dessous. Il faut avoir un pointeur courant et le déplacer vers le dernier nœud. Le nouveau nœud est inséré après le dernier nœud.
template <typename T>
void File <T> :: enfiler (const T& valeur)
{
Noeud <T>* nouveau = CreerNoeud (valeur);
// si la file est vide
// cet élément devient la tête de la file
if(compteur==0){
entete=nouveau;
}
else{//sinon
Noeud <T>* courant = entete;
// boucler jusqu'au dernier noeud
for (int i = 1; i < compteur; i++){
courant = courant -> suivant;
}
//attacher le nouveau noeud au dernier noeud
courant -> suivant = nouveau;
}
compteur++;
}
Cette opération a une complexité linéaire O(n), pour réduire la complexité en O(1), nous pouvons ajouter un nouveau pointeur queue à la définition de la file d'attente, puis l'insertion est plus simple.
template <typename T>
void File <T> :: enfiler (const T& valeur)
{
Noeud <T>* nouveau = CreerNoeud (valeur);
// si la file est vide
// cet élément devient la tête de la file
if(compteur==0){
entete=queue=nouveau;
}
else{
// ajouter le noeud apres le dernier noeud (queue)
queue->suivant=nouveau;
// mettre à jour le pointeur queue vers nouveau
queue=nouveau;
}
compteur++;
}
Supprimer un nœud
La suppression du premier noeud est très simple et peut être effectuée comme le montre la figure ci-dessous.
template <typename T>
void File <T> :: defiler (){
if (compteur == 0){
cout << "Erreur! La file est vide." << endl;
return;
}
Noeud <T>* del = entete;
entete = entete -> suivant;
delete del;
compteur--;
}
Les fichiers file.h & file.cpp
#ifndef FILE_H
#define FILE_H
#include <iostream>
#include <cassert>
using namespace std;
// Définition du noeud en tant que struct
template <typename T>
struct Noeud
{
T donnees;
Noeud <T>* suivant;
};
// Définition de la classe Liste
template <typename T>
class File
{
private:
Noeud <T>* entete;
Noeud <T>* queue;
int compteur;
Noeud <T>* CreerNoeud (const T& valeur);
public:
File ();
~File ();
void enfiler (const T& valeur);
void defiler ();
T& premier () const;
int taille () const;
bool estVide() const;
void afficher () const;
};
#endif
#ifndef FILE_CPP
#define FILE_CPP
#include "file.h"
// Constructeur
template <typename T>
File <T> :: File ():entete (NULL), compteur (0) {}
// Destructeur
template <typename T>
File <T> :: ~File ()
{
Noeud <T>* del = entete;
while (entete){
entete = entete -> suivant;
delete del;
del = entete;
}
}
template <typename T>
Noeud <T>* File <T> :: CreerNoeud (const T& valeur){
Noeud <T>* temp = new Noeud <T>;
temp -> donnees = valeur;
temp -> suivant = NULL;
return temp;
}
template <typename T>
void File <T> :: enfiler (const T& valeur)
{
Noeud <T>* nouveau = CreerNoeud (valeur);
// si la file est vide
// cet élément devient la tête de la file
if(compteur==0){
entete=queue=nouveau;
}
else{
// ajouter le noeud apres le dernier noeud (queue)
queue->suivant=nouveau;
// mettre à jour le pointeur queue vers nouveau
queue=nouveau;
}
compteur++;
}
template <typename T>
void File <T> :: defiler (){
if (compteur == 0){
cout << "Erreur! La file est vide." << endl;
return;
}
Noeud <T>* del = entete;
entete = entete -> suivant;
delete del;
compteur--;
}
template <typename T>
T& File <T> :: premier () const {
if (compteur == 0){
cout << "Erreur! La file est vide";
assert (false);
}
return entete -> donnees;
}
template <typename T>
bool File <T> :: estVide () const{
if (compteur == 0){return true;}
return false;
}
template <typename T>
int File <T> :: taille () const{
return compteur;
}
template <typename T>
void File <T> :: afficher () const {
if (compteur == 0){
cout << "La liste est vide!" << endl;
return;
}
Noeud <T>* courant = entete;
while (courant != 0){
cout << courant -> donnees << endl;
courant = courant -> suivant;
}
}
#endif
Implémentation en utilisant la classe Liste (liste chaînée)
Nous pourrions créer une nouvelle interface et un nouveau fichier d'implémentation pour notre classe File, mais il est plus efficace de réutiliser le code créé pour la classe Liste. Une classe File est une classe Liste spéciale avec des opérations limitées.
Un objet File compose un objet de Liste et n'utilise que des opérations limitées définies dans la classe Liste.
Veuillez visiter ce cours pour plus de détails sur la classe Liste
#ifndef FILE_H
#define FILE_H
#include "liste.cpp"
using namespace std;
// Définition de la classe File
template <typename T>
class File
{
private:
Liste <T> liste;
public:
void enfiler (const T& valeur);
void defiler ();
T& premier () const;
int taille () const;
bool estVide() const;
void afficher () const;
};
#endif
#ifndef FILE_CPP
#define FILE_CPP
#include "file.h"
template <typename T>
void File <T> :: enfiler (const T& valeur)
{
liste.inserer (liste.taille (), valeur);
}
template <typename T>
void File <T> :: defiler (){
liste.supprimer(0);
}
template <typename T>
T& File <T> :: premier () const {
return liste.getNoeud(0);
}
template <typename T>
bool File <T> :: estVide () const{
if (liste.taille() == 0){return true;}
return false;
}
template <typename T>
int File <T> :: taille () const{
return liste.taille();
}
template <typename T>
void File <T> :: afficher () const {
liste.afficher();
}
#endif
Programme principal
#include "file.cpp"
#include <string>
int main ( ){
// Instanciation d'une file
File <string> file;
// Insertion de six noeuds dans la file
file.enfiler ("Mostafa");
file.enfiler ("Omar");
file.enfiler ("Sara");
file.enfiler ("Mohamed");
file.enfiler ("Moneim");
file.enfiler ("Dounia");
file.enfiler ("Abdelmalek");
// Afficher les valeurs de noeuds
cout << "Afficher la file" << endl;
file.afficher ();
cout<<'\n';
// afficher les valeurs de trois noeuds
cout << "Afficher la tete de la file" << endl;
cout << file.premier () << endl;
cout<<'\n';
// Supprimer trois noeuds
cout << "Supprimer quelques noeuds et afficher la file d'attente" << endl ;
file.defiler ();
file.defiler ();
file.afficher ();
cout<<'\n';
cout << "Afficher la tete de la file d'attente" << endl;
cout << file.premier () << endl;
cout<<'\n';
// Afficher la taille apres la suppression
cout << "Nombre de noeuds dans la file d'attente : " << file.taille() ;
return 0;
}
