Java集合--Queue队列介绍

4 Queue队列

前面几篇,我们介绍了Java集合中常用到的对象。本篇中,我们再来说说Queue队列的故事。

对于Queue,或许你跟我一样,并不会将其与集合框架联系到一起,更多时候是将其归属到数据结构中。

尤其是查找集合相关的教程时,大多都是List、Set、Map,讲解Queue队列的很少出现。

但,当你真正去了解、看源码时,会发现Queue是Collection的一个子接口,与List、Set同一级别;

题外话说多了,到底什么是Queue,让我们来看!

1. Queue

Queue是Java集合框架中的一员,继承于Collection接口。

与List、Set相同的是,Queue也实现了一种数据结构,这就是队列(这也是Queue经常出现在数据结构相关文章中的主要原因)。

所以,要想明白Queue集合,首先得知道队列是什么!

队列是计算机中的一种数据结构,保存在其中的数据具有“先进先出(FIFO,First In First Out)”的特性。

如果,你不明白“先进先出”是什么,试想下排队的场景,最先进来的人解决完问题后,最早离开---这就叫“先进先出”;

当队伍中有新来的人时,需要排在队伍的末端;而当队伍中有人解决完问题时,会从队伍的前端离开。

在队列中,我们管队伍的末端叫做“队尾”,管队伍的前端叫“队头”;新来的人,称之为“入队”。而离开的人,称之为“出队”;

稍有不同的是,在数据结构中,队列不支持从队伍的中间插入和离开,只能从头尾进行。而真实生活中,我们的队伍可没有这么和谐!!!!

还有一点是,当没有人在排队时,我们称之为“空队”,也就是队列为空的情况。

通过介绍排队的场景,让我们对队列有了一个初步的概念。那么,在Java中的队列究竟如何实现呢?

1.1 队列的两种形式

在Java中,队列分为2种形式,一种是单队列,一种是循环队列;

通常,都是使用数组来实现队列,假定数组的长度为6,也就是队列的长度为6;

  • 来看单队列情况:

第一步,创建一个空数组,有两个变量,分别为front、rear,代表着头指针、尾指针;

第二步,向队列中插入数据;

第三步,移除队头中的数据;

第四步,再次向队列中插数据(此时rear指针指向了一个不存在的角标);

此时,单队列发生了“假溢出”情况,尾指针指向了一个不存在的数组角标。

如果,要解决该情况的发生,有两种方式-----一,无限扩充数组大小;二,引入循环队列;

  • 来看循环队列情况:

当尾指针超过了数组角标大小,此时我们会判断队列的头部是否有剩余的空间,如果有就把尾指针指向队列的头部;

此时,循环队列就产生了。

其实,循环队列就是将单队列的首位进行相连,形成了一个圆圈,这样就不会发生角标越界的情况了(distruptor实现);

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏小李刀刀的专栏

[译]Laravel 5.0 之 Eloquent 属性转换

本文译自 Matt Stauffer 的系列文章. ---- 之前完全忘了要把这个 Laravel 5 的系列博客写完,不过最近看到了一篇关于属性转换的简介 L...

44380
来自专栏用户1191492的专栏

物联网平台设计文档:精简GC(垃圾回收)

许多高级编程语言的自动内存管理功能让编程变成了比较容易的一件事。然而,嵌入式平台经常缺少这一部分功能,这是有原因的:现代垃圾收集(GC)系统使用的...

30250
来自专栏木可大大

编写优雅代码的最佳实践

Robert Martin曾说过"在代码阅读中说脏话的频率是衡量代码质量额唯一标准"。同时,代码的写法应当使别人理解它所需的时间最小化,也就是说我们写的代码是给...

10320
来自专栏老马说编程

计算机程序的思维逻辑 (9) - 强大的循环

循环 上节我们介绍了流程控制中的条件执行,根据具体条件不同执行不同操作。本节我们介绍流程控制中的循环,所谓循环就是多次重复执行某些类似的操作,这个操作一般不是...

22080
来自专栏coding for love

JS入门难点解析2-JS的变量提升和函数提升

(注1:如果有问题欢迎留言探讨,一起学习!转载请注明出处,喜欢可以点个赞哦!) (注2:更多内容请查看我的目录。)

15830
来自专栏林冠宏的技术文章

经典面试问题: Top K 之 ---- 海量数据找出现次数最多或,不重复的。

作者:林冠宏 / 指尖下的幽灵 掘金:https://juejin.im/user/587f0dfe128fe100570ce2d8 博客:htt...

728150
来自专栏苦逼的码农

Hash冲突之开放地址法

比如说我的输入是任意一个自然数(0,1,2,3...),而我要求经过一个函数后我的输出的数的范围要在0-9这样一个范围之间。

79520
来自专栏嵌入式程序猿

号外号外:无规矩不成方圆(4)

本文MISRA规则由嵌入式程序猿整理自网络,版权归原作者所有 不能使用三字母词 三字母词由2 个问号序列后跟1 个确定字符组成(如, ??- 代表“ ~”(非)...

27850
来自专栏极客猴

Python 中连接字符串效率最高的方式是哪种呢?

在编码过程中,我们经常需要对字符串进行连接处理操作。如果我们能使用优雅的方式来处理字符串连接,那么程序内存开销会小很多。

11120
来自专栏AI科技大本营的专栏

送书 | Python编程:从入门到实践

本文摘自《Python编程:从入门到实践》一书,本书是Amazon编程入门类榜首图书,是一本全面的Python编程从入门到实践教程,带领读者快速掌握编程基础知识...

662100

扫码关注云+社区

领取腾讯云代金券