一：类的继承关系

UML图

类的继承关系：

public class ArrayDeque extends AbstractCollection
implements Deque, Cloneable, Serializable

分析：继承自抽象结合类AbstractCollection

           实现超级队列Deque，克隆接口Cloneable, 序列化接口Serializable

二：看下类的成员属性

/**
* 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.
*
* 存放元素的Object[]数组（底层数据结构）
*/
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.
*
* 容量最小值，2的次幂，默认为8
*/
private static final int MIN_INITIAL_CAPACITY = 8;

三：接着先认识下allocateElements(int numElements)方法

/**
* Allocates empty array to hold the given number of elements.
*
* @param numElements the number of elements to hold
*
* 寻找numElements的最近的二次幂值initialCapacity
* new一个长度为initialCapacity的新Object[]数组
*/
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\];  

}

分析：这个计算方法参考下面这个链接，讲的挺好

https://www.jianshu.com/p/1c1c3f24762e

四：几个构造函数

1.

/**
* Constructs an empty array deque with an initial capacity
* sufficient to hold 16 elements.
*
* 无参构造函数初始化数组长度为16
*/
public ArrayDeque() {
elements = new Object[16];
}

分析：无参构造方法，初始化一个长度为16的数组

2.

/**
* 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);
}

分析：传入长度，初始为数组长度为大于等于numElements最小2次幂

3.

/**
* 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 front 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 c) {
allocateElements(c.size());
addAll(c);
}

分析：初始化数组长度为大于等于集合长度的最小2次幂，调用addAll()方法

/**
* {@inheritDoc}
*
*

This implementation iterates over the specified collection, and adds
* each object returned by the iterator to this collection, in turn.
*
*

Note that this implementation will throw an
* UnsupportedOperationException unless add is
* overridden (assuming the specified collection is non-empty).
*
* @throws UnsupportedOperationException {@inheritDoc}
* @throws ClassCastException {@inheritDoc}
* @throws NullPointerException {@inheritDoc}
* @throws IllegalArgumentException {@inheritDoc}
* @throws IllegalStateException {@inheritDoc}
*
* @see #add(Object)
*/
public boolean addAll(Collection c) {
boolean modified = false;
for (E e : c)
if (add(e))
modified = true;
return modified;
}

分析：遍历集合，一个个add添加

五：最常用的方法

1.offerLast() 向队尾添加一个元素

/**
* Inserts the specified element at the end of this deque.
*
* @param e the element to add
* @return {@code true} (as specified by {@link Deque#offerLast})
* @throws NullPointerException if the specified element is null
*
* 添加到队尾
*/
public boolean offerLast(E e) {
addLast(e);
return true;
}

分析：传入元素，调用addLast()方法

/**
* Inserts the specified element at the end of this deque.
*
*

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();
//根据下标，队尾值为e
elements[tail] = e;
if ( (tail = (tail + 1) & (elements.length - 1)) == head)
doubleCapacity();
}

分析：这里直接在队尾里添加了元素e，因为ArrayDeque是一个循环队列，所以当队尾和队头重合说明，队列满了，需要进行扩容。

这里要看下这个“&”按位与操作，只有1与上1才得1。

tail = (tail + 1) & (elements.length - 1)) == head

假设我们有这么一个队列：

现在数组下标1、2、3都填满了数字，当我们在队尾tail里赋上8。这时候我们需要判断当前循环队列是否已满

下一个可以插入元素下标应该为：

tail = tail + 1 = 0 + 1 = 1

数组都是2的次幂，所以数组长度 - 1有个规律，从最高为起每一位都是1，例如：

当前leng - 1 = 3，用二进制表示为 0011

与操作

         0001

         0011

等于：0001 

即下标为1，此时与head下标相同，表明数组已满。需要扩容。

如果tail + 1是正数，与操作，相当于取余“%”，例如：我们这个1 % 3 = 1，取余后得到数刚好就是tail的索引下标。

如果是负数的话，这里与操作会得到负数本身。例如在头部添加方法addFrist():

public void addFirst(E e) {
if (e == null)
throw new NullPointerException();
elements[head = (head - 1) & (elements.length - 1)] = e;
if (head == tail)
doubleCapacity();
}

分析：这里分析类似

接下来我们看：扩容操作

/**
* 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;
//头部索引p
int p = head;
//队列长度n
int n = elements.length;
//头部元素右边有多少个元素r包括头部
int r = n - p; // number of elements to the right of p
//队列长度扩大为2倍
int newCapacity = n << 1;
//如果扩大两倍后长度超过了int大小变为负数，则抛错
if (newCapacity < 0)
throw new IllegalStateException("Sorry, deque too big");
//new一个新的数组长度为原来的两倍
Object[] a = new Object[newCapacity];
//旧数组elements 从p头部开始， 新数组a，从0开始， 长度为r。所以是拷贝原数组p右侧数据包括p
System.arraycopy(elements, p, a, 0, r);
//旧数组elements 从下标0开始， 新数组a，从下标r开始， 长度为p。所以是拷贝原数组p左侧数据
System.arraycopy(elements, 0, a, r, p);
//旧数组等于新数组a
elements = a;
//队头索引等于0
head = 0;
//队尾索引等于n，n为旧数组的长度不是最新的数组
tail = n;
}

分析：这里看上面的注释已经将得很清晰了，但是我们这里需要注意一个问题

在数组复制的过程，新数组下标0是从原数组的头部右边数据开始复制的（包括头部），为什么不从原数组头部左边开始复制数据呢？仔细想下，是不是有点奇怪？

其实我们看下图就知道了，

还是这个例子：

其实循环队列的起始位置，就是head所在位置，也就是9所在的位置，它都叫队头了，当然就是起始位置了，扩容后新数组应该为：

2.pollFirst()从头部取出一个元素

public E pollFirst() {
//头部索引等于h
int h = head;
@SuppressWarnings("unchecked")
//检查头部是否有元素
E result = (E) elements[h];
// Element is null if deque empty
if (result == null)
return null;
//令当前位置为null
elements[h] = null; // Must null out slot
//队头索引向递增方向退一位
head = (h + 1) & (elements.length - 1);
return result;
}

到此我们就大概分析了下ArrayDeque

有疑问，扫我二维码添加微信，欢迎骚扰！

坚持做一件事，一起学习。