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();
}

addoffer 方法相当于 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)

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

ArrayDeque 扩容

headtail 相等时,需要进行数组扩容,变为原来容量的两倍:

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 表示 headT 表示 tail

0 1 2 3 4 5 6 7
a b c(H & T) d e f g h

扩容后:

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
c (H) d e f g h a b (T)

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;
    }
}

Add a Comment

电子邮件地址不会被公开。 必填项已用*标注