ArrayDeque详解一.特性二.数据结构三.源码分析

86 阅读 0 评论 57 点赞

我是靠谱客的博主年轻山水，最近开发中收集的这篇文章主要介绍ArrayDeque详解一.特性二.数据结构三.源码分析，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

美人如斯！

ArrayDeque是java中对双端队列的线性实现

一.特性

无容量大小限制，容量按需增长；
非线程安全队列，无同步策略，不支持多线程安全访问；
当用作栈时，性能优于Stack，当用于队列时，性能优于LinkedList
两端都可以操作
具有fail-fast特征
不能存储null
支持双向迭代器遍历

注意: ArrayDeque的迭代器和大多数容器迭代器一样，都是快速失败(fail-fast），但是程序不能利用这个特性决定是或否进行了并发操作。

二.数据结构

为了更好的理解使用线性数组实现的双端队列，这里我们先来图解线性数组实现基本数据结构-队列：

如上图所示，head指向队头，入队加元素时，tail队尾向后移动，出队时从head出取出元素并移除，这样就利用了线性数组实现先进先出的队列数据结构，当head等于tail时，则表示队列为空。
但是这样存在问题：当不断出队时，head向后移动，前面空出来的空间就被浪费，导致不断入队时，需要数组扩容，出队时造成大量空间无法使用，空间利用率低下！
假设，如果能将前面空出来的空间也利用起来进行存储末尾的元素，则空间使用率将提高，这里就需要有个循环的思维，把这种线性的弯曲成一个圆环，这样就可以反复使用空出来的空间，入队时使用出队空余出来的空间，就解决以上的问题，图解如下：

同样，当head等于tail时，则表示循环队列为空。head和tail也是循环的，像钟表中的时针，具有周期性。这里head和tail需要对长度lenth取模，这样head和tail将一直在长度范围内，可以作为数组的下标。

对于如何将数据分布到相应大小的连续空间中，常用的方式就是取模运算，即position=index%len，利用整数倍的周期性，将剩余的部分作为空间索引。

三.源码分析

1. ArrayDeque数据域

/**
* The array in which the elements of the deque are stored.
* The capacity of the deque is the length of this array, which is
* always a power of two. The array is never allowed to become
* full, except transiently within an addX method where it is
* resized (see doubleCapacity) immediately upon becoming full,
* thus avoiding head and tail wrapping around to equal each
* other.
We also guarantee that all array cells not holding
* deque elements are always null.
*/
transient Object[] elements; // non-private to simplify nested class access
/**
* The index of the element at the head of the deque (which is the
* element that would be removed by remove() or pop()); or an
* arbitrary number equal to tail if the deque is empty.
*/
transient int head;
/**
* The index at which the next element would be added to the tail
* of the deque (via addLast(E), add(E), or push(E)).
*/
transient int tail;
/**
* The minimum capacity that we'll use for a newly created deque.
* Must be a power of 2.
*/
private static final int MIN_INITIAL_CAPACITY = 8;

首先看下ArrayDeque持有的成员域，其中非常核心的是elements，head，tail三个。下面逐一介绍：

elements: 该数组用于存储队列元素，且是大小总是2的幂次方（后面会介绍为什么？）。这个数组不会满容量，会在add方法中扩容，使得头head和tail不会缠绕在一起（即head增长或不会超过tail，head减小时不会溢出到tail），这里队列长度是2的幂次方的原因后续会阐明；
head: 双端队列的头位置，出队时或者弹出栈时的元素位置，加入双端队列头端元素位置，表示当前头元素位置；
tail:双端队列的尾，入队和进栈时的元素位置，加入双端队列尾端的下个元素的索引，tail位总是空的；
MIN_INITIAL_CAPACITY:最小的初始化容量

2. 构造函数

/**
* Constructs an empty array deque with an initial capacity
* sufficient to hold 16 elements.
*/
public ArrayDeque() {
elements = new Object[16];
}
/**
* Constructs an empty array deque with an initial capacity
* sufficient to hold the specified number of elements.
*
* @param numElements
lower bound on initial capacity of the deque
*/
public ArrayDeque(int numElements) {
allocateElements(numElements);
}
/**
* Constructs a deque containing the elements of the specified
* collection, in the order they are returned by the collection's
* iterator.
(The first element returned by the collection's
* iterator becomes the first element, or <i>front</i> of the
* deque.)
*
* @param c the collection whose elements are to be placed into the deque
* @throws NullPointerException if the specified collection is null
*/
public ArrayDeque(Collection<? extends E> c) {
allocateElements(c.size());
addAll(c);
}

第一个默认的无参构造函数：创建初始化大小为16的队列
第二个构造函数：根据参数numElements创建队列，如果numElements小于8，则队列初始化大小为8；如果numElements大于8，则初始化大小为大于numElements的最小2的幂次方。如：numElements=17，则初始化大小为32
第三个构造函数：根据集合元素创建队列，初始化大小为大于集合大小的最小2的幂次方

这里重点看下第二个构造器的过程。其中调用allocateElements(numElements)方法，该方法用来实现容量分配，下面看下内部具体实现：

/**
* Allocates empty array to hold the given number of elements.
*
* @param numElements
the number of elements to hold
*/
private void allocateElements(int numElements) {
int initialCapacity = MIN_INITIAL_CAPACITY;
// Find the best power of two to hold elements.
// Tests "<=" because arrays aren't kept full.
if (numElements >= initialCapacity) {
initialCapacity = numElements;
initialCapacity |= (initialCapacity >>>
1);
initialCapacity |= (initialCapacity >>>
2);
initialCapacity |= (initialCapacity >>>
4);
initialCapacity |= (initialCapacity >>>
8);
initialCapacity |= (initialCapacity >>> 16);
initialCapacity++;
if (initialCapacity < 0)
// Too many elements, must back off
initialCapacity >>>= 1;// Good luck allocating 2 ^ 30 elements
}
elements = new Object[initialCapacity];
}

首先判断指定大小numElements与MIN_INITIAL_CAPACITY的大小关系。如果小于MIN_INITIAL_CAPACITY，则直接分配大小为MIN_INITIAL_CAPACITY的数组；如果大于MIN_INITIAL_CAPACITY，则进行无符号右移操作，然后在加1，这样就可以寻找到大于numElements的最小2的幂次方。
原理：无符号右移再进行按位或操作，就是将其低位全部补成1，然后再自加加一次，就是再向前进一位。这样就能得到其最小的2次幂。之所以需要最多移16位，是为了能够处理大于2^16次方数。

最后再判断值是否小于0，因为如果初始值在int最大值2^31-1和2^30之间，进行一系列移位操作后将得到int最大值，再加1，则溢出变成负数，所以需要检测临界值，然后再右移1位！！！

接下来再来分析下ArrayDeque的几个重要双端操作。对于双端队列有哪些重要的双端操作，可以移步至我的之前写的另一篇文章Java中Deque特性及API

在详细介绍ArrayDeque的重要API实现之前，以图解的方式看下ArrayDeque构造函数初始化出的队列的数据结构：

初始化ArrayDeque后，head和tail都是0，指向数组的0下标位置。在了解初始化后的数据构成后，再首先来看下addFirst方法

3. 重要行为

addFirst方法

/**
* Inserts the specified element at the front of this deque.
*
* @param e the element to add
* @throws NullPointerException if the specified element is null
*/
public void addFirst(E e) {
if (e == null)
throw new NullPointerException();
elements[head = (head - 1) & (elements.length - 1)] = e;
if (head == tail)
doubleCapacity();
}

先用图解的方式分析下这个方法，在第一次调用这个方法后，数据变化如下：

根据图的变化来分析下代码实现。
首先判断插入元素是否为空，再计算即将插入的位置，计算出后将元素赋值给相应的槽位，最后再判断队列容量进行扩容。

将数组的高位端作为双端队列的头部，将低位作为双端队列尾部。没从头部加入一个元素时，head头逆时针向tail尾方向移动一个位置，实现上即将head减1后对数组的最大下标按位与运算。这里就利用了2的幂次方的特性，队列容量设置为2的幂次方后，数组的最大下标位置等于2的幂次方减1，在二进制表示时，就是所有二进制位都是1。这样head位置减1后与其进行按位与运算就能得到头部插入的位置。
当head等于tail时，就表示队列已经满了。这时需要进行扩容。

下面再来看下扩容策略：

/**
* Doubles the capacity of this deque.
Call only when full, i.e.,
* when head and tail have wrapped around to become equal.
*/
private void doubleCapacity() {
assert head == tail;
int p = head;
int n = elements.length;
int r = n - p; // number of elements to the right of p
int newCapacity = n << 1;
if (newCapacity < 0)
throw new IllegalStateException("Sorry, deque too big");
Object[] a = new Object[newCapacity];
System.arraycopy(elements, p, a, 0, r);
System.arraycopy(elements, 0, a, r, p);
elements = a;
head = 0;
tail = n;
}

按照2倍方式扩容
扩容后，将原队列中从头部插入的元素即head右边元素从扩容后新数组的0位置开始排放，然后将左边的元素紧接着排放进新数组。
将head置0，tail置成扩容前数组长度。

如果从头端插入，则head继续逆时针旋转方式插入新元素。从以上图中不难看出addFirst是操作双端队列头端，且是逆时针方式旋转插入。接下来再看看从尾端插入的过程

addLast方法

/**
* Inserts the specified element at the end of this deque.
*
* <p>This method is equivalent to {@link #add}.
*
* @param e the element to add
* @throws NullPointerException if the specified element is null
*/
public void addLast(E e) {
if (e == null)
throw new NullPointerException();
elements[tail] = e;
if ( (tail = (tail + 1) & (elements.length - 1)) == head)
doubleCapacity();
}

上述的addFirst是逆时针的插入方式，addLast刚好与其相反，即顺时针方向插入，且tail表示的是下一个插入的元素的位置。

判断元素是否为空，然后直接将元素插入tail槽位
然后tail向后移动一位，再按位与（控制循环）作为新的tail槽位
判断新的tail槽位是否与head相等，然后依此进行扩容（这里扩容与上述扩容过程一样，不再赘述）。

pollFirst方法

public E pollFirst() {
int h = head;
@SuppressWarnings("unchecked")
E result = (E) elements[h];
// Element is null if deque empty
if (result == null)
return null;
elements[h] = null;
// Must null out slot
head = (h + 1) & (elements.length - 1);
return result;
}

取出头元素，如果头元素为空，则返回null
否则，将头元素槽位置为空（因为pollFirst是移除操作）
再将head顺时针向后移动一位，即加1再和数组最大下标按位与计算出新的head

注：读到这里，相信读者已经已经对双端队列的数据结构已经非常清晰，即双端操作的数组，tail向前（顺时针）移动即从尾端插入元素或者向后移动即从尾端移除元素，head向后（逆时针）移动即从头端插入元素或者向前移动即从头端移除元素。这几个过程正好具有FIFO和LIFO的特点，所以ArrayDeque既可以作为队列Queue又可以作为栈Stack。

pollLast方法

public E pollLast() {
int t = (tail - 1) & (elements.length - 1);
@SuppressWarnings("unchecked")
E result = (E) elements[t];
if (result == null)
return null;
elements[t] = null;
tail = t;
return result;
}

从以上描述的ArrayDeque的数据结构和tail的含义中，可以大致思考下，从尾端移除元素的过程。

先将tail向后（逆时针）移动一位，然后对数组最大下标按位与计算出将要移除元素的槽位
取出计算出的槽位中元素，判断是否为空，为空则返回null
如果不为空，则将该槽位置为空，将槽位下标作为新的tail

以上的过程基就是ArrayDeque的工作原理的最基本实现，其他的行为大都是基于这些过程实现：

offer方法：内部调用offerLast插入元素，返回插入结果true/false
add方法：内部调用addLast实现
poll方法：内部调用pollFirst实现
remove方法：内部调用removeFirst实现
peek方法：内部调用peekFirst实现
element方法：内部调用getFirst实现
pop方法：内部调用addFirst实现
push方法：内部调用removeFirst实现

这里不再详述每个操作的具体实现，因为这些操作都是基于addFirst、addLast、pollFirst和pollLast实现。具体调用这些基础行为实现的细节，读者可以阅读ArrayDeque源码。