在 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
