• 这次来说一下ArrayDeque,我们先看一下他的类关系图,其中忽略掉了一些标记性接口

• 我们看一下类的定义

  public class ArrayDeque<E> extends AbstractCollection<E>
                             implements Deque<E>, Cloneable, Serializable
  {...}

• 从中我们可以看到他实现了Deque接口,那么Deque是实现了Queue<E>接口,如下是两个接口中的部分方法

  Queue:
    boolean add(E e);
    boolean offer(E e);
    E remove();
    E poll();
    E element();
    E peek();
  Deque:
    void addFirst(E e);
    void addLast(E e);
    boolean offerFirst(E e);
    boolean offerLast(E e);
    E removeFirst();
    E removeLast();
    E pollFirst();
    E pollLast();
    ...

• 从上面我们就可以看到在Queue接口中只定义了关于队列的一些方法,一方进一方出,而在Deque中出现了xxFirst&xxLast一些操作方法,这样我们通过这些方法就不止可以进行队列的操作了,并且同时也支持了栈的操作,那么我们也注意到addFirst&addLast方法,能够在一个队列中的头尾都进行操作元素,所以ArrayDeque类可以支持双端队列和栈的所有操作
• 了解完他的继承实现关系,那么我们就正式的来看一下他的源码实现

属性

//保存元素的数组
transient Object[] elements;
//头指针
transient int head;
//尾指针
transient int tail;
//容量限制
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

• 从上我们就可以看到,ArrayDeque的实现依旧是采用了数组实现,并且有一定的容量限制,我们接着往下看

构造

• 构造方法依旧是三个,分别是无参的,有初始化容量的,和以集合为参数创建实例的三种构造方法

  public ArrayDeque() {
      elements = new Object[16];
  }

• 默认构造的默认容量为16,接着看其他的构造方法

  public ArrayDeque(int numElements) {
    //如果参数小于1,那么就以1为默认初始化容量,否则再去比较容量是否等于Integer.MAX_VALUE
    //是的话就以Integer.MAX_VALUE为容量,否则就是参数值+1作为默认容量
      elements =
          new Object[(numElements < 1) ? 1 :
                     (numElements == Integer.MAX_VALUE) ? Integer.MAX_VALUE :
                     numElements + 1];
  }

• 如上可以看到,即使我们传入了一些非法的参数,比如是负数情况下,ArrayDeque依旧是不会报错的,并且我们得知了,ArrayDeque的最大初始化容量就是 Integer.MAX_VALUE,如果既不是负数也不是最大值,那么就是以你参数+1作为长度进行初始化,为什么会将传入参数加一处理,因为如果你是参数为1的话,他加一处理后会常见两个长度的数组,此时head和tail都是指向0.而第二个null总是留给tail去用的

• 下面是以集合为参数的构造方法

  public ArrayDeque(Collection<? extends E> c) {
    //调用上面分析的构造方法,以集合元素个数为默认初始化容量
      this(c.size());
      //将集合中元素拷贝到数组中
      copyElements(c);
  }
  private void copyElements(Collection<? extends E> c) {
    //forEach是循环的方法,然后 :: 操作符是Java8新增的,所以这的意思是
    //将集合中元素遍历,并且依次调用本类的addLast方法添加到数组中
    //至于具体的addLast,我们马上就开始分析
      c.forEach(this::addLast);
  }

问题

• 我们之前知道了ArrayDeque是一个双端队列的实现,并且本类的实现是依靠数组的,那么我们就会想到这样的一个问题,当一个数组中被填充了一个元素,这时候head肯定是指向数组的下标0元素的,那么我们此时将头元素取出,然后数组index=0位置的元素就为null了,那么此时head必定会往后移一位,指向下一个元素,那么此时在添加tail指向肯定也是一步步往后移,那么之前释放掉的index=0的元素位置不就浪费了吗 ? 我们来看图来解释这个问题

• 图应该说的很明白了,所以我们现在遇到了这样的一个浪费的问题,那么ArrayDeque给出的解决方案就是将数组作为一个逻辑上的循环数组使用,当head后移导致前面为null时,并且tail到达一个数组的最后位置,那么就去检查head前面的位置是否有空闲的,因为取出都是从head取,所以不会出现断断续续有数据的情况,所以他就要去判断数组位置是否为null,所以ArrayDeque是不允许插入null元素的

• 看图之后我们知道了大概的思路,所以我们知道了head不会总是0的,tail也不一定总是大于head的,那么对于ArrayDeque最终是怎么实现调整的,我们来看他的源码实现
• 鉴于方法太多,我们就挑出最核心的方法说

add

public boolean add(E e) {
  //默认将元素添加到数组最后面
    addLast(e);
    return true;
}
public void addLast(E e) {
    if (e == null)
        throw new NullPointerException();
    //保存引用
    final Object[] es = elements;
    //tail的实现保证永远指向最后一个元素的下一个null位置
    //所以可以直接进行插入
    es[tail] = e;
    //这个方法可以说是很巧妙了,主要目的是在于判断是否还有空余位置插入元素
    //是否需要扩容,并且还确定tail的指向
    if (head == (tail = inc(tail, es.length)))
        grow(1);
}
static final int inc(int i, int modulus) {
    if (++i >= modulus) i = 0;
    return i;
}

• 理解inc方法有点不容易,所以我们画图来说

• 从上图,我们就非常清楚了inc的方法的巧妙,也清楚了add方法的流程

分清数组的First和Last

ArrayDeque<String> stringArrayDeque = new ArrayDeque<>(4);
stringArrayDeque.addFirst("1");
stringArrayDeque.addLast("2");
sys(stringArrayDeque); //输出方法

• 结果

  [2, null, null, null, 1]

• 所以数组的<-这边是Last,相反则是First

addFirst

public void addFirst(E e) {
    if (e == null)
        throw new NullPointerException();
    final Object[] es = elements;
    //直接使用方法计算位置然后出入
    es[head = dec(head, es.length)] = e;
    if (head == tail)  //数组满了
        grow(1);//扩容
}
static final int dec(int i, int modulus) {
    if (--i < 0) i = modulus - 1;
    return i;
}

• 经过了inc方法,dec方法我们看着就容易理解多了,其目的就是寻找head的插入位置,上图

• OK到这我们就完全了解了他们的实现了, 然后其中涉及到的grow方法我们没有说,下来我们来看一下

grow

private void grow(int needed) {
    final int oldCapacity = elements.length;
    int newCapacity;
    // 如果容量小,则增加一倍,否则增加50%
    int jump = (oldCapacity < 64) ? (oldCapacity + 2) : (oldCapacity >> 1);
    //如果需要增加的容量比指定需要增长的容量小
    //或者
    //之前的容量加上需要增加的容量后的  总容量大于数组最大容量
    if (jump < needed || (newCapacity = (oldCapacity + jump)) - MAX_ARRAY_SIZE > 0)
        newCapacity = newCapacity(needed, jump);
    //确定后开始拷贝
    final Object[] es = elements = Arrays.copyOf(elements, newCapacity);
    // Exceptionally, here tail == head needs to be disambiguated
    //如果tail和head之间还有位置
    //或者数组满了和排除是初始化状态的数组
    if (tail < head || (tail == head && es[head] != null)) {
        //新增容量
        int newSpace = newCapacity - oldCapacity;
        //将数组内元素整理一下
        System.arraycopy(es, head,
                         es, head + newSpace,
                         oldCapacity - head);
        //将之前的元素置空
        for (int i = head, to = (head += newSpace); i < to; i++)
            es[i] = null;
    }
}
//边缘条件下的容量计算,特别是溢出
private int newCapacity(int needed, int jump) {
    final int oldCapacity = elements.length, minCapacity;
    //总容量大于数组最大容量
    if ((minCapacity = oldCapacity + needed) - MAX_ARRAY_SIZE > 0) {
      //达到上限,报错
        if (minCapacity < 0)
            throw new IllegalStateException("Sorry, deque too big");
        //返回最大容量
        return Integer.MAX_VALUE;
    }
    //到这就代表没有超过限制
    //如果指定需要增长的大于方法计算出来的需要增长的容量
    if (needed > jump)
    //就返回之前容量和指定增加的容量的和
        return minCapacity;
    //否则如果没有超过限制,就返回之前容量和计算出来的容量之和,否则就返回数组上限值
    return (oldCapacity + jump - MAX_ARRAY_SIZE < 0)
        ? oldCapacity + jump
        : MAX_ARRAY_SIZE;
}

• 好了大概的逻辑我们就清楚了,实现扩容并不是只根据参数进行扩容而是进行多方面考虑,比如数组的大小

addAll

public boolean addAll(Collection<? extends E> c) {
    final int s, needed;
    //deque中的元素数加上集合中的元素数加上永远保证的一个null空间之和减去
    //数组的长度,如果大于0表名数组不够,进行grow,否则就不grow
    if ((needed = (s = size()) + c.size() + 1 - elements.length) > 0)
        grow(needed);
    //循环拷贝进去
    copyElements(c);
    return size() > s;
}
//返回此deque中的元素数
public int size() {
    return sub(tail, head, elements.length);
}
static final int sub(int i, int j, int modulus) {
  //判断是否是tail与head有null,让后分情况处理
    if ((i -= j) < 0) i += modulus;
    return i;
}

• 到这add方法基本即结束了,下面是删除方法,删除方法有remove和poll,两者的区别在之前的文章提到过了,在这我就只分析一下remove好了

remove

public E remove() {
    return removeFirst();
}
public E removeFirst() {
    //还是调用了poll方法...
    E e = pollFirst();
    //其实poll方法跟remove方法只是缺了这个判断
    if (e == null)
        throw new NoSuchElementException();
    return e;
}
public E pollFirst() {
    final Object[] es;
    final int h;
    //返回数组索引i处的元素
    E e = elementAt(es = elements, h = head);
    //返回的元素不为null
    if (e != null) {
        //将它设置为null
        es[h] = null;
        //inc方法返回head下一个元素位置
        head = inc(h, es.length);
    }
    //返回元素
    return e;
}
//实现简单
static final <E> E elementAt(Object[] es, int i) {
    return (E) es[i];
}

• 还有根据OBject对象删除了,无非就是for循环去找,判断相等的办法是equals
• 对于removeLast的实现就是采用了pollLast方法,里面的核心实现肯定一样,不同的是它使用dec方法,将tail做参数返回位置,别的其他都一样
• 删除了方法还有delete,方法的区别是,i位置被删除后,元素后的整体会迁移
• 还有适应Java8出现的一些lambda方法,比如removeIf,参数是Predicate函数接口,如果你了解lambda你就会知道这个怎样用了
• add方法是默认在last添加元素,而remove是在first删除,所以这两个方法就构成了一个队列的操作
• 下面介绍的push.pop就构成了一个栈的操作

push

• 没啥可说的了,都分析过了

  public void push(E e) {
      addFirst(e);
  }
  public void addFirst(E e) {
      if (e == null)
          throw new NullPointerException();
      final Object[] es = elements;
      es[head = dec(head, es.length)] = e;
      if (head == tail)
          grow(1);
  }

pop

• 也没啥可说的了

  public E pop() {
      return removeFirst();
  }
  //调用关系自己看一下吧 ,上面也有贴源码

• 所以到这我就将一核心办法给写了一下,当然这完全是自己的分析,也是第一次看,所以不对的地方请指正,谢谢您

总结

• 那么今天的分析比较令自己惊讶的地方就是inc这个方法,真的是十分的巧妙,而对于其他操作,只要了解一下堆栈是啥再继续在本子上画画图就出来了,那么今天介绍的ArrayDeque是一个数组实现,有容量,不是线程安全,好像已经把他概括完了...
• 对了, 源注释介绍本类的时候, 告诉了我们使用这个类比Stack和LinkedList要快