3.7 队列的链式存储结构★3◎3

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