Java集合中有一个Stack的类，这个类基于Vector集合实现，但是效率较低。ArrayDeque在官方文档中被推荐为栈的首选集合，其次为LikedList
ArrayDeque特点
- ArrayDeque是基于循环数组的双端队列，被用来实现队列和栈的数据结构的功能。
- ArrayDeque是非线程安全的。
- 不允许放入null元素，否则抛出异常。
ArrayDeque数据结构
网络图片，侵联删
上图中我们看到，** head 指向首端第一个有效元素， tail 指向尾端第一个可以插入元素的空位**。因为是循环数组，所以 head 不一定总等于0， tail 也不一定总是比
head 大。
定义
实现了Deque双端队列接口，以及克隆和序列化接口
方法剖析
构造函数
构造函数
allocateElements 方法
这个方法原理以及起到的作用和HashMap.tableSizeFor(int cap)基本一样：返回2的指数和用来后来的掩码运算。
- 默认构造函数会创建初始长度为16的数组。
- 当使用含有初始容量的构造函数的时候，会按照构造参数创建大于等于 numElements 的2的整数幂的数。
addFirst的调用流程
网络图片，侵联删
addFirst(E e)的作用是在Deque的首端插入元素，也就是在head的前面插入元素，在空间足够且下标没有越界的情况下，只需要将elements[--head] = e即可。
实际需要考虑：1.空间是否够用，以及2.下标是否越界的问题。上图中，如果head为0之后接着调用addFirst()，虽然空余空间还够用，但head为-1，下标越界了。下列代码很好的解决了这两个问题。
** addFirst **
- 空间问题：空间问题是在插入之后解决的，因为
tail总是指向下一个可插入的空位，也就意味着elements数组至少有一个空位，所以插入元素的时候不用考虑空间问题。在插入之后判断一下头尾是否重合即数组是否已满，如果已满则进行扩容。 - 当插入head结点是，计算下标为 head-1 当head为0时将得到 -1 ，其实想要将在head为0的节点前插入元素，利用循环数组性质，此时应该插入在数组的末尾。
head = (head - 1) & (elements.length - 1)这段代码相当于就可以完成上述功能：实际上对数组长度的取模运算，当大于等于0时，对数组长度取余还是原来的数，当head为-1时，对数组取余等于数组的最后一个元素。
doubleCapacity扩容函数
网络图片，侵联删
- 复制分两次进行，第一次复制
head右边的元素，第二次复制head左边的元素。 - ** 保证扩容后的循环数组是规整的(head = 0)。**
addLast()
addLast(E e)的作用是在Deque的尾端插入元素，也就是在 tail 的位置插入元素，由于 tail 总是指向下一个可以插入的空位，因此只需要 elements[tail] = e; 即可。插入完成后再检查空间，如果空间已经用光，则调用doubleCapacity()进行扩容。
- 直接在尾端添加元素（尾端保证含有一个空闲位置）。
- 插入后检查是否已满，如果满了则进行扩容。
pollFirst()
删除并返回Deque首端元素，也即是 head 位置处的元素。如果容器不空，只需要直接返回elements[head]即可，当然还需要处理下标的问题。由于ArrayDeque中不允许放入null，当elements[head] == null时，意味着容器为空。
pollLast()
pollLast()的作用是删除并返回Deque尾端元素，也即是tail位置前面的那个元素。
peekFirst()
peekFirst()的作用是返回但不删除Deque首端元素，也即是head位置处的元素，直接返回elements[head]即可。
peekLast()
peekLast()的作用是返回但不删除Deque尾端元素，也即是tail位置前面的那个元素。
toArray()
按照循环数组的头尾顺序复制数组
当将ArrayDeque转换为其他类型的集合时，就可以按照循环数组的顺序构建其他集合如ArrayList
当用其他集合构建本集合时，都会调用参数集合的toArray()方法。
所以不用担心循环数组在转换为其他集合时会影响元素顺序。
网友评论