ArrayDeque详解(含动画演示)

ArrayDeque详解

ArrayDeque是JDK中对双端队列的一种实现。

1、 ArrayDeque的继承体系

可以看到ArrayDeque实现了Collection、Deque，说明是单值集合，且具有双端队列的功能。

小知识点：
Queue 读作 /kjuː/，发音类似于“ cue ”。
Deque 读作 /deɪk/ 或 /dɛk/，发音接近于“deck ”。

2、Queue和Deque接口的区别

• Queue:
  单端队列的抽象，遵循先进先出（FIFO, First In First Out）原则。元素从队尾（rear）加入，从队头（front）移除。
  定义了一组操作队列的规则。
  比如： boolean add(E e); boolean offer(E e); E remove(); E poll(); E element(); E peek();
  单端队列图示：
  

• Deque（双端队列，Double Ended Queue）:
  是Queue的子接口，不仅支持FIFO操作，还支持后进先出（LIFO，类似栈的行为）以及其他灵活的插入和删除操作。元素可以从两端（前端和后端）进行插入和删除。
  也定义了一组操作双端的规则。
  比如： void addFirst(E e); void addLast(E e); E removeFirst(); E removeLast(); 等等
  双端队列图示：
  

应用场景:
Queue常用于需要按顺序处理元素的场景，如任务调度、消息队列等。
Deque因其双端操作的灵活性，适用于更广泛的场景，如作为栈使用（后进先出）、实现撤销/重做功能、以及任何需要在两端高效插入和删除的场合。

3、 ArrayDeque的数据结构

先看下ArrayDeque类的属性注释：

可以看出ArrayDeque底层使用Object[]数组来存储元素。

// 使用可变数组实现的双端队列ArrayDeque
public class ArrayDeque<E> {

    // 用于存储队列元素的数组，transient表示序列化时不包括该字段
    transient Object[] elements; // 非私有化以简化嵌套类的访问

    // 队列头部的位置索引
    transient int head;

    // 队列尾部的位置索引
    transient int tail;

    // 如果自定义容量小于8  则使用8作为最小容量初始化数组
    private static final int MIN_INITIAL_CAPACITY = 8;

    // 构造函数和其他方法实现...
}

4、ArrayDeque的构造方法

• ①、无参构造

public ArrayDeque() {
    // 初始化一个默认容量为16的数组
    elements = new Object[16];
}

如果使用无参构造，初始容量就是16。

• ②、带参构造1，接收一个自定义容量

public ArrayDeque(int numElements) {
    // 调用 allocateElements 方法分配数组空间
    allocateElements(numElements);
}

private void allocateElements(int numElements) {
    // 初始化初始容量为 8
    int initialCapacity = MIN_INITIAL_CAPACITY;

    // 如果 numElements 大于初始容量，则找到最合适的2的幂次方作为容量
    if (numElements >= initialCapacity) {
        initialCapacity = numElements;
        // 下面的代码通过位运算将 initialCapacity 调整为大于 numElements 的最小2的幂次方
        initialCapacity |= (initialCapacity >>>  1);
        initialCapacity |= (initialCapacity >>>  2);
        initialCapacity |= (initialCapacity >>>  4);
        initialCapacity |= (initialCapacity >>>  8);
        initialCapacity |= (initialCapacity >>> 16);
        initialCapacity++;

        // 检查是否溢出，如果溢出，则将 initialCapacity 右移一位
        // 当 initialCapacity 超过某个极限时，处理起来会非常困难甚至是不可能的。
        // 通过右移一位，代码试图回退到一个可以实际处理的大小（大约 2^30），这是一种防止极端情况下内存分配失败的保护措施。
        if (initialCapacity < 0)
            initialCapacity >>>= 1; // Good luck allocating 2 ^ 30 elements

    }
    // 创建一个指定容量的数组
    elements = new Object[initialCapacity];
}
    

// Good luck allocating 2 ^ 30 elements
这个注释比较有意思，就像是你写了一个方法给别人用，你发现别人传过来数值大的离谱，然后你对这种情况做了点处理让这个数值小点，变成了 2^30。 实际上这也是个大的离谱的数值。 你于是在代码上面写了个注释，祝你好运，God bless you!
大概就是这个意思。 说明这个作者比较幽默呀，哈哈~
@author Josh Bloch and Doug Lea 可以看到作者是 Josh Bloch(《Effective Java》的作者) 和 Doug Lea(JUC并发框架的作者) 两位都是大神级的人物~
我猜 // Good luck allocating 2 ^ 30 elements 应该是 Josh Bloch写的注释，如果你看过《Effective Java》可能也会猜是他了 ~

• ③、带参构造2，接收一个集合

public ArrayDeque(Collection<? extends E> c) {
    // 调用 allocateElements 方法分配数组空间，容量为集合的大小
    allocateElements(c.size());
    // 将集合中的所有元素添加到 ArrayDeque 中
    addAll(c);
}

public boolean addAll(Collection<? extends E> c) {
    boolean modified = false;
    // 遍历集合中的每一个元素
    for (E e : c) {
        // 将元素添加到 ArrayDeque 中，如果成功添加则修改标志
        if (add(e))
            modified = true;
    }
    // 返回是否有元素被添加
    return modified;
}
   

5、 ArrayDeque的addFirst方法

将元素添加到队列头部

public void addFirst(E e) {
    // 检查传入的元素是否为 null，如果是则抛出 NullPointerException
    if (e == null)
        throw new NullPointerException();

    // 计算新的头部索引
    // 1. head - 1 表示向前移动一个位置。
    // 2. (head - 1) & (elements.length - 1) 表示取模运算，以保持环形数组的特性。
    // 使用按位与运算 (&) 来代替取模运算 (%) 是因为这在性能上更高效，
    // 前提是数组的长度必须是 2 的幂，这也是 ArrayDeque 的设计约束。
    head = (head - 1) & (elements.length - 1);

    // 将元素存放在新的头部位置
    elements[head] = e;

    // 如果头部和尾部相遇，说明数组已满，需要扩容
    if (head == tail)
        doubleCapacity();
}

6、 ArrayDeque的addLast方法

将元素添加到队列尾部

public void addLast(E e) {
    // 检查传入的元素是否为 null，如果是则抛出 NullPointerException
    if (e == null)
        throw new NullPointerException();

    // 将元素存放在当前的尾部位置
    elements[tail] = e;

    // 计算新的尾部索引
    // 1. tail + 1 表示向后移动一个位置。
    // 2. (tail + 1) & (elements.length - 1) 表示取模运算，以保持环形数组的特性。
    // 使用按位与运算 (&) 来代替取模运算 (%) 是因为这在性能上更高效，
    // 前提是数组的长度必须是 2 的幂，这也是 ArrayDeque 的设计约束。
    tail = (tail + 1) & (elements.length - 1);

    // 如果尾部和头部相遇，说明数组已满，需要扩容
    if (tail == head)
        doubleCapacity();
}

7、 ArrayDeque是如何利用head和tail索引实现环形数组的？

主要看head和tail是怎么计算的： 默认下标 head和tail都是0
head

head = (head - 1) & (elements.length - 1);
// 将元素存放在新的头部位置
elements[head] = e;

tail

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

可以看到head是先计算，再利用计算过的下标 去给数组赋值
tail则是先用计算前的下标给数组赋值后，再计算新的下标。

addFirst的过程：
当head默认是0。开始的时候，先减一，再和数组长度减一求与，这个操作就相当于，head下标和数组长度求余，再往左移动一位。
比如一开始 head = 0，数组长度是8， 那head = (0-1)&(8-1)=7, 那么第一个添加到队列头部的元素就在整个数组的最后一个位置。
依次类推第二个添加到队列头部的元素就在整个数组的倒数第二个位置。

addLast的过程：
当tail默认是0开始的时候，开始的时候，直接添加元素到数组的第一个位置，然后再计算tail(此时计算的位置是下一次要添加到位列末尾的位置)，tail = (0+ 1) & (8 - 1) = 1，也就是第二次要添加到队列末尾的元素放在数组的第二个位置。
依次类推。

这个时候再把上面的动画拿过来看下更清晰点：

假如ArrayDeque的容量是8，依次向队头添加一个元素，再向队尾添加一个元素，直到 tail= head

此时正好数组被填满了，ArrayDeque就需要扩容了。
下面我们看下ArrayDeque是如何扩容的。

8、 ArrayDeque的doubleCapacity方法（扩容）

如果比较熟悉Collection类型集合的读者，一定很清楚，涉及到扩容就少不了数组复制 System.arraycopy 。
下面这段代码的核心是将现有的元素复制到一个新的更大的数组中，以便有足够的空间添加新的元素。

private void doubleCapacity() {
    assert head == tail;  // 确保在扩容时，队列是满的，即 head == tail

    int p = head;  // 记录当前 head 的位置
    int n = elements.length;  // 获取当前数组的长度
    int r = n - p;  // 计算从 head 到数组末尾的元素数量
    int newCapacity = n << 1;  // 将数组容量扩大一倍

    if (newCapacity < 0) {
        throw new IllegalStateException("Sorry, deque too big");  // 如果新容量溢出（超过整数最大值），抛出异常
    }

    Object[] a = new Object[newCapacity];  // 创建一个新的更大的数组
    System.arraycopy(elements, p, a, 0, r);  // 将 head 到数组末尾的元素复制到新数组的开头
    System.arraycopy(elements, 0, a, r, p);  // 将数组开头到 head 的元素复制到新数组后续位置

    elements = a;  // 更新 elements 引用，指向新的数组
    head = 0;  // 重置 head 为新数组的开头
    tail = n;  // tail 更新为原数组的长度，表示队列元素的结束位置
}

注释已经非常详细了，我们再写一段代码来验证下。

我们利用反射获取ArrayDeque的数组，数组长度，head，tail的值。

import java.lang.reflect.Field;
import java.util.ArrayDeque;

public class TestA {

    public static void main(String[] args) throws Exception {

        ArrayDeque<String> deque = new ArrayDeque<>(1); // 容量小于8就默认是8
        deque.addFirst("队头1");
        deque.addFirst("队头2");
        deque.addFirst("队头3");
        deque.addFirst("队头4");

        deque.addLast("队尾1");
        deque.addLast("队尾2");
        deque.addLast("队尾3");
        deque.addLast("队尾4");

        Class<? extends ArrayDeque> aClass = deque.getClass();

        // 通过反射获取 elements 数组
        Field elementsField = aClass.getDeclaredField("elements");
        elementsField.setAccessible(true);
        Object[] elements = (Object[]) elementsField.get(deque);

        // 获取数组长度
        int length = elements.length;

        // 通过反射获取 head
        Field headField = aClass.getDeclaredField("head");
        headField.setAccessible(true);
        int head = (int) headField.get(deque);

        // 通过反射获取 tail
        Field tailField = aClass.getDeclaredField("tail");
        tailField.setAccessible(true);
        int tail = (int) tailField.get(deque);

        // 打印数组、数组长度、head 和 tail
        System.out.println("Array elements: ");
        for (Object element : elements) {
            System.out.print(element + " ");
        }
        System.out.println();
        System.out.println("Array length: " + length);
        System.out.println("Head: " + head);
        System.out.println("Tail: " + tail);

    }
}

运行结果：

Array elements: 
队头4 队头3 队头2 队头1 队尾1 队尾2 队尾3 队尾4 null null null null null null null null 
Array length: 16
Head: 0
Tail: 8

从结果可以看到 我们把队列添加第八个元素的时候正好填满了队列，tail=head ,触发扩容，扩容后的情况看运行结果就很清晰了。

我们再看下扩容前的情况，即队尾4还没添加之前的数组情况：

队尾1 队尾2 队尾3 null 队头4 队头3 队头2 队头1 
Array length: 8
Head: 4
Tail: 3

这样对比看就十分清晰了。
再画个动画加深印象：

9、 ArrayDeque的其他方法pollFirst、pollLast、peekFirst、peekLast、delete

pollFirst方法

pollFirst 方法用于从队列头部移除并返回第一个元素，如果队列为空则返回 null。

public E pollFirst() {
    int h = head;  // 获取头部索引
    @SuppressWarnings("unchecked")
    E result = (E) elements[h];  // 获取头部元素
    // 如果队列为空，返回 null
    if (result == null)
        return null;
    elements[h] = null;  // 将头部元素置为空
    // 更新头部索引，使用按位与操作来处理环形缓冲区
    head = (h + 1) & (elements.length - 1);
    return result;  // 返回移除的元素
}

pollLast方法

pollLast 方法用于从队列尾部移除并返回最后一个元素，如果队列为空则返回 null。

public E pollLast() {
    // 获取尾部索引，使用按位与操作来处理环形缓冲区
    int t = (tail - 1) & (elements.length - 1);
    @SuppressWarnings("unchecked")
    E result = (E) elements[t];  // 获取尾部元素
    // 如果队列为空，返回 null
    if (result == null)
        return null;
    elements[t] = null;  // 将尾部元素置为空
    tail = t;  // 更新尾部索引
    return result;  // 返回移除的元素
}

peekFirst方法

peekFirst 方法用于返回队列头部的第一个元素，但不移除它。如果队列为空，则返回 null。

public E peekFirst() {
    // 如果队列为空，elements[head] 为 null
    return (E) elements[head];  // 返回头部元素
}

peekLast方法

peekLast 方法用于返回队列尾部的最后一个元素，但不移除它。如果队列为空，则返回 null。

public E peekLast() {
    // 使用按位与操作来处理环形缓冲区，返回尾部元素
    return (E) elements[(tail - 1) & (elements.length - 1)];
}

10、 ArrayDeque实现栈

在Stack详解那篇文章已经写过了，这里直接搬过来。

class MyStack<T>{
	// 使用 ArrayDeque 作为底层数据结构来存储栈元素
    private ArrayDeque<T> arrayDeque;

	// 构造方法，初始化 ArrayDeque
    public MyStack() {
        this.arrayDeque = new ArrayDeque<T>();
    }
    
	// 将元素压入栈顶，使用 addFirst 方法将元素添加到双端队列的头部
    public void push(T elementData){
        arrayDeque.addFirst(elementData);
    }


    public void peek(){
        arrayDeque.getFirst();
    }

    public T pop(){
       return arrayDeque.removeFirst();
    }

    public int size(){
        return arrayDeque.size();
    }

    public boolean isEmpty(){
        return arrayDeque.isEmpty();
    }

    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        // 这里不需要反序迭代  因为我们的push是往头部添加元素 直接正序迭代就是出栈顺序
        Iterator<T> iterator = arrayDeque.iterator();
        while (iterator.hasNext()){
            builder.append(iterator.next().toString()).append("  ");
        }
        return builder.toString();
    }
}

补充： ArrayDeque部分方法的注释以供参考