Java 常用集合类 ArrayDeque

ArrayDeque 整体设计

ArrayDeque 使用循环数组实现的双端队列实现，继承自抽象类 AbstractCollection，同时实现了 Deque 接口（和 Cloneable、Serializable 接口）。双端队列可以实现单端队列的先入先出的方式，也可以实现栈结构的先入后出的方式。ArrayDeque 是非线程安全的。

Queue 是一个单端队列，Deque 是一个双端队列。

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

ArrayDeque 属性和构造函数

// 存储元素的数组
transient Object[] elements;

// 头部元素索引
transient int head;

// 尾部元素索引
transient int tail;

// 无参构造函数，默认容量16
public ArrayDeque() {
    elements = new Object[16];
}

// 指定容量的构造函数
public ArrayDeque(int numElements) {
    allocateElements(numElements);
}

// 指定集合的构造函数
public ArrayDeque(Collection<? extends E> c) {
    allocateElements(c.size());
    addAll(c);
}

1. tail 表示的是下一个要加入的元素的索引，不是当前最后一个元素的索引。

2. 数组的大小必须是 2^n。由 allocateElements() 方法实现。

ArrayDeque 添加元素

ArrayDeque 可以在队首或队尾添加元素：

public void addFirst(E e) {
    if (e == null)
        throw new NullPointerException();
    elements[head = (head - 1) & (elements.length - 1)] = e;
    if (head == tail)
        doubleCapacity();
}

public void addLast(E e) {
    if (e == null)
        throw new NullPointerException();
    elements[tail] = e;
    if ( (tail = (tail + 1) & (elements.length - 1)) == head)
        doubleCapacity();
}

add、offer 方法相当于 addLast

public boolean add(E e) {
    addLast(e);
    return true;
}

public boolean offer(E e) {
    return offerLast(e);
}

public boolean offerLast(E e) {
    addLast(e);
    return true;
}

在队首插入数据，head向前移动一位，插入数据。计算 head 坐标方法：

head = (head - 1) & (elements.length - 1)

在队尾插入数据，直接插入 tail 位置的元素，并计算下一次 tail 坐标：

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

在计算 head 和 tail 坐标时采用环形队列的形式，如果当前坐标在队列的头部或尾部，下一次坐标移动到队列的另一端。

ArrayDeque 扩容

当 head 和 tail 相等时，需要进行数组扩容，变为原来容量的两倍：

private void doubleCapacity() {
    assert head == tail;
    int p = head;
    int n = elements.length;
    int r = n - p; // number of elements to the right of p
    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);
    System.arraycopy(elements, 0, a, r, p);
    elements = a;
    head = 0;
    tail = n;
}

首先记录当前 head 的位置（p），然后把容量变为原来的两倍，之后把 head 右侧的元素（包含 head）复制到新数组的开头（0 - r 位置），再把 head 左侧的元素也复制到新数组（r - n 位置）。

原队列：（H 表示 head，T 表示 tail）

扩容后：

ArrayDeque 获取元素

ArrayDeque 有多种获取元素的方法，

• 在方向上分为两类：获取队首或队尾元素
• 在方式上分为两类：获取到元素后从队列中删除或不删除
• 对不存在元素处理：抛出异常或返回 null

返回 head 元素，队列不变

public E element() {
    return getFirst();
}

public E getFirst() {
    E result = (E) elements[head];
    if (result == null)
        throw new NoSuchElementException();
    return result;
}

public E peek() {
    return peekFirst();
}

public E peekFirst() {
    return (E) elements[head];
}

head 元素出队列

public E pop() {
    return removeFirst();
}

public E removeFirst() {
    E x = pollFirst();
    if (x == null)
        throw new NoSuchElementException();
    return x;
}

public E poll() {
    return pollFirst();
}

public E pollFirst() {
    int h = head;
    @SuppressWarnings("unchecked")
    E result = (E) elements[h];
    if (result == null)
        return null;
    elements[h] = null; 
    head = (h + 1) & (elements.length - 1);
    return result;
}

返回 tail 前一位元素

public E getLast() {
    E result = (E) elements[(tail - 1) & (elements.length - 1)];
    if (result == null)
        throw new NoSuchElementException();
    return result;
}

public E peekLast() {
    return (E) elements[(tail - 1) & (elements.length - 1)];
}

tail 前一位元素出队列

public E removeLast() {
    E x = pollLast();
    if (x == null)
        throw new NoSuchElementException();
    return x;
}

public E pollLast() {
    int t = (tail - 1) & (elements.length - 1);
    E result = (E) elements[t];
    if (result == null)
        return null;
    elements[t] = null;
    tail = t;
    return result;
}

ArrayDeque 删除元素

ArrayDeque 不仅可以移除队首或队尾元素，还可以指定元素移除，或移除第一次（或最后一次）出现的元素：

public boolean remove(Object o) {
    return removeFirstOccurrence(o);
}

public boolean removeFirstOccurrence(Object o) {
    if (o == null)
        return false;
    int mask = elements.length - 1;
    int i = head;
    Object x;
    while ( (x = elements[i]) != null) {
        if (o.equals(x)) {
            delete(i);
            return true;
        }
        i = (i + 1) & mask;
    }
    return false;
}

public boolean removeLastOccurrence(Object o) {
    if (o == null)
        return false;
    int mask = elements.length - 1;
    int i = (tail - 1) & mask;
    Object x;
    while ( (x = elements[i]) != null) {
        if (o.equals(x)) {
            delete(i);
            return true;
        }
        i = (i - 1) & mask;
    }
    return false;
}

删除时调用 delete 方法实现，会执行数组拷贝：

// 删除坐标为 i 的元素
private boolean delete(int i) {

    final Object[] elements = this.elements;
    final int mask = elements.length - 1;
    final int h = head;
    final int t = tail;
    // i 到 head 和 tail 的距离
    final int front = (i - h) & mask;
    final int back  = (t - i) & mask;

    // 优化项：如果判断该元素到 head 的距离近，移动 i 到 head 间的元素
    // 反之执行相反的操作

    // 移动完成后重新计算 head 或 tail 的位置
    if (front < back) {
        if (h <= i) {
            System.arraycopy(elements, h, elements, h + 1, front);
        } else { 
            System.arraycopy(elements, 0, elements, 1, i);
            elements[0] = elements[mask];
            System.arraycopy(elements, h, elements, h + 1, mask - h);
        }
        elements[h] = null;
        head = (h + 1) & mask;
        return false;
    } else {
        if (i < t) { 
            System.arraycopy(elements, i + 1, elements, i, back);
            tail = t - 1;
        } else { 
            System.arraycopy(elements, i + 1, elements, i, mask - i);
            elements[mask] = elements[0];
            System.arraycopy(elements, 1, elements, 0, t);
            tail = (t - 1) & mask;
        }
        return true;
    }
}