资讯专栏INFORMATION COLUMN

Java中的Queue与Deque

zhangrxiang / 859人阅读

摘要:最小初始化容量。它作为堆栈队列双端队列的操作和的操作是一致的,只是内部的实现不同。根据元素内容查找和删除的效率比较低,为。但是接口有对应的并发实现类类。

Queue接口的实现类

Queue接口作为队列数据结构,java在实现的时候,直接定义了Deque接口(双端队列)来继承Queue接口,并且只实现Deque接口。这样java中的双端队列就囊括了队列、双端队列、堆栈(Deque接口又定义了Stack的操作方法)这3种角色的功能。

所以我们在使用的时候直接使用的是Deque接口的实现类,当然Deque接口继承自Queue接口。

Deque接口的实现类

我们记住,Deque接口所能代表的数据结构:队列,双端队列,堆栈。

ArrayDeque

1.内部使用transient Object[] elements数组来实现。拥有head/tail这2个头尾指针。最小初始化容量8。它还是一个循环队列。

2.在扩容/初始化的时候,数组的内部大小一定是2个幂次方,也就是说大小只可能是:8、16、32、64这样的倍增。

3.它作为堆栈、队列、双端队列的操作和LinkedList的操作是一致的,只是内部的实现不同。当然,它们也有区别。

ArrayDeque实现了双端队列,内部使用循环数组实现,这决定了它有如下特点:

在两端添加、删除元素的效率很高,动态扩展需要的内存分配以及数组拷贝开销可以被平摊,具体来说,添加N个元素的效率为O(N)。

根据元素内容查找和删除的效率比较低,为O(N)。

与ArrayList和LinkedList不同,没有索引位置的概念,不能根据索引位置进行操作(无法随机访问,这也符合队列的性质)。

4.操作示例,要记住,Deque具有3种数据结构的特性,不同的数据结构应该使用不同的语义化方法!

LinkedList

LinkedList中在“List有序集合”这一篇文章中讲过了,从队列和双端队列的角度来看,LinkedList和ArrayDeque的方法声明都是一致的。只不过LinkedList较之于ArrayDeque多实现了List接口,还具有有序集合List的特性。

ArrayDeque和LinkedList的比较

ArrayDeque和LinkedList都实现了Deque接口,应该用哪一个呢?如果只需要Deque接口,从两端进行操作,一般而言,ArrayDeque效率更高一些,应该被优先使用。不过,如果同时需要根据索引位置进行操作,或者经常需要在中间进行插入和删除,则应该选LinkedList(注意,这里使用的是List特性,而不是Deque特性了)。

PriorityQueue

有一个直接实现了Queue接口的类,但是它并不是真正意义上的队列,而是一个优先队列

PriorityQueue保存元素的顺序并不是按照加入的顺序,而是根据元素的大小(实现Comparable接口或提供Comparator类)来决定元素在Queue队列中的顺序。默认情况如果我们存入String对象,则是按降序排列。

可以看到,优先队列的默认大小为11,内部使用Object[]数组来实现队列结构。

对于扩容操作,可以看到。如果当前容量小于64,则容量增加2;如果当前容量大于等于64,则变为原来的1.5倍。

讲讲Queue/Deque对应的并发类

PriorityQueue优先队列没有对应的并发类。但是Queue接口有对应的并发实现类:java.util.concurrent.ConcurrentLinkedQueue类。

Deque接口有对应的并发实现类:java.util.concurrent.ConcurrentLinkedDeque类。

Collection集合下的Queue/Deque

从类图来看,实现了Queue接口的类就是PriorityQueue,但要注意它是优先队列!实现了Deque接口的类有ArrayDeque和LinkedList,2者的内部实现不同,一个是数组,另一个是链表。

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/77270.html

相关文章

  • java集合-List

    摘要:会死循环,因为栈内不会弹出所以判断会一直执行。集合用于模拟队列这种数据结构,队列通常是指先进先出的容器。集合不仅提供了的功能,还提供了双端队列,栈的功能。如果有多个线程需要访问集合中的元素,需要考虑使用将几个包装成线程安全集合。 List判断两个对象相等只通过equals方法比较返回true即可。 public class A { @Override public ...

    MasonEast 评论0 收藏0
  • Java 集合 Queue

    摘要:除此之外,还有一个接口,代表一个双端队列,双端队列可以同时从两端删除添加元素,因此的实现类既可当成队列使用,也可当成栈使用。相当于栈方法将一个元素进该双端队列所表示的栈的栈顶。 Queue用于模拟队列这种数据结构,队列通常是指先进先出(FIFO)的容器。队列的头部保存在队列中存放时间最长的元素,队列的尾部保存在队列中存放时间最短的元素。新元素插入(offer)到队列的尾部,访问元素(p...

    bang590 评论0 收藏0
  • 源码|jdk源码之栈、队列及ArrayDeque分析

    摘要:栈队列双端队列都是非常经典的数据结构。结合了栈和队列的特点。因此,在中,有栈的使用需求时,使用代替。迭代器之前源码源码之与字段中分析过,容器的实现中,所有修改过容器结构的操作都需要修改字段。 栈、队列、双端队列都是非常经典的数据结构。和链表、数组不同,这三种数据结构的抽象层次更高。它只描述了数据结构有哪些行为,而并不关心数据结构内部用何种思路、方式去组织。本篇博文重点关注这三种数据结构...

    ZHAO_ 评论0 收藏0
  • Week 2 - Java 容器 - 详细剖析 List 之 ArrayList, Vector,

    摘要:底层使用的是双向链表数据结构之前为循环链表,取消了循环。快速随机访问就是通过元素的序号快速获取元素对象对应于方法。而接口就是用来标识该类支持快速随机访问。仅仅是起标识作用。,中文名为双端队列。不同的是,是线程安全的,内部使用了进行同步。 前言 学习情况记录 时间:week 2 SMART子目标 :Java 容器 记录在学习Java容器 知识点中,关于List的需要重点记录的知识点。...

    MartinDai 评论0 收藏0
  • Java 队列

    摘要:队列中有元素时,就说明有过期了,线程继续执行,然后元素出队,根据相应的移除缓存。所以严格来说,虽然实现了队列接口,但是它的目的却并不是队列,而是将生产者消费者线程配对。转移队列链式转移队列。 引言 本周在编写短信验证码频率限制切面的时候,经潘老师给的实现思路,使用队列进行实现。 看了看java.util包下的Queue接口,发现还从来没用过呢! Collection集合类接口,由它派生...

    Pocher 评论0 收藏0

发表评论

0条评论

最新活动
阅读需要支付1元查看
<