3.7 队列的链式存储结构★3◎3
3.7 队列的链式存储结构★3◎3
我们可以采用线性链表来表示队列，在不增加额外变量和方便队列操作的要求下，我们规定链表尾为队列尾，链表头为队列头，如图3-8所示。
以带头结点的单链表为例，当采用链式结构存储队列时，队列的各类操作的实现方法如表3-6所示。
表3-6 带头结点单链表实现队列
|
操 作 |
实现方法 |
时间复杂度 |
| 队列初始化 | 初始化链表L;front=L;rear=L； | |
| 队列元素数 | 遍历链表 | O(n) |
| 队列空判断 | L->next==NULL | |
| 队列满判断 | 无 | |
| 入队列时指针操作 | 在链表L尾插入结点，即插入结点到rear后； rear指向新插入的结点，即rear=rear->next； |
O(1) |
| 出队列时指针操作 | 删除链表L的第一个结点：ListDelete_L(L, 1, E)； front=L不变； 如果队列空，则初始化rear，即rear=L； |
O(1) |
如图3-9所示为带头结点单链表表示队列时的指针变化情况示意图。
队列链式存储结构的特点：
（1）入队列、出队列操作的时间复杂度为常数。
（2）只要存储空间足够，就没有最大数据元素数的限制。
（3）只需队列头指针和尾指针就可以完成各种队列操作，不需要额外增加其他存储空间。
（4）在不增加新的存储空间的情况下，获取队列中元素数的算法时间复杂度为O(n)。
队列的链式存储结构适用于用户无法估计队列最大长度的应用中。
3.7 队列的链式存储结构★3◎3