首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Java集合--Queue队列介绍

Java集合--Queue队列介绍

作者头像
贾博岩
发布2018-05-11 16:01:32
1K0
发布2018-05-11 16:01:32
举报
文章被收录于专栏:博岩Java大讲堂博岩Java大讲堂

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实现);

本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2017.10.21 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 4 Queue队列
    • 1. Queue
      • 1.1 队列的两种形式
      领券
      问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档