Implémenter une structure de données de file d'attente à l'aide d'une liste chaînée en C++
Cet article explique comment implémenter une structure de données de file d’attente à l’aide d’une liste chaînée en C++.
Implémenter une structure de données de file d’attente à l’aide d’une liste à liaison unique en C++
Une file d’attente est une structure de données qui gère ses éléments de manière FIFO (premier entré, premier sorti), donc le premier élément ajouté sera le premier à être retiré de la file d’attente.
Généralement, les opérations d’insertion et de suppression de la structure de données de file d’attente sont appelées respectivement mise en file d’attente et sortie de file d’attente. Une file d’attente abstraite peut être implémentée en utilisant différentes méthodes et structures de données. Habituellement, le côté où les nouveaux éléments sont ajoutés est appelé - front, tandis que le côté dont les éléments sont supprimés - un arrière de la file d’attente.
Dans les exemples suivants, nous implémentons la file d’attente à l’aide de la liste à chaînage simple, qui se compose de nœuds stockant l’objet de données et le pointeur vers le nœud suivant. Dans ce cas, nous avons choisi de représenter un objet de données avec un seul objet string pour plus de simplicité, mais c’est au programmeur de concevoir la structure de nœuds la plus optimale.
Ensuite, nous pouvons définir une classe appelée Queue, qui comprend trois données membres : front, back et size. Les deux premiers sont explicites, tandis que le dernier indique le nombre d’éléments actuel de la file d’attente. Il peut y avoir deux variantes principales de la structure de données de file d’attente illimitée et limitée, la première pouvant ajouter des éléments jusqu’à ce qu’il y ait de la mémoire disponible. D’autre part, une file d’attente limitée est conçue pour ne stocker qu’un nombre fixe d’éléments.
Dans cet article, nous concevons une file d’attente illimitée, mais le lecteur peut développer intuitivement la file d’attente délimitée avec de petites modifications dans les exemples de code donnés. Étant donné que nous implémentons une file d’attente illimitée à partir de zéro, nous devons gérer les allocations de mémoire dynamiques à mesure que la file d’attente augmente. Ainsi, les fonctions membres enQueue et deQueue incluront les opérateurs new et delete. Notez que cette implémentation de la file d’attente n’est pas destinée à être efficace mais démontre plutôt les mécanismes de fonctionnement de base de cette structure de données en général.
Notre Queue a deux constructeurs, dont l’un prend initializer_list de valeurs chaîne et invoque plusieurs fois la fonction enQueue pour construire un objet Queue. Chaque invocation enQueue incrémente le membre size, et si besoin, l’utilisateur de la classe peut récupérer sa valeur à l’aide de la fonction getSize. Nous avons également implémenté une fonction d’assistance printNodes pour inspecter le contenu de l’objet Queue donné. Cette fonction n’a pas besoin d’être définie dans un scénario du monde réel, mais elle peut être utile pour les tests et le débogage.
#include <iostream>
#include <string>
using std::cin;
using std::cout;
using std::endl;
using std::string;
struct ListNode {
struct ListNode *next = nullptr;
string data;
} typedef ListNode;
class Queue {
public:
explicit Queue() {
back = front = nullptr;
size = 0;
};
Queue(std::initializer_list<string> list);
ListNode *enQueue(string data);
string deQueue();
void printNodes();
size_t getSize() const;
~Queue();
private:
ListNode *front;
ListNode *back;
size_t size;
};
Queue::Queue(std::initializer_list<string> list) {
front = back = nullptr;
size = 0;
for (const auto &item : list) {
enQueue(item);
}
}
ListNode *Queue::enQueue(string data) {
auto new_node = new ListNode;
new_node->data = std::move(data);
new_node->next = nullptr;
if (front == nullptr) {
front = back = new_node;
size++;
return new_node;
}
back->next = new_node;
back = back->next;
size++;
return new_node;
}
void Queue::printNodes() {
auto count = 0;
auto tmp = front;
while (tmp) {
cout << "node " << count << " - data: " << tmp->data << endl;
tmp = tmp->next;
count++;
}
}
size_t Queue::getSize() const { return size; }
int main() {
Queue q1 = {"Precise", "Quantal", "Saucy", "Raring"};
q1.printNodes();
cout << "queue size = " << q1.getSize() << endl;
cout << "/ ------------------------------ / " << endl;
q1.enQueue("Xenial");
q1.enQueue("Bionic");
q1.printNodes();
cout << "queue size = " << q1.getSize() << endl;
return EXIT_SUCCESS;
}
Production:
node 0 - data: Precise
node 1 - data: Quantal
node 2 - data: Saucy
node 3 - data: Raring
queue size = 4
/ ------------------------------ /
node 0 - data: Precise
node 1 - data: Quantal
node 2 - data: Saucy
node 3 - data: Raring
node 4 - data: Xenial
node 5 - data: Bionic
queue size = 6
La classe Queue précédente n’a pas l’implémentation du destructeur et la fonction pour supprimer des éléments de la file d’attente. Ces deux éléments sont définis dans l’extrait de code suivant, et le code du pilote correspondant est inclus dans la fonction main du programme.
La fonction deQueue est conçue pour renvoyer une valeur string spécifique à notre implémentation. Par conséquent, cette fonction renvoie une chaîne vide pour indiquer que la file d’attente est vide, et l’utilisateur est responsable de vérifier la valeur de retour. Pendant ce temps, la fonction destructeur s’assure que toute la mémoire allouée est libérée avant que l’objet ne soit hors de portée.
#include <iostream>
#include <string>
using std::cin;
using std::cout;
using std::endl;
using std::string;
struct ListNode {
struct ListNode *next = nullptr;
string data;
} typedef ListNode;
class Queue {
public:
explicit Queue() {
back = front = nullptr;
size = 0;
};
Queue(std::initializer_list<string> list);
ListNode *enQueue(string data);
string deQueue();
void printNodes();
size_t getSize() const;
~Queue();
private:
ListNode *front;
ListNode *back;
size_t size;
};
Queue::Queue(std::initializer_list<string> list) {
front = back = nullptr;
size = 0;
for (const auto &item : list) {
enQueue(item);
}
}
ListNode *Queue::enQueue(string data) {
auto new_node = new ListNode;
new_node->data = std::move(data);
new_node->next = nullptr;
if (front == nullptr) {
front = back = new_node;
size++;
return new_node;
}
back->next = new_node;
back = back->next;
size++;
return new_node;
}
string Queue::deQueue() {
if (front == nullptr)
return "";
else {
auto tmp = front->next;
auto data = front->data;
delete front;
front = tmp;
size--;
return data;
}
}
Queue::~Queue() {
struct ListNode *tmp = nullptr;
while (front) {
tmp = front->next;
delete front;
front = tmp;
}
}
void Queue::printNodes() {
auto count = 0;
auto tmp = front;
while (tmp) {
cout << "node " << count << " - data: " << tmp->data << endl;
tmp = tmp->next;
count++;
}
}
size_t Queue::getSize() const { return size; }
int main() {
Queue q1 = {"Precise", "Quantal", "Saucy", "Raring"};
auto ret = q1.deQueue();
if (!ret.empty())
cout << ret << endl;
else
cout << "Queue is empty!" << endl;
cout << "queue size = " << q1.getSize() << endl;
cout << "/ ------------------------------ / " << endl;
while (!q1.deQueue().empty())
;
cout << "queue size = " << q1.getSize() << endl;
ret = q1.deQueue();
if (!ret.empty())
cout << ret << endl;
else
cout << "Queue is empty!" << endl;
for (int i = 0; i < 100; ++i) {
q1.enQueue("hello");
}
q1.printNodes();
cout << "queue size = " << q1.getSize() << endl;
return EXIT_SUCCESS;
}
Precise
queue size = 3
/ ------------------------------ /
queue size = 0
Queue is empty!
queue size = 100
Founder of DelftStack.com. Jinku has worked in the robotics and automotive industries for over 8 years. He sharpened his coding skills when he needed to do the automatic testing, data collection from remote servers and report creation from the endurance test. He is from an electrical/electronics engineering background but has expanded his interest to embedded electronics, embedded programming and front-/back-end programming.
LinkedIn Facebook