在 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