1.链队列

队列是一种线性结构，线性是指其在逻辑结构，上一节我们顺序存储实现队列，这次链式存储实现队列。与单链表的实现不同的是，只能在表头删除，表尾插入。

2.代码实现

2.1 带头结点

#include <stdio.h>
#include <stdlib.h>
typedef int ElemType;
typedef struct LinkNode {ElemType data;struct LinkNode* next;
}LinkNode;
typedef struct {LinkNode* front, * rear;//int size;//如果频繁使用队列长度的话，考虑增加变量size记录，否则每遍历的时间复杂度是O(n)
}LinkQueue;
//带头结点
void InitQueue(LinkQueue& Q)
{Q.front = Q.rear = (LinkNode*)malloc(sizeof(LinkNode));if (Q.front == NULL)return;Q.front->next = NULL;
}
bool IsEmpty(LinkQueue Q)
{if (Q.front == Q.rear)//Q.front->next==NULLreturn true;elsereturn false;
}
void EnQueue(LinkQueue& Q, ElemType x)
{LinkNode* s = (LinkNode*)malloc(sizeof(LinkNode));if (s == NULL)return;s->next = NULL;s->data = x;Q.rear->next = s;Q.rear = s;
}
bool DeQueue(LinkQueue& Q, ElemType& x) {if (Q.front == Q.rear)return false;LinkNode* s = Q.front->next;x = s->data;Q.front->next = s->next;if (Q.rear == s)Q.rear = Q.front;free(s);return true;
}

2.2 不带头结点

与代码2.1相同的部分省略

//不带头结点
void InitQueue1(LinkQueue &Q)
{Q.front = Q.rear = NULL;
}
bool IsEmpty1(LinkQueue Q)
{if (Q.front == NULL)//Q.rear==NULLreturn true;elsereturn false;
}
void EnQueue1(LinkQueue& Q, ElemType x)
{LinkNode* s= (LinkNode*)malloc(sizeof(LinkNode));if (s == NULL)return;s->next = NULL;s->data = x;if (Q.rear == NULL)Q.front = Q.rear = s;//不带头结点，第一个元素入队时单独处理，与后续元素入队不同的是，要更改头指针的指向else {Q.rear->next = s;Q.rear = s;}
}
bool DeQueue1(LinkQueue& Q, ElemType& x) {if (Q.front == Q.rear)return false;LinkNode* p = Q.front;x = p->data;Q.front = p->next;if (Q.rear == p)Q.rear = Q.front=NULL;free(p);return true;
}

总结

链式存储实现的队列与顺序存储相比，好处在于，顺序存储的空间是预分配的，一旦满了就不能再插入。但链式存储一般不存在队满的情况，除非内存不足。
在书写代码时，思考不带头结点与带头节点在操作上的区别，是否单独处理要分情况。