专栏首页博岩Java大讲堂Java集合--Queue队列介绍

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 条评论
登录 后参与评论

相关文章

  • Java集合--阻塞队列(引言)

    贾博岩
  • Java集合--非阻塞队列(ConcurrentLinkedQueue基础)

    贾博岩
  • Java集合--阻塞队列(LinkedBlockingQueue)

    贾博岩
  • Java队列学习第一篇之列介绍

    队列大家都知道,但是在Java中队列分哪几种呢?清楚吗?都有哪些地方用到了队列呢?最常用的场景的就是消息中间件,比如各种MQ都是使用的队列来的。如果没有用过消息...

    凯哥Java
  • 【数据结构(C语言版)系列三】 队列

    队列是一种先进先出的线性表,它只允许在表的一端进行插入,而在另一端删除元素。这和我们日常生活中的排队是一致的,最早进入队列的元素最早离开。在队列中,允许插入的一...

    闪电gogogo
  • 【FreeRTOS】队列管理2

    创建一个队列用于保存类型为xData 的结构体数据单元。结构体成员包括了一个数据值和表示数据含义的编码,两者合为一个消息可以一次性发送到队列。 ? 中央控...

    心跳包
  • 【FreeRTos】队列管理1

    写队列任务在每次循环中都调用taskYIELD()。taskYIELD()通知调度器立即进行任务切换,而不必等到当前任务的时间片耗尽。某个任务调用taskY...

    心跳包
  • Hadoop FairScheduler

    本文档描述FairScheduler,一个允许YARN应用程序公平共享集群资源的调度插件。

    用户1217611
  • 栈与队列:总结篇!

    相信不仅仅是C++中有这些问题,那么大家使用其他编程语言,也可以考虑一下这四个问题,栈和队列是如何实现的。

    代码随想录
  • 算法与数据结构(二) 栈与队列的线性和链式表示(Swift版)

    数据结构中的栈与队列还是经常使用的,栈与队列其实就是线性表的一种应用。因为线性队列分为顺序存储和链式存储,所以栈可以分为链栈和顺序栈,队列也可分为顺序队列和链队...

    lizelu

扫码关注云+社区

领取腾讯云代金券