写cs61b题目时惊叹为什么会有这种东西，于是搜索了一番，发现这容器还是很有意思的，于是搬运了一下。

参考： ArrayDeque - (jianshu.com)

Java ArrayDeque - Java教程 - 菜鸟教程 (cainiaojc.com)

在ArrayDeque类实现这两个接口：Java Queue和Java Deque

使用了数组来存储数据，同时用两个int值 head 和 tail 来表示头部和尾部。不过需要注意的是 tail 并不是尾部元素的索引，而是尾部元素的 下一位 ，即下一个将要被加入的元素的索引。

ArrayDeque 有三个构造函数来初始化，除了无参的构造函数使用了默认容量，其它两个构造函数会通过 allocateElements 函数来计算初始容量

数组的大小很特殊，大小必为2的n次方（2^n）。下面我们看看 allocateElements 方法

(1)对于一个小于2^30的值，经过五次右移和位或操作后，可以得到一个 2^k - 1 的值。最后再将这个值 +1 ，得到 2^k 。通过这个方法，可以将一个任意的初始值转化为2^n的值.

(2)不过有一点不足在于，如果本身传进来的值就是 2^n 的值，那么经过转化会变成 2^(n+1) ，所以我们在不用刻意去传入 2^n 的值。

(3)如果传入的值大于等于 2^30 ，那么经过转化会变成负值，即<0，此时会把初始值设置为 2^30 ，即最大的容量只有 2^30

在ArrayDeque中，数组是作为环形来使用的，正常情况下在末尾添加元素后，tail=tail+1是要判断是否越界，如果越界，会变为从索引0开始。参考如下图片，当H添加到索引7后，tail值会+1,此时tail=8，但是越界了，所以应该将tail设置为0。

我们看看 tail = (tail + 1) &(elements.length - 1) 的正确性：

所以当 tail+1 <= length - 1 ，此时数组并没有越界， (tail + 1) &(elements.length - 1) 后得到的还是 tail+1 。如果 tail + 1 = length ，此时数组越界了， (tail + 1) &(elements.length - 1) 后得到0。

所以通过 (tail + 1) &(elements.length - 1) 可以跳过条件判断在环形数组中获取正确的索引值，然后再判断新的 tail 是否等于 head ，如果结果为 true ，那么数组已经满了，需要扩容，即 doubleCapacity() 。

原理和addLast相同

无论是从头部还是从尾部添加元素，都会判断 tail==head ，如果两个索引相遇，说明数组空间已满，需要扩容操作.

ArrayDeque支持从头尾两端移除元素

在上文中，我们讲了怎么去实现一个ArrayDeque，但Java标准库中已经为我们准备好了，我们只需按规则使用就行

add() - 将指定的元素插入ArrayDeque双端队列的 末尾

addFirst() -在ArrayDeque双端队列的 开头 ，插入指定的元素

addLast() - 在ArrayDeque双端队列的 末尾 插入指定的内容（等效于 add() ）

注意：如果ArrayDeque双端队列已满，则所有这些方法 add() ， addFirst() 和 addLast() 都会引发IllegalStateException

offer() - 将指定的元素插入ArrayDeque双端队列的 末尾

offerFirst() - 在ArrayDeque双端队列的 开始处 插入指定的元素

offerLast() - 将指定的元素插入ArrayDeque双端队列的 末尾

注意： offer()，offerFirst()并offerLast()返回true是否成功插入元素；否则，返回。如果ArrayDeque双端队列已满，则这些方法返回false。

getFirst() - 返回ArrayDeque双端队列的 第一个元素

getLast() - 返回ArrayDeque双端队列的 最后一个元素

注：如果ArrayDeque双端队列为空，getFirst()和getLast()抛出NoSuchElementException。

peek() - 返回ArrayDeque双端队列的 第一个 元素

peekFirst() - 返回ArrayDeque双端队列的 第一个 元素（等效于 peek() ）

peekLast() - 返回ArrayDeque双端队列的 最后一个 元素

注：如果ArrayDeque双端队列为空，peek()，peekFirst()和getLast()抛出 NoSuchElementException

remove() - 返回并从ArrayDeque双端队列的 第一个 元素中删除一个元素

remove(element) - 返回并从ArrayDeque双端队列的 头部 删除指定的元素

removeFirst() - 返回并从ArrayDeque双端队列中删除 第一个 元素（等效于remove()）

removeLast() - 返回并从ArrayDeque双端队列中删除 最后一个元素

注意：如果数组双端队列为空，则remove()，removeFirst()和removeLast()方法将引发异常。 另外，如果找不到元素，则remove(element)会引发异常。

poll() - 返回并删除ArrayDeque双端队列的 第一个 元素

pollFirst() - 返回并删除ArrayDeque双端队列的 第一个 元素（等效于poll()）

pollLast() - 返回并删除ArrayDeque双端队列的 最后一个 元素

注意：如果ArrayDeque双端队列为空，则如果找不到该元素，则poll()，pollFirst()和pollLast()返回null。

删除所有元素

iterator() - 返回可用于遍历ArrayDeque双端队列的 迭代器

descendingIterator() -返回一个迭代器，该迭代器可用于以 相反顺序 遍历ArrayDeque双端队列

注：为了使用这些方法，我们必须导入java.util.Iterator包。

使用迭代器的方法如下

element() -从ArrayDeque双端队列的头部返回一个元素。

contains(element) -在ArrayDeque双端队列中搜索指定的元素。如果找到该元素，则返回true，否则返回false。

size() -返回ArrayDeque双端队列的长度。

toArray() -将ArrayDeque双端队列转换为数组并返回。

clone() -创建ArrayDeque双端队列的副本并返回它。

push() - 在堆栈顶部添加一个元素

peek() - 从堆栈顶部返回一个元素

pop() - 返回并从堆栈顶部删除元素

所属论坛: JAVA论坛

正文内容:

java方面的：

it人资讯交流网

http://www.it315.org

这个网站是我最近才发现的，虽然内容不多，但是提供的相关java工具挺齐全。还有就是里面提供了java教学视频录象的免费下载，好像一两周更换一段。个人觉得挺适合初学者的，尤其是那个classpath的设置，讲的很透彻，大家有空可以看一看。

java官方站点(英文)

http://java.sun.com

要想了解最新的java动态，下载最新的java相关，比如j2se、j2ee、j2se的最新jdk版本就来这里吧。

java中文站

http://www.java-cn.com

这个可能大家都知道，不用说了，他提供的java资源是最丰富的。注册论坛是免费的，还送积分，用积分可以下载软件和电子书等，如果积分用完了，就需要自己发表一些文章来赚新的积分。

中文java网站

http://www.cn-java.com

跟上面站点类似的一个站，宗旨就是：为java爱好者服务。值得一看！

锋网

http://www.ijsp.net/tech/book/index.jsp

综合性的java网站，内含“下载中心”、“教程教学”等栏目。

java动力

http://eww.cn

网站的内容可以，但是最为出色的是它所运用的flash技术，我就不在这里多说了，大家去看看就知道了，一个字“酷”！！！

vc方面的：

vc知识库

http://www.vckbase.com

这个网站就不用多说了，学习vc必去之地。网站专门提供了免费的ftp下载，好东东巨多！

vc之路

http://www.vcroad.com

综合软件开发网站，以vc为主。“资源中心”有许多值得下载的东东。

visual c++/mfc开发指南

http://www.vchelp.net

以讲述windows开发为主的站点，提供了最新的源代码，开发工具，开发资料，开发教程和对好的开发站点，开发工具，图书做介绍，同时为从事开发的朋友提供发布自己开发的软件，代码和工具场所。

c维拥?

http://www.c-view.org/root/index.htm

最近发现的vc好站，书籍、软件、代码下载一应具全！！！

游戏开发：

风云工作室

http://member.netease.com/~cloudwu/2000/index.html

标点游戏制作

http://makegame.myetang.com/

未来开发者

http://www.fdev.net/

综合的：

中国软件网

http://www.csdn.net

中国最大的开发者网络，他之所以著名就是因为他的论坛，大家有空可以去看看，能下到很多不错的东东，另外也是交流学习的好地方。

电子书籍的：

http://www.itebook.net

最后公布一个巨好的，狂多的电子书下载

http://www.pdown.net

还有巨好的

http://www.codestudy.net/default.asp