ArrayDeque使用&实现原理分析

学习Okhttp实现源码时，发现其任务分发时用到了ArrayDeque。因此了解一下ArrayDeque的使用方式和实现原理。

一、Deque

deque（double-ended queue）双端队列，是一种具有队列和栈的性质的数据结构。

双端队列中的元素可以从两端弹出，其限定插入和删除操作在表的两端进行。假设两端分别为端点A和端点B，在实际应用中：

可以有输出受限的双端队列（即端点A允许插入和删除，端点B只允许插入的双端队列）；
可以有输入受限的双端队列（即端点A允许插入和删除，端点B只允许删除的双端队列）；
如果限定双端队列从某个端点插入的元素只能从该端点删除，则该双端队列就蜕变为两个栈底相邻的栈；

deque（double-ended queue）也是一种队列，了解deque时首先需要回忆一下queue的使用和实现原理。

对于Queue（先进先出）的详细使用方式和实现原理，可参考文章：

BlockingQueue使用方式及源码阅读

 https://blog.csdn.net/xiaxl/article/details/80774479

Deque实现了以下功能方法，供开发者使用：

// 源码来自：android-29/java/util/Deque

public interface Deque<E> extends java.util.Queue<E> {

/**

 * 添加元素

 */

 // 在队列前边 添加元素，返回是否添加成功

boolean offerFirst( E e);

// 在队列后边 添加元素，返回是否添加成功

boolean offerLast( E e);

// 在队列前边 添加元素

void addFirst(E e);

// 在队列后边添加元素

void addLast( E e);

/**

 * 删除元素

 */

 // 删除第一个元素，返回删除元素的值；如果元素为null，将返回null；

E pollFirst();

// 删除最后一个元素，返回删除元素的值；如果为null，将返回null；

E pollLast();

// 删除第一个元素，返回删除元素的值；如果元素为null，将抛出异常；

E removeFirst();

// 删除最后一个元素，返回删除元素的值；如果为null，将抛出异常；

E removeLast();

// 删除第一次出现的指定元素

boolean removeFirstOccurrence( java.lang.Object o);

// 删除最后一次出现的指定元素

boolean removeLastOccurrence( java.lang.Object o);

/**

 * 取数据

 */

// 获取第一个元素，没有返回null；

E peekFirst();

// 获取最后一个元素，没有返回null；

E peekLast();

// 获取第一个元素,如果没有则抛出异常;

E getFirst();

// 获取最后一个元素，如果没有则抛出异常；

E getLast();

/**

 * 队列方法------------------------------------------

 */

// 向队列中添加一个元素。若添加成功则返回true；若因为容量限制添加失败则返回false是。

boolean offer(E e);

// 删除队列头的元素，如果队列为空，则返回null；

E poll();

// 返回队列头的元素，如果队列为空，则返回null；

E peek();

// 向队列中添加一个元素。若添加成功则返回true；若因为容量限制添加失败，则抛出IllegalStateException异常。

boolean add(E e);

// 删除队列头的元素，如果队列为空，则抛出异常；

E remove();

// 返回队列头的元素，如果队列为空，将抛异常；

E element();

/**

 * 堆栈方法------------------------------------------

 */

// 栈顶添加一个元素

void push( E e);

// 移除栈顶元素,如果栈顶没有元素将抛出异常

E pop();

}

二、ArrayDeque 源码学习

2.1、变量说明

// 源码来自：android-29/java/util/ArrayDeque

// 用数组存放队列元素；

transient Object[] elements;

// 头部index

transient int head;

// 下一个要添加到尾步的index (除tail=0时，当前的尾部为tail-1)；

transient int tail;

head 与 tail 对应的index位置示例如下图所示：

addFirst 方法：在队列前面添加元素；

代码实现中：从数组的末尾向前添加数据，如上图添加顺序为 E1、E2、...；
addLast方法：在队列后面添加元素；

代码实现中：在数组的前边向后添加数据，如上图添加顺序为 Ea、Eb、...；
head 为当前头部的index；
tail 为下一个要添加的尾部的index；

2.2、构造方法

// 源码来自：android-29/java/util/ArrayDeque

// 构造方法：默认数组长度为8

public ArrayDeque() {

    // 创建一个长度为16的数组

    elements = new Object[16];

}

// 构造方法：根据自定义长度 分配数组空间

public ArrayDeque(int numElements) {

    // 根据输入长度 分配数组空间

    allocateElements(numElements);

}

// 找到大于需要长度的最小的2的幂整数

private void allocateElements(int numElements) {

	// MIN_INITIAL_CAPACITY为8

    int initialCapacity = MIN_INITIAL_CAPACITY;

	// 假设用户输入的为9

    if (numElements >= initialCapacity) {

		// initialCapacity = 9;

        initialCapacity = numElements;

		// initialCapacity = 9 | ( 9 >>> 1)

		// initialCapacity = ( 1001 ) | ( 0100 ) = 1101 = 13;

        initialCapacity |= (initialCapacity >>>  1);

		// initialCapacity = 13 | ( 13 >>> 2)

		// initialCapacity = ( 1101 ) | ( 0011 ) = 1111 = 15;

        initialCapacity |= (initialCapacity >>>  2);

		// initialCapacity = 15 | ( 15 >>> 4)

		// initialCapacity = ( 1111 ) | ( 0000 ) = 1111 = 15;

        initialCapacity |= (initialCapacity >>>  4);

		// initialCapacity = 15 | ( 15 >>> 8)

		// initialCapacity = ( 1111 ) | ( 0000 ) = 1111 = 15;

        initialCapacity |= (initialCapacity >>>  8);

        initialCapacity |= (initialCapacity >>> 16);

		// 15+1 = 16;

        initialCapacity++;

        if (initialCapacity < 0)    // Too many elements, must back off

            initialCapacity >>>= 1; // Good luck allocating 2^30 elements

    }

	// 创建数组（数组的长度为：大于需要长度的最小的2的幂整数）

    elements = new Object[initialCapacity];

}

以上两个构造方法实现中：

第一个构造方法，创建一个默认长度为8的数组；
第二个构造方法，如代码中注释举例，其会通过allocateElements(numElements)将数组的长度定义为2的倍数（找到大于需要长度的最小的2的幂整数）；
allocateElements(numElements)方法：可以将一个任意的初始值转化为2^n的值。

如果本身传进来的值就是2^n 的值，那么经过转化会变成2^(n+1)；

如果传入的值大于等于2^30，那么经过转化会变成负值，即< 0，此时会把初始值设置为2^30，即最大的容量只有2^30；

2.3、队列首部添加元素

offerFirst(E e)、addFirst(E e) 源码实现

// 源码来自：android-29/java/util/ArrayDeque

//  在队列前边 添加元素，返回是否添加成功

public boolean offerFirst(E e) {

    addFirst(e);

    return true;

}

// 在队列前边 添加元素

public void addFirst(E e) {

	// 存入空数据时，抛出异常NullPointerException

    if (e == null)

        throw new NullPointerException();

	// 这样写 当head=0时，添加到的位置为elements.length - 1

	// 从数组的末尾 向前 依次添加数据

    elements[head = (head - 1) & (elements.length - 1)] = e;

	// 空间不足

    if (head == tail)

        doubleCapacity(); // 扩容

}

offerFirst(E e)、addFirst(E e) 在数组前面添加元素：源码实现中，从数组的末尾向前依次添加数据元素；

2.4、队列首部删除元素

pollFirst()、removeFirst()源码实现

// 源码来自：android-29/java/util/ArrayDeque

// 删除第一个元素，返回删除元素的值；如果元素为null，将抛出异常；

public E removeFirst() {

    E x = pollFirst();

	// 若为空，则抛出异常；

    if (x == null)

        throw new NoSuchElementException();

    return x;

}

// 删除第一个元素，返回删除元素的值；如果元素为null，将返回null；

public E pollFirst() {

	// 数组

    final Object[] elements = this.elements;

	// 头部index

    final int h = head;

	// 头部元素

    E result = (E) elements[h];

    // 如果头部元素为null，则返回null

    if (result != null) {

		// 数据元素出队列

        elements[h] = null; // Must null out slot

		// 指向下一个元素

        head = (h + 1) & (elements.length - 1);

    }

    return result;

}

执行pollFirst()、removeFirst()方法，进行数据出队列时，其数据的删除示意图如下图所示：

2.5、队列尾部添加元素

offerLast(E e)、addLast(E e) 源码实现

// 源码来自：android-29/java/util/ArrayDeque

// 在数组后添加元素，返回是否添加成功

public boolean offerLast(E e) {

    addLast(e);

    return true;

}

// 在数组后面添加元素

public void addLast(E e) {

	// 存入空数据时，抛出异常NullPointerException

    if (e == null)

        throw new NullPointerException();

	// 存入数据

    elements[tail] = e;

	// (tail + 1) == head 空间已满

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

		// 扩容

        doubleCapacity();

}

offerLast(E e)、addLast(E e) 在数组后添加元素: 源码实现中，从数组的前端向后依次添加数据元素；

2.6、队列尾部移除元素

pollLast()、removeLast()源码实现

// 源码来自：android-29/java/util/ArrayDeque

// 删除最后一个元素，返回删除元素的值；如果为null，将抛出异常；

public E removeLast() {

    E x = pollLast();

    if (x == null)

        throw new NoSuchElementException();

    return x;

}

// 删除最后一个元素，返回删除元素的值；如果为null，返回null；

public E pollLast() {

	// 数组元素

    final Object[] elements = this.elements;

	// tail-1

    final int t = (tail - 1) & (elements.length - 1);

    // 获取当前元素

    E result = (E) elements[t];

    if (result != null) {

		// 当前元素置空

        elements[t] = null;

		// 将tail-1 赋值给 tail

        tail = t;

    }

    return result;

}

执行pollLast()、removeLast()方法，进行数据出队列时，其数据的删除示意图如下图所示：

2.7、扩容 doubleCapacity()

向数组中添加元素时，若数组容量不足，会调用doubleCapacity()方法，扩容为当前容量的两倍：

// 源码来自：android-29/java/util/ArrayDeque

// 空间不足：扩容

private void doubleCapacity() {

    assert head == tail;

	// 头部 index

    int p = head;

	// 数组长度

    int n = elements.length;

	//

    int r = n - p;

	// 容量扩展为当前的2倍

    int newCapacity = n << 1;

	// 新的容量超过2^30，抛出异常

    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置空，保证其中元素可被垃圾回收

    Arrays.fill(elements, null);

	// elements被重新赋值

    elements = a;

	// header 和tail重新赋值

    head = 0;

    tail = n;

}

扩容后的数组为原始数组空间的两倍：

三、ArrayDeque 队列应用

3.1 入队列

// 向队列中添加一个元素。若添加成功则返回true；若因为容量限制添加失败则返回false是。

boolean offer(E e);

ArrayDeque入队列时：offer会调用offerLast实现入队列

3.2 出队列

// 删除队列头的元素，如果队列为空，则返回null；

E poll();

ArrayDeque出队列时：poll会调用pollFirst实现出队列

四、ArrayDeque 堆栈应用

4.1 入堆栈

// 栈顶添加一个元素

void push( E e);

ArrayDeque入堆栈时：push会调用offerLast实现入堆栈

4.2 出堆栈

// 移除栈顶元素,如果栈顶没有元素将抛出异常

E pop();

ArrayDeque出堆栈时：poll会调用pollFirst实现出堆栈

参考

百度百科deque

https://baike.baidu.com/item/deque/849385?fr=aladdin

巴特西

ArrayDeque使用&实现原理分析