课程咨询: 400-996-5531 / 投诉建议: 400-111-8989
认识达内从这里开始
认真做教育 专心促就业
随着互联网的不断发展，越来越多的人都在学习Java编程开发语言，而本文我们就通过案例分析来简单了解一下，队列的概念与类型。
1、基本概念
队列也是一种受限的线性表，特殊之处在于它只允许在一端插入，在另一端删除。因此，先进入队列的元素能先从队列中删除，故队列又被称为先进先出表。
2、实现类型
在物理存储层面，队列既可以用数组实现，也可以用链表实现，在这两种数据结构的基础上增加队列的限制即可。
使用数组实现的队列被称为顺序队列，使用链表实现的队列被称为链式队列。
3、顺序队列
使用数组实现的顺序队列比实现完整功能的数组更加简单，不需要实现往数组中插入元素和删除数组内元素的功能。
需要申请一个大小为n的数组;然后，创建一个队头标识和队尾标识;当入队时，需要将队尾标识后移一位;当出队时，也需要将队头标识后移一位。
当数组无限大的时候，上述的实现方式没有任何问题。但数组向来是限制大小的，而且出队之后，数组的前半部分已经没有数据存储了，非常浪费空间。
对于这种情况，通常采用搬移数据的办法，当队尾标识已经达到n的下标时，则做一次数据搬移，并且将队头标识和队尾标识指向新的下标。
以这种实现思路，入队的均摊时间复杂度为O(1)，出队的时间复杂度一直都是O(1)。
4、链式队列
使用链表实现的链式队列比使用数组实现的顺序队列更加简单，由于链表的特性，减少了搬移数据这一步。
链表不需要提前申请内存空间，也不需要担心内存空间不够的问题，只需要创建好队头标识和队尾标识即可，因此链式队列也是常见的队列实现方式。
如果是采用尾插法实现的链表，可以将链表的哨兵结点的指向作为队头标识，这样只需要新增一个队尾标识即可。当新的元素入队时，将这个元素链接到尾结点，然后修改队尾标识的指向;需要出队时，则做删除头结点的操作，修改哨兵结点的指向。
以链表实现的队列，无论是入队还是出队，时间复杂度都可以达到O(1)。
5、循环队列
顺序队列在入队时会有搬移数据的情况，存在一定的性能损耗，循环队列则是在这一方面做了部分优化，减少这一步操作。
如果把数组看作一条直线，就可以把循环队列看作一个环，通过将队列做成环的方式，可以避免数据搬移的操作。
6、双端队列
双端队列是一种具有队列和栈的性质的数据结构，即常说的deque(double-endedqueue)，是一种限定插入和删除操作在表的两端进行的线性表。
【免责声明】本文系本网编辑部分转载，转载目的在于传递更多信息，并不代表本网赞同其观点和对其真实性负责。如涉及作品内容、版权和其它问题，请在30日内与管理员联系，我们会予以更改或删除相关文章，以保证您的权益!更多内容请加danei0707学习了解。欢迎关注“达内在线”参与分销，赚更多好礼。
< 上一篇：贵阳达内计算机培训数据结构栈的应用场景都有哪些
2024-01-19
免费试听课程
- 全部课程
- IT课程
- 设计课程
- 运营课程
4578
最新开班时间
- 北京
- 上海
- 广州
- 深圳
- 南京
- 成都
- 武汉
- 西安
- 青岛
- 天津
- 杭州
- 重庆
- 哈尔滨
- 济南
- 沈阳
- 合肥
- 郑州
- 长春
- 苏州
- 长沙
- 昆明
- 太原
- 无锡
- 石家庄
- 南宁
- 佛山
- 珠海
- 宁波
- 保定
- 呼和浩特
- 洛阳
- 烟台
- 运城
- 潍坊
- 开课名称
- 开班时间
- 抢座
- 咨询
- 开课名称
- 开班时间
- 抢座
- 咨询
-
- Java全链路开发
- 3月31日
- 火热抢座中
- 立即咨询
- 云计算全栈开发
- 3月31日
- 火热抢座中
- 立即咨询
-
- 网络安全工程师
- 3月31日
- 火热抢座中
- 立即咨询
- 人工智能工程师
- 3月31日
- 火热抢座中
- 立即咨询
-
- 数据分析与商业智能
- 3月31日
- 火热抢座中
- 立即咨询
- C++物联网工程师
- 3月31日
- 火热抢座中
- 立即咨询
-
- Web全栈开发
- 3月31日
- 火热抢座中
- 立即咨询
- 软件测试工程师
- 3月31日
- 火热抢座中
- 立即咨询
-
- AI大模型全栈工程师
- 3月31日
- 火热抢座中
- 立即咨询
- 鸿蒙原生应用开发
- 3月31日
- 火热抢座中
- 立即咨询
-
- 智能职场办公
- 3月31日
- 火热抢座中
- 立即咨询
- VFX商业视效设计
- 3月31日
- 火热抢座中
- 立即咨询
-
- AGI商业设计变现
- 3月31日
- 火热抢座中
- 立即咨询
- UID全链路设计
- 3月31日
- 火热抢座中
- 立即咨询
-
- 新媒体电商运营
- 3月31日
- 火热抢座中
- 立即咨询
-
- Java全链路开发
- 3月31日
- 火热抢座中
- 立即咨询
- 云计算全栈开发
- 3月31日
- 火热抢座中
- 立即咨询
-
- 网络安全工程师
- 3月31日
- 火热抢座中
- 立即咨询
- C++物联网工程师
- 3月31日
- 火热抢座中
- 立即咨询
-
- Web全栈开发
- 3月31日
- 火热抢座中
- 立即咨询
- 软件测试工程师
- 3月31日
- 火热抢座中
- 立即咨询
-
- AI大模型全栈工程师
- 3月31日
- 火热抢座中
- 立即咨询
- 鸿蒙原生应用开发
- 3月31日
- 火热抢座中
- 立即咨询
-
- 智能职场办公
- 3月31日
- 火热抢座中
- 立即咨询
- VFX商业视效设计
- 3月31日
- 火热抢座中
- 立即咨询
-
- AGI商业设计变现
- 3月31日
- 火热抢座中
- 立即咨询
- UID全链路设计
- 3月31日
- 火热抢座中
- 立即咨询
-
- 新媒体电商运营
- 3月31日
- 火热抢座中
- 立即咨询
-
- 云计算全栈开发
- 3月31日
- 火热抢座中
- 立即咨询
- 网络安全工程师
- 3月31日
- 火热抢座中
- 立即咨询
-
- C++物联网工程师
- 3月31日
- 火热抢座中
- 立即咨询
- Web全栈开发
- 3月31日
- 火热抢座中
- 立即咨询
-
- 软件测试工程师
- 3月31日
- 火热抢座中
- 立即咨询
- AI大模型全栈工程师
- 3月31日
- 火热抢座中
- 立即咨询
-
- 鸿蒙原生应用开发
- 3月31日
- 火热抢座中
- 立即咨询
- 智能职场办公
- 3月31日
- 火热抢座中
- 立即咨询
-
- VFX商业视效设计
- 3月31日
- 火热抢座中
- 立即咨询
- AGI商业设计变现
- 3月31日
- 火热抢座中
- 立即咨询
-
- UID全链路设计
- 3月31日
- 火热抢座中
- 立即咨询
- 新媒体电商运营
- 3月31日
- 火热抢座中
- 立即咨询
-
- Java全链路开发
- 3月31日
- 火热抢座中
- 立即咨询
- 网络安全工程师
- 3月31日
- 火热抢座中
- 立即咨询
-
- 数据分析与商业智能
- 3月31日
- 火热抢座中
- 立即咨询
- C++物联网工程师
- 3月31日
- 火热抢座中
- 立即咨询
-
- Web全栈开发
- 3月31日
- 火热抢座中
- 立即咨询
- 软件测试工程师
- 3月31日
- 火热抢座中
- 立即咨询
-
- AI大模型全栈工程师
- 3月31日
- 火热抢座中
- 立即咨询
- 鸿蒙原生应用开发
- 3月31日
- 火热抢座中
- 立即咨询
-
- 智能职场办公
- 3月31日
- 火热抢座中
- 立即咨询
- VFX商业视效设计
- 3月31日
- 火热抢座中
- 立即咨询
-
- AGI商业设计变现
- 3月31日
- 火热抢座中
- 立即咨询
- UID全链路设计
- 3月31日
- 火热抢座中
- 立即咨询
-
- 新媒体电商运营
- 3月31日
- 火热抢座中
- 立即咨询
-
- 云计算全栈开发
- 3月31日
- 火热抢座中
- 立即咨询
- 网络安全工程师
- 3月31日
- 火热抢座中
- 立即咨询
-
- C++物联网工程师
- 3月31日
- 火热抢座中
- 立即咨询
- Web全栈开发
- 3月31日
- 火热抢座中
- 立即咨询
-
- 软件测试工程师
- 3月31日
- 火热抢座中
- 立即咨询
- AI大模型全栈工程师
- 3月31日
- 火热抢座中
- 立即咨询
-
- 鸿蒙原生应用开发
- 3月31日
- 火热抢座中
- 立即咨询
- 智能职场办公
- 3月31日
- 火热抢座中
- 立即咨询
-
- VFX商业视效设计
- 3月31日
- 火热抢座中
- 立即咨询
- AGI商业设计变现
- 3月31日
- 火热抢座中
- 立即咨询
-
- UID全链路设计
- 3月31日
- 火热抢座中
- 立即咨询
- 新媒体电商运营
- 3月31日
- 火热抢座中
- 立即咨询
预约申请试听课
400-111-8989
lihm@tedu.cn
