C++代码实现链队列详解

什么是链队列？

链队列是一种基于链表实现的队列，它克服了顺序队列需要进行元素搬移的缺点，具有入队和出队均可以在O(1)时间内完成的优点。

链队列的数据结构

链队列的数据结构主要由节点结构体和队列结构体两部分组成。

节点结构体

节点结构体主要包括当前节点存储的数据和指向下一个节点的指针。

template <typename T>
struct Node{
    T data;
    Node<T>* next;
};

队列结构体

队列结构体主要包括队头和队尾节点以及队列中元素的数量。因为队列中只能从队尾插入元素，从队头删除元素，所以队头和队尾是比较重要的。

template <typename T>
struct Queue{
    Node<T>* front;
    Node<T>* rear;
    int size;
};

链队列的操作

链队列主要包括以下几个操作：入队、出队、判断队列是否为空、获取队列元素个数、打印队列元素。

入队操作

链队列入队操作实质上就是在队尾插入一个新节点，然后更新队列的rear指针和size大小。

template <typename T>
void enqueue(Queue<T>* q, T value){
    Node<T>* p = new Node<T>;
    p->data = value;
    p->next = nullptr;
    if (q->front == nullptr){
        q->front = q->rear = p;
    } else {
        q->rear->next = p;
        q->rear = p;
    }
    q->size++;
}

出队操作

链队列出队操作实质上就是删除队头节点，然后更新队列的front指针和size大小，并返回队头节点的值。

template <typename T>
T dequeue(Queue<T>* q){
    if (q->front == nullptr){
        throw "queue is empty";
    }
    Node<T>* p = q->front;
    T ret = p->data;
    q->front = p->next;
    if (q->front == nullptr){
        q->rear = nullptr;
    }
    delete p;
    q->size--;
    return ret;
}

判断队列是否为空操作

判断队列是否为空操作主要判断队列的front指针是否为空。

template <typename T>
bool is_empty(Queue<T>* q){
    return (q->front == nullptr);
}

获取队列元素个数操作

获取队列元素个数操作主要返回队列的size大小。

template <typename T>
int length(Queue<T>* q){
    return q->size;
}

打印队列元素操作

打印队列元素操作主要遍历队列中所有节点，然后输出节点中存储的数据。

template <typename T>
void print(Queue<T>* q){
    Node<T>* p = q->front;
    while (p != nullptr){
        std::cout << p->data << " ";
        p = p->next;
    }
    std::cout << std::endl;
}

链队列的示例说明

示例一

Queue<int>* q = new Queue<int>{nullptr, nullptr, 0};
enqueue(q, 1);
enqueue(q, 2);
enqueue(q, 3);
print(q);  // output: 1 2 3
std::cout << length(q) << std::endl;  // output: 3
std::cout << is_empty(q) << std::endl;  // output: 0
std::cout << dequeue(q) << std::endl;  // output: 1
print(q);  // output: 2 3
delete q;

示例二

Queue<std::string>* q = new Queue<std::string>{nullptr, nullptr, 0};
enqueue(q, "hello");
enqueue(q, "world");
enqueue(q, "!");
print(q);  // output: hello world !
std::cout << length(q) << std::endl;  // output: 3
std::cout << is_empty(q) << std::endl;  // output: 0
std::cout << dequeue(q) << std::endl;  // output: hello
print(q);  // output: world !
delete q;

总结

本文详细讲解了链队列的概念、数据结构和操作，并给出了代码实现和两个示例。希望读者可以通过本文更好地理解链队列的实现方式。