一：类的继承关系

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]; }

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

四：几个构造函数

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

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

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