Implementieren einer Warteschlangendatenstruktur mit verknüpfter Liste in C++
In diesem Artikel wird erläutert, wie Sie eine Warteschlangendatenstruktur mithilfe einer verknüpften Liste in C++ implementieren.
Implementieren Sie die Warteschlangendatenstruktur mithilfe einer einfach verketteten Liste in C++
Eine Warteschlange ist eine Datenstruktur, die ihre Elemente im FIFO-Verfahren (First-In-First-Out) verwaltet, sodass das zuerst hinzugefügte Element als erstes aus der Warteschlange entfernt wird.
Im Allgemeinen werden die Einfüge- und Entfernungsoperationen für die Warteschlangendatenstruktur als Einreihen bzw. Ausreihen bezeichnet. Eine abstrakte Warteschlange kann mit verschiedenen Methoden und Datenstrukturen implementiert werden. Normalerweise wird die Seite, auf der neue Elemente hinzugefügt werden, als front bezeichnet, während die Seite, von der die Elemente entfernt werden, als eine Rückseite der Warteschlange bezeichnet wird.
In den folgenden Beispielen implementieren wir die Warteschlange mithilfe der einfach verketteten Liste, die aus Knoten besteht, die das Datenobjekt und den Zeiger auf den nächsten Knoten speichern. In diesem Fall haben wir uns der Einfachheit halber dafür entschieden, ein Datenobjekt mit einem einzigen string-Objekt darzustellen, aber es liegt am Programmierer, die optimale Knotenstruktur zu entwerfen.
Als nächstes können wir eine Klasse namens Queue definieren, die drei Datenelemente enthält: front, back und size. Die ersten beiden sind selbsterklärend, während letztere die aktuelle Elementanzahl der Warteschlange bezeichnet. Es kann zwei Hauptvarianten der Warteschlangen-Datenstruktur unbegrenzt und begrenzt geben, von denen die erstere Elemente hinzufügen kann, bis Speicher verfügbar ist. Andererseits ist eine begrenzte Warteschlange dafür ausgelegt, nur eine feste Anzahl von Elementen zu speichern.
In diesem Artikel entwerfen wir eine unbegrenzte Warteschlange, aber der Leser kann die begrenzte Warteschlange mit kleinen Modifikationen in den gegebenen Codebeispielen intuitiv entwickeln. Da wir eine unbegrenzte Warteschlange von Grund auf neu implementieren, müssen wir die dynamischen Speicherzuweisungen verwalten, wenn die Warteschlange wächst. Daher enthalten die Memberfunktionen enQueue und deQueue die Operatoren new und delete. Beachten Sie, dass diese Implementierung der Warteschlange keine effiziente sein soll, sondern die grundlegenden Arbeitsmechanismen dieser Datenstruktur im Allgemeinen demonstriert.
Unsere Queue hat zwei Konstruktoren, von denen einer initializer_list von string-Werten nimmt und die Funktion enQueue mehrmals aufruft, um ein Queue-Objekt zu konstruieren. Jeder Aufruf von enQueue erhöht das Member size, und bei Bedarf kann der Benutzer der Klasse seinen Wert mit der Funktion getSize abrufen. Wir haben auch eine Hilfsfunktion printNodes implementiert, um den Inhalt des angegebenen Queue-Objekts zu überprüfen. Diese Funktion muss in einem realen Szenario nicht definiert werden, kann aber zum Testen und Debuggen nützlich sein.
#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;
}
Ausgabe:
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
Der vorherigen Klasse Queue fehlt die Destruktor-Implementierung und die Funktion zum Entfernen von Elementen aus der Warteschlange. Diese beiden sind im folgenden Code-Schnipsel definiert und der entsprechende Treibercode ist in der Funktion main des Programms enthalten.
Die Funktion deQueue ist so konzipiert, dass sie einen für unsere Implementierung spezifischen string-Wert zurückgibt. Folglich gibt diese Funktion eine leere Zeichenkette zurück, um anzuzeigen, dass die Warteschlange leer ist, und der Benutzer ist dafür verantwortlich, den Rückgabewert zu überprüfen. In der Zwischenzeit stellt die Destruktorfunktion sicher, dass der gesamte zugewiesene Speicher freigegeben wird, bevor das Objekt den Gültigkeitsbereich verlässt.
#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