File d'attente en C++

La structure File d'attente (Queue)

Une file d'attente est une structure de données abstraite qui implémente le mécanisme FIFO (First In, First Out — premier entré, premier sorti) : l'élément inséré en premier est également supprimé en premier.

Comme la pile, une file peut être implémentée par un tableau (taille fixe) ou par une liste chaînée (taille dynamique). La figure ci-dessous illustre la structure interne d'une file chaînée avec ses deux pointeurs entete et queue.

Opérations de base

Implémentation directe

Enfiler un élément

L'insertion se fait toujours à la fin. Sans pointeur queue, il faudrait parcourir toute la liste — complexité O(n). En maintenant un pointeur queue vers le dernier nœud, l'opération devient O(1).

  Version naïve — O(n)

template <typename T>
void File<T>::enfiler(const T& valeur) {
    Noeud<T>* nouveau = CreerNoeud(valeur);
    if (compteur == 0) {
        entete = nouveau;
    } else {
        Noeud<T>* courant = entete;
        for (int i = 1; i < compteur; i++)
            courant = courant->suivant;
        courant->suivant = nouveau;
    }
    compteur++;
}

  Version optimisée avec pointeur queue — O(1)

template <typename T>
void File<T>::enfiler(const T& valeur) {
    Noeud<T>* nouveau = CreerNoeud(valeur);
    if (compteur == 0) {
        entete = queue = nouveau;   // 1er élément : tête et queue identiques
    } else {
        queue->suivant = nouveau;   // attacher après le dernier nœud
        queue = nouveau;            // avancer le pointeur queue
    }
    compteur++;
}

Défiler l'élément en tête

La suppression se fait en tête — même principe que pour la pile.

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--;
}

Fichiers complets — implémentation directe

#ifndef FILE_H
#define FILE_H

#include <iostream>
#include <cassert>
using namespace std;

template <typename T>
struct Noeud {
    T donnees;
    Noeud<T>* suivant;
};

template <typename T>
class File {
private:
    Noeud<T>* entete;
    Noeud<T>* queue;       // pointeur vers le dernier nœud
    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"

template <typename T>
File<T>::File() : entete(NULL), compteur(0) {}

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);
    if (compteur == 0) {
        entete = queue = nouveau;
    } else {
        queue->suivant = 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 { return (compteur == 0); }

template <typename T>
int File<T>::taille() const { return compteur; }

template <typename T>
void File<T>::afficher() const {
    if (compteur == 0) { cout << "La file est vide!" << endl; return; }
    Noeud<T>* courant = entete;
    while (courant != 0) {
        cout << courant->donnees << endl;
        courant = courant->suivant;
    }
}
#endif

Implémentation par composition (réutilisation de la classe Liste)

Comme pour la pile, on peut réutiliser la classe Liste par composition : la file contient une liste et délègue ses opérations en mappant insertion en queue (inserer(taille(), valeur)) et suppression en tête (supprimer(0)).

#ifndef FILE_H
#define FILE_H
#include "liste.cpp"
using namespace std;

template <typename T>
class File {
private:
    Liste<T> liste;   // composition : la file contient une 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);  // insertion en dernière position
}

template <typename T>
void File<T>::defiler() {
    liste.supprimer(0);                     // suppression en tête
}

template <typename T>
T& File<T>::premier() const {
    return liste.getNoeud(0);
}

template <typename T>
bool File<T>::estVide() const {
    return (liste.taille() == 0);
}

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() {
    File<string> file;

    file.enfiler("Mostafa");
    file.enfiler("Omar");
    file.enfiler("Sara");
    file.enfiler("Mohamed");
    file.enfiler("Moneim");
    file.enfiler("Dounia");
    file.enfiler("Abdelmalek");

    cout << "Afficher la file" << endl;
    file.afficher();
    cout << '\n';

    cout << "Afficher la tete de la file" << endl;
    cout << file.premier() << endl;
    cout << '\n';

    cout << "Supprimer quelques noeuds et afficher la file" << endl;
    file.defiler();
    file.defiler();
    file.afficher();
    cout << '\n';

    cout << "Afficher la tete de la file" << endl;
    cout << file.premier() << endl;
    cout << '\n';

    cout << "Nombre de noeuds dans la file : " << file.taille();
    return 0;
}

Afficher la file
Mostafa
Omar
Sara
Mohamed
Moneim
Dounia
Abdelmalek

Afficher la tete de la file
Mostafa

Supprimer quelques noeuds et afficher la file
Sara
Mohamed
Moneim
Dounia
Abdelmalek

Afficher la tete de la file
Sara

Nombre de noeuds dans la file : 5