`
mixer_a
  • 浏览: 338303 次
社区版块
存档分类
最新评论

深度剖析Java数据结构之队列(一)——双端队列(ArrayDeque)

 
阅读更多

一、队列

队列是一种特殊的线性表,它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作。进行插入操作的端称为队尾,进行删除操作的端称为队头。队列中没有元素时,称为空队列。

二、双端队列

双端队列是只既可以在表的前端进行插入和删除操作,又可以在表的后端进行插入和删除操作。

三、ArrayDeque的实现

Java中的双端队列是用数组实现的,类的全限名称是java.util.ArrayDeque,该类的声明如下:

该类继承了AbstractCollection类,实现了Deque、Cloneable和Serializable接口。实现Cloneable和Serializable接口的主要目的是为了实现克隆和序列化。

该类中定义了四个个成员变量

其中elements是数组的首地址,head是指向队首的下标,tail是指向队尾的下一个位置的下标。MIN_INITIAL_CAPACITY 定义了在创建队列是,如果有指定长度,而且指定长度小于MIN_INITIAL_CAPACITY,则使用MIN_INITIAL_CAPACITY 作为数组的最小长度。

其构造函数有一下几种:

第一种构造函数,默认情况下,数组的长度为16。

第二种构造函数,给定数组长度,则调用allocateElements()函数,分配数组空间。allocateElements()函数的实现如下:

对于一个给定长度,先判断是否小于定义的最小长度,如果小于,则使用定义的最小长度作为数组的长度。否则,找到比给定长度大的最小的2的幂数(在if里面的以为语句实现这一功能)。

第三种构造函数,给定一个集合,先分配空间,然后添加到集合中。

从上面的三种构造函数中,可以判断出来,数组的长度是2的幂数,定义为2的幂数个人认为有两个原因:

1.伙伴系统

操作系统分配内存的方法使用伙伴系统的话,每一块的大小都是2的幂数,如果分配的内存大小为2的幂数,可以减少内存分配的时间。

伙伴系统在百度百科中的解释:http://baike.baidu.com/view/4935190.htm

2.插入和删除的速度

对于数组,如果head的值为0,时,在队首插入元素,有一种方法是将全部元素都向后移动一位,然后将新的元素插入。这样子的话,插入和删除的速度会非常慢,特别是在元素很多的情况下。另一种方法就是在head的值为0时,在队首插入元素,可以将head的值置为(数组的长度-1)。也就是将新插入的元素放到数组的最后,以此类推。在计算插入元素位置下标的时候,数组长度是2的幂数就用处了。下面是插入元素时,计算插入位置的值的语句

length-1的值为高位全为0,低位全为1,通过按位相与,可以得出应该插入元素的位置。
然后就是该类的一些方法了,有点面向对象的思想的都应该会想到,应该有头插,头删,尾插,尾删等等一些操作,在此就不一一列出了,实现起来也比较简单。关键还是要了解ArrayDeque的实现机制。

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics