鼻部整形

注册

 

发新话题 回复该主题

ArrayDequeJDK双端队列源 [复制链接]

1#
前言

在本篇文章当中主要跟大家介绍JDK给我们提供的一种用数组实现的双端队列,在之前的文章LinkedList源码剖析当中我们已经介绍了一种双端队列,不过与ArrayDeque不同的是,LinkedList的双端队列使用双向链表实现的。

双端队列整体分析

我们通常所谈论到的队列都是一端进一端出,而双端队列的两端则都是可进可出。下面是双端队列的几个操作:

数据从双端队列左侧进入。

数据从双端队列右侧进入。

数据从双端队列左侧弹出。

数据从双端队列右侧弹出。

而在ArrayDeque当中也给我们提供了对应的方法去实现,比如下面这个例子就是上图对应的代码操作:

数组实现ArrayDeque(双端队列)的原理

ArrayDeque底层是使用数组实现的,而且数组的长度必须是2的整数次幂,这么操作的原因是为了后面位运算好操作。在ArrayDeque当中有两个整形变量head和tail,分别指向右侧的第一个进入队列的数据和左侧第一个进行队列的数据,整个内存布局如下图所示:

其中tail指的位置没有数据,head指的位置存在数据。

当我们需要从左往右增加数据时(入队),内存当中数据变化情况如下:

当我们需要从右往做左增加数据时(入队),内存当中数据变化情况如下:

当我们需要从右往左删除数据时(出队),内存当中数据变化情况如下:

当我们需要从左往右删除数据时(出队),内存当中数据变化情况如下:

底层数据遍历顺序和逻辑顺序

上面主要谈论到的数组在内存当中的布局,但是他是具体的物理存储数据的顺序,这个顺序和我们的逻辑上的顺序是不一样的,根据上面的插入顺序,我们可以画出下面的图,大家可以仔细分析一下这个图的顺序问题。

上图当中队列左侧的如队顺序是0,1,2,3,右侧入队的顺序为15,14,13,12,11,10,9,8,因此在逻辑上我们的队列当中的数据布局如下图所示:

根据前面一小节谈到的输入在入队的时候数组当中数据的变化我们可以知道,数据在数组当中的布局为:

ArrayDeque类关键字段分析

以上就是ArrayDeque当中的最主要的字段,其含义还是比较容易理解的!

ArrayDeque构造函数分析

默认构造函数,数组默认申请的长度为16。

指定数组长度的初始化长度,下面列出了改构造函数涉及的所有函数。

上面的最难理解的就是函数calculateSize了,他的主要作用是如果用户输入的长度小于MIN_INITIAL_CAPACITY时,返回MIN_INITIAL_CAPACITY。否则返回比initialCapacity大的第一个是2的整数幂的整数,比如说如果输入的是9返回的16,输入4返回8。

calculateSize的代码还是很难理解的,让我们一点一点的来分析。首先我们使用一个2的整数次幂的数进行上面移位操作的操作!

从上图当中我们会发现,我们在一个数的二进制数的32位放一个1,经过移位之后最终32位的比特数字全部变成了1。根据上面数字变化的规律我们可以发现,任何一个比特经过上面移位的变化,这个比特后面的31个比特位都会变成1,像下图那样:

因此上述的移位操作的结果只取决于最高一位的比特值为1,移位操作后它后面的所有比特位的值全为1,而在上面函数的最后,我们返回的结果就是上面移位之后的结果+1。又因为移位之后最高位的1到最低位的1之间的比特值全为1,当我们+1之后他会不断的进位,最终只有一个比特位置是1,因此它是2的整数倍。

经过上述过程分析,我们就可以立即函数calculateSize了。

ArrayDeque关键函数分析addLast函数分析

代码(tail+1)(elements.length-1)==(tail+1)%elements.length成立的原因是任意一个数a对2n进行取余数操作和a跟2n1进行运算的结果相等,即:

a%2n=a(2n1)

从上面的代码来看下标为tail的位置是没有数据的,是一个空位置。

addFirst函数分析

上面代码操作结果和上文当中我们提到的,在队列当中从右向左加入数据一样。从上面的代码看,我们可以发现下标为head的位置是存在数据的。

doubleCapacity函数分析

上面的代码还是比较简单的,这里给大家一个图示,大家就更加容易理解了:

扩容之后将原来数组的数据拷贝到了新数组当中,虽然数据在旧数组和新数组当中的顺序发生变化了,但是他们的相对顺序却没有发生变化,他们的逻辑顺序也是一样的,这里的逻辑可能有点绕,大家在这里可以好好思考一下。

pollLast和pollFirst函数分析

这两个函数的代码就比较简单了,大家可以根据前文所谈到的内容和图示去理解下面的代码。

总结

在本篇文章当中,主要跟大家分享了ArrayDeque的设计原理,和他的底层实现过程。ArrayDeque底层数组当中的数据顺序和队列的逻辑顺序这部分可能比较抽象,大家可以根据图示好好体会一下!!!

更多精彩内容合集可访问项目:

分享 转发
TOP
发新话题 回复该主题