关于队列的介绍,在前面一篇 循环队列 已经说过。我们来看看第二种队列——链队列。 物理结构为链式存储结构的队列，对内存空间的利用率更高。
链式队列的表示
image
是不是似曾相识的结构？链栈，再看看链栈的表示
image
区别：
栈，新的元素添加在栈顶，而且栈顶先出；
队列，队尾进，队首出。
二者相反
所以，我们链队列的操作简单来说就是：
- 进入队列 ：Q.rear尾节点后追加新节点，将Q.rear指向新节点，新节点成队尾；
- 出队列 ：Q.front指向的首元节点出队列，Q.front指向首元节点的下一个节点
老规矩先定义数据结构
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OK 1
typedef int Status;/* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int ElemType;/* ElemType类型根据实际情况而定，这里假设为int */
typedef struct QueueNode {
ElemType data;
struct QueueNode *next;
} QueueNode, *QueueNodePtr;
typedef struct {
QueueNodePtr front;
QueueNodePtr rear;
} LinkQueue;
初始化
先创建一个头节点，让Q.front和Q.rear指向头节点，头节点的next为NULL
image
/// 初始化
Status InitQueue(LinkQueue *Q)
{
// 初始队列为空,只有头节点，不是有效数据的节点
*Q->front = *Q->rear = (QueueNodePtr)malloc(sizeof(QueueNode));
if (*Q->front == NULL) return ERROR;
// 头节点的后面为空
*Q->front->next = NULL;
return OK;
}
判断队列为空
当队列为空时，恰入上图初始化的状态，只剩一个头节点，此时 Q.front == Q.rear
/// 判断是否为空
Status QueueEmpty(LinkQueue Q)
{
if (Q.front == Q.rear) return TRUE;
return FALSE;
}
进入队列
进入队列的操作，是将新元素，追加到rear指向的队尾之后，rear->next = 新元素，再将rear指向新元素，此时，新元素成为队尾。因为不受存储空间限制（内存占满另说），所以不需要一开始就判断是否队满，也没有队满的操作。
- 创建新节点p
- 追加到队尾
- 队列的rear指向p，标记成新队尾
image
Status EnQueue(LinkQueue *Q, ElemType e)
{
QueueNodePtr p = (QueueNodePtr)malloc(sizeof(QueueNode));
if (p == NULL) return ERROR;
p->data = e;
p->next = NULL;
// 追加到队尾
*Q->rear->next = p;
// 标记成队尾
*Q->rear = p;
return OK;
}
出队列
出队列操作，是将首元节点从链队删除。
- 判断队列是否为空
- 找到队首节点head（此时已拿到节点，将该节点的data回调出去），等待删除
- 更改标记head后面的节点s为首元节点，即head->next
- 判断是否是最后一个节点，是的话，rear也指向头节点
- 释放原首节点head
image
Status DeQueue(LinkQueue *Q, ElemType *e)
{
if (QueueEmpty(*Q)) return ERROR;
QueueNodePtr head;
// 找到要删除的节点
head = *Q->front->next;
// 回调到函数外
*e = head->data;
// 更改头节点
*Q->front->next = head->next;
// 如果删到了队尾最后一个元素
if (*Q->rear == head)
*Q->rear = *Q->front;
// 删除临时指针指向的头节点
free(head);
return OK;
}
清空
仅清空头节点以外的全部节点，有头节点在，清空完，还能继续EnQueue()操作。又回到初始化后的状态
image
/// 清空队列
Status ClearQueue(LinkQueue *Q)
{
if (*Q->front->next == NULL) return ERROR;
QueueNodePtr temp, p; // 首元节点
*Q->rear = *Q->front;
p = *Q->front->next;
*Q->front->next = NULL;
// 此时只有temp指向首元节点
while (p) {
temp = p;
p = p->next;
free(temp);
}
return OK;
}
销毁
销毁操作，和清空不一样，清空仅仅删除除头节点以外的所有节点，清空后还可以再入队。但是销毁已经彻底不使用，需要连头节点也一并free掉，所以代码中是从front开始，而非front->next。
已free所有的节点
image
/// 销毁队列
Status DestoryQueue(LinkQueue *Q)
{
if (*Q->front->next == NULL) return ERROR;
/*
说明，头节点也是个malloc开辟的，也需要释放
*/
while (*Q->front) {
*Q->rear = *Q->front->next;
free(*Q->front);
*Q->front = *Q->rear;
}
return OK;
}
获取队首
不更改队列，不破坏队列现有结构，仅查找。所以首元节的数据直接读取 Q.front->next->data，
Status GetHead(LinkQueue Q, ElemType *e)
{
if (QueueEmpty(*Q)) return ERROR;
*e = Q.front->next->data;
return OK;
}
