数据结构链队列的实现

链队列是一种基于链表实现的队列，它的队头和队尾分别位于链表的头部和尾部。链队列的实现需要定义一个队列结构体，包含队头和队尾指针，以及链表节点结构体，包含数据域和指向下一个节点的指针。链队列的入队操作需要在队尾插入新节点，出队操作需要在队头删除节点。具体实现细节如下：

// 定义链表节点结构体
struct Node {
    int data;
    Node* next;
};

// 定义链队列结构体
struct Queue {
    Node* front; // 队头指针
    Node* rear; // 队尾指针
};

// 初始化链队列
void initQueue(Queue& q) {
    q.front = q.rear = new Node{0, nullptr}; // 创建一个空节点作为哨兵节点
}

// 判断链队列是否为空
bool isEmpty(Queue& q) {
    return q.front == q.rear;
}

// 入队操作
void enqueue(Queue& q, int x) {
    Node* newNode = new Node{x, nullptr}; // 创建新节点
    q.rear->next = newNode; // 将新节点插入队尾
    q.rear = newNode; // 更新队尾指针
}

// 出队操作
void dequeue(Queue& q) {
    if (isEmpty(q)) return; // 队列为空，直接返回
    Node* p = q.front->next; // 指向队头节点
    q.front->next = p->next; // 删除队头节点
    if (q.rear == p) q.rear = q.front; // 如果队列只有一个节点，更新队尾指针
    delete p; // 释放节点内存
}