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)。
队列的链式存储结构适用于用户无法估计队列最大长度的应用中。
评论列表 人参与