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

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


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

    关于作者: admin

    这里可以再内容模板定义一些文字和说明,也可以调用对应作者的简介!或者做一些网站的描述之类的文字活着HTML!

    为您推荐

    发表评论

    电子邮件地址不会被公开。 必填项已用*标注

    评论列表 人参与

    联系我们

    联系我们

    8888-88888888

    在线咨询: QQ交谈

    邮箱: email@admin.com

    工作时间:周一至周五,9:00-17:30,节假日休息

    关注微信
    微信扫一扫关注我们

    微信扫一扫关注我们

    关注微博
    返回顶部