【数据结构】Java 常用集合类 ArrayDeque

 关注
发布于: 2020 年 07 月 22 日
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);
}
﻿
tail 表示的是下一个要加入的元素的索引，不是当前最后一个元素的索引。
数组的大小必须是 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 坐标时采用<u>环形队列</u>的形式，如果当前坐标在队列的头部或尾部，下一次坐标移动到队列的另一端。
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;
    }
}
﻿