在 C++ 中使用链表实现队列数据结构
Jinku Hu
2023年10月12日
本文将解释如何使用 C++ 中的链表实现队列数据结构。
在 C++ 中使用单向链表实现队列数据结构
队列是一种以 FIFO（先进先出）方式管理其元素的数据结构，因此添加的第一个元素将首先从队列中删除。
通常，队列数据结构的插入和移除操作分别称为入队和出队。抽象队列可以使用不同的方法和数据结构来实现。通常，添加新元素的一侧称为前端，而删除元素的一侧称为队列的后端。
在下面的例子中，我们使用单向链表来实现队列，它由存储数据对象的节点和指向下一个节点的指针组成。在这种情况下，为了简单起见，我们选择用单个字符串对象来表示数据对象，但由程序员来设计最佳节点结构。
接下来，我们可以定义一个名为 Queue 的 class，它包括三个数据成员：front、back 和 size。前两个是不言自明的，而后一个表示队列的当前元素计数。队列数据结构可以有无界和有界两种主要变体，前者可以添加元素，直到有可用内存。另一方面，有界队列旨在仅存储固定数量的元素。
在本文中，我们设计了一个无界队列，但读者可以在给定的代码示例中稍作修改，直观地开发出有界队列。由于我们是从头开始实现一个无界队列，我们需要随着队列的增长来管理动态内存分配。因此，enQueue 和 deQueue 成员函数将包括 new 和 delete 运算符。请注意，队列的这种实现并不旨在成为一种高效的实现，而是总体上演示了该数据结构的基本工作机制。
我们的 Queue 有两个构造函数，其中一个接受 string 值的 initializer_list 并多次调用 enQueue 函数来构造一个 Queue 对象。每个 enQueue 调用都会增加 size 成员，如果需要，类的用户可以使用 getSize 函数检索其值。我们还实现了一个辅助函数 printNodes 来检查给定 Queue 对象的内容。这个函数不需要在实际场景中定义，但它对于测试和调试很有用。
#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;
}
输出：
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
前面的 Queue 类缺少析构函数实现和从队列中删除元素的函数。这两个在下面的代码片段中定义，相应的驱动程序代码包含在程序的 main 函数中。
deQueue 函数旨在返回特定于我们的实现的 string 值。因此，该函数返回一个空字符串表示队列为空，用户负责检查返回值。同时，析构函数确保在对象超出范围之前释放所有分配的内存。
#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
作者： Jinku Hu
