在 C++ 中使用連結串列實現佇列資料結構

Jinku Hu 2021年10月2日
在 C++ 中使用連結串列實現佇列資料結構

本文將解釋如何使用 C++ 中的連結串列實現佇列資料結構。

在 C++ 中使用單向連結串列實現佇列資料結構

佇列是一種以 FIFO(先進先出)方式管理其元素的資料結構,因此新增的第一個元素將首先從佇列中刪除。

通常,佇列資料結構的插入和移除操作分別稱為入隊和出隊。抽象佇列可以使用不同的方法和資料結構來實現。通常,新增新元素的一側稱為前端,而刪除元素的一側稱為佇列的後端。

在下面的例子中,我們使用單向連結串列來實現佇列,它由儲存資料物件的節點和指向下一個節點的指標組成。在這種情況下,為了簡單起見,我們選擇用單個字串物件來表示資料物件,但由程式設計師來設計最佳節點結構。

接下來,我們可以定義一個名為 Queueclass,它包括三個資料成員:frontbacksize。前兩個是不言自明的,而後一個表示佇列的當前元素計數。佇列資料結構可以有無界和有界兩種主要變體,前者可以新增元素,直到有可用記憶體。另一方面,有界佇列旨在僅儲存固定數量的元素。

在本文中,我們設計了一個無界佇列,但讀者可以在給定的程式碼示例中稍作修改,直觀地開發出有界佇列。由於我們是從頭開始實現一個無界佇列,我們​​需要隨著佇列的增長來管理動態記憶體分配。因此,enQueuedeQueue 成員函式將包括 newdelete 運算子。請注意,佇列的這種實現並不旨在成為一種高效的實現,而是總體上演示了該資料結構的基本工作機制。

我們的 Queue 有兩個建構函式,其中一個接受 string 值的 initializer_list 並多次呼叫 enQueue 函式來構造一個 Queue 物件。每個 enQueue 呼叫都會增加 size 成員,如果需要,類的使用者可以使用 getSize 函式檢索其值。我們還實現了一個輔助函式 printNodes 來檢查給定 Queue 物件的內容。這個函式不需要在實際場景中定義,但它對於測試和除錯很有用。

#include <iostream>
#include <string>

using std::cout; using std::cin;
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::cout; using std::cin;
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
Author: Jinku Hu
Jinku Hu avatar Jinku Hu avatar

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

相關文章 - C++ Data Structure