文档章节

看看ArrayDeque源码

woshixin
 woshixin
发布于 11/22 18:20
字数 901
阅读 8
收藏 0

之前看了其他实现Deque接口的类,这里再看看ArrayDeque吧,下图可以看到这个类设计的结构层次,其实Deque接口是继承了Queue接口的。用可调整大小的数组实现Deque接口。没有容量限制,他们根据需要增长以支持使用。它们不是线程安全的,在没有外部同步的情况下,它们不支持多线程的并发访问。禁止使用空元素。

大多数ArrayDeque操作以常量时间运行。例外包括remove,removeFirstOccurrence,removeLastOccurrence,contains,iterator.remove()和一些批量操作,所有这些都以线性时间运行。

此类有三个构造函数,如下图:

ArrayDeque​():构造一个空数组deque,其初始容量16个元素。

ArrayDeque​(int numElements):构造一个空数组deque,其初始容量足以容纳指定数量的元素。

ArrayDeque​(Collection<? extends E> c):按照集合的迭代器返回的顺序构造一个包含指定集合元素的双端队列。

ArrayDeque中的字段主要有 transient Object[] elements,transient int head;,transient int tail;这里看到就是修饰词都是transient,表示类实现了序列化接口,但是该敏感词汇不会被序列化。elements是用来存储元素的;head表示队列的头部,pop()和remove()操作的元素;tail表示下一个元素要添加的位置,比如push(),add()和addLast()要增加的元素。

calculateSize和名字表述一样,用于调整队列容量的使用工具,但是有个限制就是2 ^ 30个元素,注释写的很有趣"good luck"。

还有一种扩容测试是变为原来的两倍,这边如果容量太大,会报“sorry,deque too big”的IllegalStateException异常,可以看到扩容就要复制一份原来的元素,这个还是比较消耗资源的。复制这里用的都是 public static native void arraycopy(Object src,  int  srcPos,Object dest, int destPos,int length);

在此双端队列的前面插入指定的元素,addFirst​(E e)。这里因为是使用数组,所以增加队首元素的时候,需要判断元素在的位置,通过移动head的位置,elements[head = (head - 1) & (elements.length - 1)],这与我们正常看到的队列的第一个元素概念不同。如果head与tail指向了同一个位置,就需要扩容啦。

addLast​(E e):在此双端队列的末尾插入指定的元素。这个与addfist类似,就是要判断队尾的位置,然后是否扩容。

然后我们看看pollFisrt(),将head位置的元素置为空,然后head+1的位置设置为队首,这里借助了一个变量h;后面的pollLast也是类似的,取tail前一个元素的位置。类似的,getFirst()和getLast()也是通过相同的方式,获取元素。

这里判断size和empty的方式也可以看看,size是通过tail和head的差值计算,虽然可能是负数,但是与length-1做了与操作。empty的判断比较简单,就是比较head和tail是否相等。

这里麻烦一点的就是delete操作了,删除某个位置的元素,因为这里按照head和tail的位置,移动tail或者head的位置。

 

 

 

© 著作权归作者所有

共有 人打赏支持
woshixin
粉丝 25
博文 288
码字总数 238978
作品 0
杭州
程序员
私信 提问
Java集合--Queue(Java中实现2)

1.1 Deque源码(基于JDK1.7.0_45) 本票中,我们来看看Deque源码,在Queue基础上,又增加了哪些功能? Deque接口,是一个实现了双端队列数据结构的队列,即在头尾都可进行删除和新增操作; ...

贾博岩
2017/10/21
0
0
深入理解ArrayDeque的设计与实现

前言 最近在研读OkHttp源码,发现它的Dispatcher分发器使用了ArrayDeque数据集合,这个集合类是java.util里提供的双端队列/栈,非线程安全,但是性能很好,非常值得研究一下。 基本设计 我们...

蓝灰_q
2017/11/29
0
0
Java基础——Queue、Deque、ArrayDeque源码分析

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/qq_30379689/article/details/80558771 Queue是什么 Queue是具有队列特性的接口 Queue具有先进先出的特点 Qu...

Hensen_
06/03
0
0
学习LinkedBlockingDeque源码

之前已经看了实现deque接口的ArrayDeque, ConcurrentLinkedDeque, LinkedList,也不能落下ConcurrentLinkedDeque,但是好像没在项目中用过。 这里看到实现的接口还有BlockingDeque<E>, Block...

woshixin
12/10
0
0
Java Connection集合分析之Queue

Queue队列 1.Queue用于模拟队列这种数据结构,队列通常是指“先进先出”(FIFO)的容器。新元素插入(offer)到队列的尾部,访问元素(poll)操作会返回队列头部的元素。通常,队列不允许随机...

我爱春天的毛毛雨
11/14
0
0

没有更多内容

加载失败,请刷新页面

加载更多

java框架学习日志-7(静态代理和JDK代理)

静态代理 我们平时去餐厅吃饭,不是直接告诉厨师做什么菜的,而是先告诉服务员点什么菜,然后由服务员传到给厨师,相当于服务员是厨师的代理,我们通过代理让厨师炒菜,这就是代理模式。代理...

白话
今天
21
0
Flink Window

1.Flink窗口 Window Assigner分配器。 窗口可以是时间驱动的(Time Window,例如:每30秒钟),也可以是数据驱动的(Count Window,例如:每一百个元素)。 一种经典的窗口分类可以分成: 翻...

满小茂
今天
17
0
my.ini

1

architect刘源源
今天
14
0
docker dns

There is a opensource application that solves this issue, it's called DNS Proxy Server It's a DNS server that solves containers hostnames, if could not found a hostname that mat......

kut
今天
15
0
寻找数学的广度——《这才是数学》读书笔记2700字

寻找数学的广度——《这才是数学》读书笔记2700字: 文|程哲。数学学习方式之广:国内外数学教育方面的专家,进行了很多种不同的数学学习方式尝试,如数学绘本、数学游戏、数学实验、数学步道...

原创小博客
今天
27
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部