[源码探究]ArrayDeque双端队列使用&实现原理分析

作者: CODING技术小馆 | 来源:发表于2021-04-12 10:13 被阅读0次

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位置示例如下图所示：

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()方法，进行数据出队列时，其数据的删除示意图如下图所示：

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()方法，进行数据出队列时，其数据的删除示意图如下图所示：

enter description here

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双端队列使用&实现原理分析

ArrayDeque双端队列使用&实现原理分析

一、Deque

二、ArrayDeque 源码学习

2.1、变量说明

2.2、构造方法

2.3、队列首部添加元素

2.4、队列首部删除元素

2.5、队列尾部添加元素

2.6、队列尾部移除元素

2.7、扩容 doubleCapacity()

三、ArrayDeque 队列应用

3.1 入队列

3.2 出队列

四、ArrayDeque 堆栈应用

4.1 入堆栈

4.2 出堆栈

参考

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

[源码探究]ArrayDeque双端队列 使用&实现原理分析

ArrayDeque双端队列 使用&实现原理分析

一、Deque

二、ArrayDeque 源码学习

2.1、变量说明

2.2、构造方法

2.3、队列首部添加元素

2.4、队列首部删除元素

2.5、队列尾部添加元素

2.6、队列尾部移除元素

2.7、扩容 doubleCapacity()

三、ArrayDeque 队列应用

3.1 入队列

3.2 出队列

四、ArrayDeque 堆栈应用

4.1 入堆栈

4.2 出堆栈

参考

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

[源码探究]ArrayDeque双端队列使用&实现原理分析

ArrayDeque双端队列使用&实现原理分析