在总集篇中我大概梳理了一下整个集合类的关系，这篇文章是对总集篇的扩展，本文将详细讨论ArrayDeque的实现原理。所有涉及到的源码都是基于JDK11。顺便插一句，大家要学就学新的嘛，毕竟11可是长期支持版本，可以用好几年的那种。
ArrayDeque简介
ArrayDeque是基于数组实现的双端循环队列，通常来说，ArrayDeque可以实现队列的功能，也能实现栈的功能，同时可以通过双端的乱序操作实现一些特殊的算法。
ArrayDeque的类描述
public class ArrayDeque<E> extends AbstractCollection<E>
implements Deque<E>, Cloneable, Serializable
其主要实现了Deque接口，下面看一看Deque要求提供的功能。
void addFirst(E e);
void addLast(E e);
boolean offerFirst(E e);
boolean offerLast(E e);
E removeFirst();
E removeLast();
E pollFirst();
E pollLast();
E getFirst();
E getLast();
E peekFirst();
E peekLast();
// 删除在deque中第一次出现的指定元素
boolean removeFirstOccurrence(Object o);
// 删除在deque中最后一次出现的指定元素
boolean removeLastOccurrence(Object o);
// 以下API是为了与queue兼容，添加元素在尾节点操作，删除元素在头节点删除
boolean add(E e);
boolean offer(E e);
E remove();
E poll();
E element();
E peek();
// 以下API是为了实现栈的语义
void push(E e);
E pop();
ArrayDeque的成员变量
// 用来存放元素的数组
transient Object[] elements;
// 头节点指针，指向当前元素，准确的说是指向remove将要删除的元素
transient int head;
// 尾节点指针，指向当前元素的下一个元素，准确的说是指向add将要添加的位置
transient int tail;
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
支撑ArrayDeque的内部结构
主要就是串并行迭代器，这两部分的代码很简单，就不贴出来了。
ArrayDeque重要的函数
添加元素相关函数
// 插入头节点
public void addFirst(E e) {
if (e == null)
throw new NullPointerException();
final Object[] es = elements;
// 因为head指向当前元素，所以需要先将索引向下挪动一位，再赋值，其中head向下挪动一位
// 的方式是当前值减一，根据循环队列的规则，当减一越界的时候需要处理为数组尾部
es[head = dec(head, es.length)] = e;
// 当首位指针相同的时候，满了，扩容。ArrayDeque没有浪费一个容量来区分head==tail是是满还是空
// 这也没有必要，再插入元素的相关函数中head==tail一定意味这元素满，需要扩容。
// 在元素删除的相关函数中，head==tail一定意味着元素空，需要抛出异常。
if (head == tail)
grow(1);
}
static final int dec(int i, int modulus) {
if (--i < 0) i = modulus - 1;
return i;
}
private void grow(int needed) {
// overflow-conscious code
final int oldCapacity = elements.length;
int newCapacity;
// Double capacity if small; else grow by 50%
int jump = (oldCapacity < 64) ? (oldCapacity + 2) : (oldCapacity >> 1);
// 如果扩充的容量小于需求的容量或者扩充后超过了最大值，则处理一下
if (jump < needed
|| (newCapacity = (oldCapacity + jump)) - MAX_ARRAY_SIZE > 0)
newCapacity = newCapacity(needed, jump);
// 扩容并且将元素复制过来，复制后的元素从数组0号位开始
final Object[] es = elements = Arrays.copyOf(elements, newCapacity);
// Exceptionally, here tail == head needs to be disambiguated
// 重置tail和head
if (tail < head || (tail == head && es[head] != null)) {
// wrap around; slide first leg forward to end of array
int newSpace = newCapacity - oldCapacity;
// 将元素移到数组后部，从head + newSpace到最后
System.arraycopy(es, head,
es, head + newSpace,
oldCapacity - head);
// 将前面元素设置为null，将head位置调整为head + newSpace
for (int i = head, to = (head += newSpace); i < to; i++)
es[i] = null;
}
}
// 在尾端插入元素
public void addLast(E e) {
if (e == null)
throw new NullPointerException();
final Object[] es = elements;
// 先设置值，tail指向下一次add的位置，所以应该先设置值
es[tail] = e;
// 然后调整tail位置，如果head和tail相等，则扩容
if (head == (tail = inc(tail, es.length)))
grow(1);
}
删除相关函数
public E removeFirst() {
E e = pollFirst();
if (e == null)
throw new NoSuchElementException();
return e;
}
public E pollFirst() {
final Object[] es;
final int h;
// 获取head指向元素
E e = elementAt(es = elements, h = head);
if (e != null) {
es[h] = null;
// head向上挪一位
head = inc(h, es.length);
}
return e;
}
public E removeLast() {
E e = pollLast();
if (e == null)
throw new NoSuchElementException();
return e;
}
public E pollLast() {
final Object[] es;
final int t;
// 因为tail是指向下一位，所以要先挪位再获取
E e = elementAt(es = elements, t = dec(tail, es.length));
if (e != null)
es[tail = t] = null;
return e;
}
get相关函数
get相关函数十分简单，就不贴代码了。
网友评论