Introduction à std::queue
std::queue est une structure de données essentielle en C++ qui permet de gérer des éléments selon le principe FIFO (First-In-First-Out). Cela signifie que le premier élément inséré sera le premier à être retiré.
Elle est incluse dans la bibliothèque <queue> et repose sur un conteneur sous-jacent, généralement std::deque. Cette structure est particulièrement utile pour des cas comme le traitement en file d’attente, les algorithmes de parcours en largeur (BFS), ou encore la gestion de flux de données.
Qu'est-ce que std::queue en C++ ?
std::queue est une classe de la bibliothèque standard C++ qui représente une file d’attente. Elle permet de stocker des éléments de manière séquentielle et de les traiter dans l’ordre où ils ont été ajoutés. C’est une abstraction idéale pour les scénarios où l’ordre d’arrivée des éléments doit être respecté.
Méthodes de base à la classe queue en C++ :
Voici les principales fonctions de std::queue que vous devez connaître :
push()— Ajouter un élément à la fin de la file.pop()— Retirer l’élément en tête de la file.front()— Accéder à l’élément en tête de la file.back()— Accéder à l’élément en fin de la file.empty()— Vérifier si la file est vide.size()— Obtenir le nombre d’éléments dans la file.
Comment ajouter à une file d’attente en C++ ?
Pour ajouter un élément à une file d’attente, utilisez la méthode push(). Elle insère l’élément à la fin de la file.
Exemple :
#include <queue>
#include <iostream>
int main() {
std::queue<int> q;
q.push(10); // Ajouter un élément
q.push(20); // Ajouter un autre élément
std::cout << "Front: " << q.front() << ", Back: " << q.back() << std::endl;
return 0;
}À quoi sert la fonction queue pop en C++ ?
La méthode pop() est utilisée pour retirer l’élément en tête de la file. Cela permet de traiter les éléments dans l’ordre où ils ont été ajoutés.
Exemple :
#include <queue>
#include <iostream>
int main() {
std::queue<int> q;
q.push(10);
q.push(20);
std::cout << "Front avant pop: " << q.front() << std::endl;
q.pop(); // Retirer l’élément en tête
std::cout << "Front après pop: " << q.front() << std::endl;
return 0;
}Exemple d'utilisation de la méthode push sur la classe queue en C++
La méthode push() permet d’ajouter un élément à la fin de la file.
Exemple :
#include <queue>
#include <iostream>
int main() {
std::queue<int> q;
q.push(5);
q.push(15);
q.push(25);
std::cout << "Front: " << q.front() << ", Back: " << q.back() << std::endl;
return 0;
}Exemple d'utilisation de la méthode front sur la classe queue en C++
La méthode front() permet d’accéder à l’élément en tête de la file sans le retirer.
Exemple :
#include <queue>
#include <iostream>
int main() {
std::queue<int> q;
q.push(10);
q.push(20);
std::cout << "L'élément en tête est: " << q.front() << std::endl;
return 0;
}Exemple d'utilisation de la méthode back sur la classe queue en C++
La méthode back() permet d’accéder à l’élément en fin de la file.
Exemple :
#include <queue>
#include <iostream>
int main() {
std::queue<int> q;
q.push(10);
q.push(20);
std::cout << "L'élément en fin est: " << q.back() << std::endl;
return 0;
}Exemple d'utilisation de la méthode empty sur la classe queue en C++
La méthode empty() permet de vérifier si la file est vide.
Exemple :
#include <queue>
#include <iostream>
int main() {
std::queue<int> q;
std::cout << "La file est-elle vide ? " << (q.empty() ? "Oui" : "Non") << std::endl;
q.push(10);
std::cout << "La file est-elle vide ? " << (q.empty() ? "Oui" : "Non") << std::endl;
return 0;
}Exemple d'utilisation de la méthode size sur la classe queue en C++
La méthode size() permet d’obtenir le nombre d’éléments dans la file.
Exemple :
#include <queue>
#include <iostream>
int main() {
std::queue<int> q;
q.push(10);
q.push(20);
q.push(30);
std::cout << "La taille de la file est: " << q.size() << std::endl;
return 0;
}Comment vérifier si une file d’attente est vide en C++ ?
Pour vérifier si une file est vide, utilisez la méthode empty(). Elle retourne true si la file est vide, sinon false.
Exemple :
#include <queue>
#include <iostream>
int main() {
std::queue<int> q;
std::cout << "Queue vide ? " << (q.empty() ? "Oui" : "Non") << std::endl;
q.push(10);
std::cout << "Queue vide ? " << (q.empty() ? "Oui" : "Non") << std::endl;
return 0;
}Exemple complet
Un programme C++ minimal illustrant :
- Création d’une queue
- Insertion et suppression
- Parcours de la queue
#include <iostream>
#include <queue>
int main() {
std::queue<int> q;
q.push(10);
q.push(20);
q.push(30);
std::cout << "Front: " << q.front() << std::endl;
q.pop();
std::cout << "New Front: " << q.front() << std::endl;
return 0;
}Queue Implementation in C++
Bien que std::queue soit une abstraction prête à l’emploi, il est utile de comprendre comment elle est implémentée. std::queue repose sur un conteneur sous-jacent, comme std::deque (par défaut) ou std::list. Vous pouvez également personnaliser le conteneur sous-jacent en le spécifiant lors de la déclaration.
Exemple d’implémentation personnalisée :
#include <iostream>
#include <queue>
#include <list>
int main() {
// Utilisation de std::list comme conteneur sous-jacent
std::queue<int, std::list<int>> customQueue;
customQueue.push(10);
customQueue.push(20);
std::cout << "Front: " << customQueue.front() << ", Back: " << customQueue.back() << std::endl;
return 0;
}Si vous souhaitez implémenter une queue manuellement, vous pouvez utiliser un conteneur comme std::deque ou std::list et définir les opérations push, pop, front, et back.
Exemple d’implémentation manuelle :
#include <iostream>
#include <deque>
class CustomQueue {
private:
std::deque<int> data;
public:
void push(int value) {
data.push_back(value);
}
void pop() {
if (!data.empty()) {
data.pop_front();
}
}
int front() const {
return data.front();
}
int back() const {
return data.back();
}
bool empty() const {
return data.empty();
}
size_t size() const {
return data.size();
}
};
int main() {
CustomQueue q;
q.push(10);
q.push(20);
std::cout << "Front: " << q.front() << ", Back: " << q.back() << std::endl;
q.pop();
std::cout << "Front after pop: " << q.front() << std::endl;
return 0;
}Comment vider une file d’attente en C++ ?
La méthode clear() n’existe pas pour std::queue. Pour vider une file, vous devez retirer manuellement tous les éléments en utilisant des appels successifs à pop().
Exemple :
#include <queue>
#include <iostream>
int main() {
std::queue<int> q;
q.push(10);
q.push(20);
q.push(30);
std::cout << "Taille avant clear: " << q.size() << std::endl;
// Vider la file
while (!q.empty()) {
q.pop();
}
std::cout << "Taille après clear: " << q.size() << std::endl;
return 0;
}Cette approche garantit que tous les éléments sont retirés de la file, laissant celle-ci vide.
Cas d’usage classique
- Systèmes de gestion de file d’attente (impression, tâches)
- Parcours en largeur (BFS) dans les graphes
- Traitement de flux de données
Bonnes pratiques
- Toujours vérifier avec
empty()avant d’accéder àfront()oupop(). - Éviter l’utilisation de
queuesi un accès aléatoire est nécessaire. - Privilégier
emplace()si vous voulez construire un objet directement dans la file (C++11+).
Quiz : Testez vos connaissances
- Quelle méthode permet d'accéder à l’élément en fin de file ?
- Que se passe-t-il si on appelle
pop()sur une file vide ? - Quel est le conteneur sous-jacent par défaut dans
std::queue? - La file suit-elle un comportement FIFO ou LIFO ?
- Quelle est la sortie du code suivant :
std::queue<int> q;
q.push(1); q.push(2); q.pop(); std::cout << q.front();Réponses au quiz
back()- Comportement indéfini — à éviter
std::deque- FIFO
2
Conclusion
std::queue est une structure simple mais puissante pour gérer des flux FIFO. Elle est idéale pour des applications variées allant des algorithmes aux systèmes de gestion de tâches.
Prochaine étape : explorer les queues concurrentes ou les priority_queue.