《栈和队列》课程中的第四讲主要讲解了链队的概念和实现，链队是一种使用链表作为存储结构的队列。在链队中，队列的逻辑结构表现为线性序列，而存储结构则采用单链表的形式。下面将详细阐述链队的存储结构、基本运算的实现以及相关算法。
链队的存储结构由两部分组成：存储队列元素的单链表节点和分别指向队头和队尾的指针。为了简化结构，这里采用不带头节点的单链表，队头和队尾通过指针进行标记。队头指针`qfront`指向队列的第一个元素，队尾指针`qrear`指向队列的最后一个元素。
在链队中，有四个基本的运算操作：
1. 初始化队列(InitQueue)：这个操作用于构建一个空队列，仅创建一个链队头节点，其`front`和`rear`域均置为`NULL`，不创建数据元素节点。具体的C++实现如下：
```cpp
void InitQueue(LiQueue *&q) {
q = (LiQueue *)malloc(sizeof(LiQueue));
q->front = q->rear = NULL;
}
```
2. 销毁队列(DestroyQueue)：此操作释放队列占用的所有存储空间，包括链队头节点和所有数据节点。代码实现如下：
```cpp
void DestroyQueue(LiQueue *&q) {
QNode *p = q->front, *r;
if (p != NULL) { // p指向队头数据节点
r = p->next;
while (r != NULL) {
free(p);
p = r;
r = p->next;
}
}
free(p); // 释放链队头节点
free(q);
}
```
3. 判断队列是否为空(QueueEmpty)：通过检查`rear`指针是否为`NULL`来判断队列是否为空，如果为`NULL`则返回`true`，否则返回`false`。
```cpp
bool QueueEmpty(LiQueue *q) {
return (q->rear == NULL);
}
```
4. 进队(enQueue)：将元素`e`插入队列尾部。如果原队列为空，则新节点既是队首也是队尾；否则，将新节点链接到队尾，并更新`rear`指针。
```cpp
void enQueue(LiQueue *&q, ElemType e) {
QNode *p;
p = (QNode *)malloc(sizeof(QNode));
p->data = e;
p->next = NULL;
if (q->rear == NULL) // 若链队为空
q->front = q->rear = p;
else {
q->rear->next = p; // 将*p节点链到队尾，并将rear指向它
q->rear = p;
}
}
```
5. 出队(deQueue)：从队列头部删除并返回元素。如果队列为空，返回`false`；如果队列只有一个节点，删除该节点后队列变为空；否则，删除队首节点并返回`true`。
```cpp
bool deQueue(LiQueue *&q, ElemType &e) {
QNode *t;
if (q->rear == NULL)
return false;
t = q->front;
if (q->front == q->rear) {
q->front = q->rear = NULL;
} else {
q->front = q->front->next;
}
e = t->data;
free(t);
return true;
}
```
此外，对于采用循环单链表存储的链队，可以利用尾指针`rear`唯一标识队列。在这种情况下，队列的初始化、进队和出队操作略有不同。初始化时，只需将`rear`设为`NULL`；判断队列是否为空依然检查`rear`是否为`NULL`；进队操作是在链表末尾插入节点；而出队操作则是删除链表的第一个节点。
总结来说，链队是一种灵活的队列实现方式，尤其适用于动态变化的队列大小。通过链表的特性，可以方便地实现队列的插入和删除操作，而不需要预先知道队列的大小。在实际应用中，链队常被用于处理需要先进先出(FIFO)规则的数据流，如操作系统中的进程调度、数据缓冲区管理等场景。
