数据结构 - ArrayDeque 双向数组队列

简介

优先级队列只支持从一段取数据，内部结构是数组，但是必须符合二叉堆，每次取数据都会伴随上移下移，如果我们元素不不需要排序，有没有更好的队列呢？ArrayDeque 就能满足这个需要，并且它可以在两端方数据和取数据，内部也是用数组实现。

ArrayDeque 类

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

ArrayDeque 继承AbstractCollection抽象类，并且实现Deque接口

ArrayDeque 属性

// 元素数组，长度为2的幂
transient Object[] elements;
// 头指针
transient int head;
// 尾指针
transient int tail;
// 最小长度
private static final int MIN_INITIAL_CAPACITY = 8;

ArrayDeque 构造函数

public ArrayDeque() {
    elements = new Object[16];
}
public ArrayDeque(int numElements) {
    allocateElements(numElements);
}
public ArrayDeque(Collection<? extends E> c) {
    allocateElements(c.size());
    addAll(c);
}
private void allocateElements(int numElements) {
    elements = new Object[calculateSize(numElements)];
}
private static int calculateSize(int numElements) {
    // 取默认最小值为初始值
    int initialCapacity = MIN_INITIAL_CAPACITY;
    if (numElements >= initialCapacity) {
        // 大于8则找最接近2的n次幂
        initialCapacity = numElements;
        // 5次位移可以得到2的n次幂减1
        initialCapacity |= (initialCapacity >>>  1);
        initialCapacity |= (initialCapacity >>>  2);
        initialCapacity |= (initialCapacity >>>  4);
        initialCapacity |= (initialCapacity >>>  8);
        initialCapacity |= (initialCapacity >>> 16);
        // 加1得到2的n次幂
        initialCapacity++;
        // 传2的n次幂会有问题，最终的值是2的n+1次幂
        if (initialCapacity < 0)   
            initialCapacity >>>= 1;
    }
    // 返回的是初始值
    return initialCapacity;
}

是否还记得HashMap中初始长度求最小2的幂？calculateSize中那一长串也是这个作用。可以看出初始数组长度默认16，最小不能小于8，如果传2的n次幂，最终长度是2的n+1次幂，HashMap中为了解决这个问题先减1在位移

ArrayDeque 添加

public void addFirst(E e) {
    if (e == null)
        throw new NullPointerException();
    // 从最后一位开始依次向前添加元素
    elements[head = (head - 1) & (elements.length - 1)] = e;
    // 当head==tail时进行扩容
    if (head == tail)
        doubleCapacity();
}

很多人在看head = (head - 1) & (elements.length - 1)时会比较晕，这里细说一下，elements.length一定是2的n次幂不用多说，转换为二进制就是n+1位为1，其他位为0，那么elements.length - 1呢？从右往左n位都是1。举例elements.length为16，第一次添加时head=0 head - 1 = -1 （1的反码再取补码）转为二进制32个1，32个1和15取位于结果就是15；第二次添加时head=15 head - 1 = 14 转为二进制 1110，1110 & 1111结果为1110 （14），实际上head = (head - 1) & (elements.length - 1)就是最后一位开始递减

public void addLast(E e) {
    if (e == null)
        throw new NullPointerException();
    // 从第一位开始依次添加元素
    elements[tail] = e;
    // 扩容，下面会说怎么计算的
    if ( (tail = (tail + 1) & (elements.length - 1)) == head)
        doubleCapacity();
}

tail = (tail + 1) & (elements.length - 1)也是同样的道理，实际上就是从第一位开始累加，而(tail = (tail + 1) & (elements.length - 1)) == head，就是前后指针是否相同了。这里为什么不用tail + 1？这里是考虑head值为0的情况，设elements.length = 16，当head为0，tail当前值为15时实际上数组这时已经满了，但是怎么判断数组满了呢?tail + 1 = 16, elements.length - 1 = 15， head = 0，那么10000 & 1111 = 00000000 == head，这里是一处非常巧妙的做法，简单一行做了很多事 将tail+1的同时还能判断数组有没有满，与运算又能提高程序效率。需要注意的是，这里是把元素放在tail位置之后再把tail+1的，也就是说tail下标位置是没有值的，也就是含头不含尾

ArrayDeque 扩容

private void doubleCapacity() {
    assert head == tail;
    int p = head;
    int n = elements.length;
    int r = n - p;
    // 将数组长度扩大2倍
    int newCapacity = n << 1;
    // 如果扩容后超出int最大值则抛出异常
    if (newCapacity < 0)
        throw new IllegalStateException("Sorry, deque too big");
    Object[] a = new Object[newCapacity];
    // 将head后面的元素拷贝到新数组的开始位置
    System.arraycopy(elements, p, a, 0, r);
    // 将head前面的元素拷贝到新数组的开始位置
    System.arraycopy(elements, 0, a, r, p);
    elements = a;
    head = 0;
    tail = n;
}

ArrayDeque 扩容是原数组长度扩大一倍

ArrayDeque 删除

// 将队列首部的元素取出并移除
public E removeFirst() {
    E x = pollFirst();
    // x==null，说明队列为空
    if (x == null)
        throw new NoSuchElementException();
    return x;
}
// 将队列尾部的元素取出并移除
public E removeLast() {
    E x = pollLast();
    // x==null，说明队列为空
    if (x == null)
        throw new NoSuchElementException();
    return x;
}

ArrayDeque 出队

// 将队列首部的元素取出并移除
public E pollFirst() {
    int h = head;
    // 将队列头部的元素赋值给result
            E result = (E) elements[h];
    // result为null说明队列为空
    if (result == null)
        return null;
    // 将头部元素置空
    elements[h] = null;
    // 将头部指针向右移一位
    head = (h + 1) & (elements.length - 1);
    return result;
}
// 将队列尾部元素取出并移除
public E pollLast() {
    // 当tail>0时，直接取tail - 1位置元素，tail位置为null
    // 当tail=0时，取elements.length - 1处元素
    int t = (tail - 1) & (elements.length - 1);
    E result = (E) elements[t];
    // result为null说明队列为空
    if (result == null)
        return null;
    // 将头部元素置空
    elements[t] = null;
    // 将取出到的元素位置索引赋给tail，tail处值为null，含头不含尾
    tail = t;
    return result;
}

removeFirst，removeLast 这两个方法也是移除并返回元素，和pollFirst不同的是该接口会判断返回的值是否为null，如果为null，就抛出异常。也就是说，该方法不允许要移除的元素为null。还有两个方法，peekFirst，peekLast也是返回头元素或尾元素，只是不移除元素。

数据结构 - ArrayDeque 双向数组队列

原文：https://www.cnblogs.com/yuanjiangnan/p/12653491.html