数据结构学习笔记——队列

定义

队列(Queue):是只允许在一端进行插入操作,而在另一端进行删除操作的线性表

队列是一种先进先出的线性表。允许插入的一端称为队尾,允许删除的一端称为队头。

如下图所示:

循环队列

线性表有顺序存储和链式存储,栈是线性表,所以有这两种存储方式。同样,队列作为一种特殊的线性表,也同样存在这两种存储方式。

队列顺序存储的不足

假设有一个队列有n个元素,则顺序存储的队列需要建立一个大于n的数组,并把队列的所有元素存储在数组的前n个单元,数组下标为0的一端即是队头。所谓的入队操作,其实就是在队尾追加一个元素,不需要移动任何元素,因此世家复杂度为O(1)。

与栈不同的是,队列元素的出队是在队头,即下标为0的位置,也就意味着,队列中的所有元素都得向前移动,也就是下标为0的位置不为空,时间复杂度为O(n).

它们的具体实现和线性表的顺序存储结构是一样的,不再累赘。

但是

如果不去限制队列的元素必须存储在数组的前n个单元这一条件,出队的性能就会大大增加,如图

为了避免只有一个元素时,队头和队尾重合使得处理变得麻烦,就引入两个指针,front指向队头元素,rear指向队尾元素的下一个位置,这样当front等于rear时,表示空队列。

这样又出现一个问题,如果队尾已有元素,再插入新元素时rear指向哪里?而且,当队列中只有队尾有元素时,向后再加,就会产生数组越界错误,可实际上之前的位置可能有空,我们把这种现象叫做假溢出

循环队列定义

解决假溢出的办法就是后面满了,就再从头开始,也就是头尾相接的循环。我们把队列的这种头尾相接的顺序存储结构称为循环队列。

下标2、3、4位置已有元素,在插入新元素,则存放下标为0的位置。如图:

但之前约定当front==rear时,表示队列为空,上述方法中front==rear时还表示队列已满,怎么处理呢?

我们要求,队列满时,数组中还有一个空闲单元,如图:

得出以下公式:

  • 队列满 的条件(rear+1)%QueueSize==front
  • 队列长度公式:(rear-front+QueueSize)%QueueSize

队列的链式存储

队列的链式存储结构,其实就是线性表的单链表,只不过它只能尾进头出而已,我们简称为链队列。

空队列时,front和rear都指向头节点:

入队操作

  1. 将最后一个元素后继指向新元素;
  2. 将尾指针指向新元素。

出队操作

  1. 将头结点的后继改为后面一位结点;
  2. 若除头节点外只剩一个元素时,将rear指向头节点。

总的来说,在可以确定队列长度最大值的情况下,建议用循环队列,如果你无法预估队列的长度时,则用链队列。

原文发布于微信公众号 - Android机动车(JsAndroidClub)

原文发表时间:2018-03-26

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏瓜大三哥

UVM模型(二)之component

UVM模型(二)之component Component与object是UVM中两个最重要的概念。 ? 1.uvm_component中的parent UV...

27980
来自专栏java达人

快速失败Vs安全失败(Java迭代器附示例)

译者:java达人-卍极客 英文出处:Java Concept Of The Day 英文链接:http://javaconceptoftheday.com/...

23870
来自专栏前端黑板报

(转)ES6新特性概览

ES6(ECMAScript 6)是即将到来的新版本JavaScript语言的标准,代号harmony(和谐之意,显然没有跟上我国的步伐,我们已经进入中国梦版本...

22950
来自专栏青玉伏案

算法与数据结构(一) 线性表的顺序存储与链式存储(Swift版)

温故而知新,在接下来的几篇博客中,将会系统的对数据结构的相关内容进行回顾并总结。数据结构乃编程的基础呢,还是要不时拿出来翻一翻回顾一下。当然数据结构相关博客中我...

22470
来自专栏信安之路

php 不用字母,数字和下划线写 shell

还有这个师傅的 《记一次拿webshell踩过的坑(如何用PHP编写一个不包含数字和字母的后门)》

51110
来自专栏ACM算法日常

Bessie的好牌(队列)- POJ 3629

Bessie is playing a card game with her N-1 (2 ≤ N ≤ 100) cow friends using a dec...

14730
来自专栏calvin

【nodejs】让nodejs像后端mvc框架(asp.net mvc)一样处理请求--参数自动映射篇(6/8)

路由、action的扫描、发现、注册搞定之后,后来我发现在我们的action里面获取参数往往都是通过request对象来一个一个获取。同样的一行代码我们不厌其烦...

12720
来自专栏小灰灰

Java容器篇小结之List自问自答

I. List篇 0. 什么是List 看到这个有点懵逼,一时还真不知道怎么解释,能让完全没有接触过的人都能听懂 列表,什么是列表呢? 好比你到了一个村里,看...

22580
来自专栏小灰灰

JDK容器学习之List: CopyOnWriteArrayList,ArrayList,LinkedList对比

列表 List, ArrayList, LinkedList, CopyOnWriteArrayList, Vector 简述 1. 列表划分为线程安全和线程...

223100
来自专栏Java进阶架构师

对HashMap的思考及手写实现

HashMap是Java中常用的集合,而且HashMap的一些思想,对于我们平时解决业务上的一些问题,在思路上有帮助,基于此,本篇博客将分析HashMap底层设...

11120

扫码关注云+社区

领取腾讯云代金券