ArrayDeque
ArrayDeque 能解决什么问题？什么时候使用 ArrayDeque?
1）Deque 接口大小可变的循环数组实现，ArrayDeque 没有容量限制并会按需增长。
2）ArrayDeque 的容量为 2 的幂，因为索引的计算是通过 & 操作实现的。
3）ArrayDeque 不是线程安全的，ArrayDeque 不允许使用 null 元素。
4）ArrayDeque 的大多数操作基于平摊常数时间，除了 remove* 和 contains。
5）ArrayDeque 返回的 iterator 是快速失败的。
如何使用 ArrayDeque?
1）ArrayDeque 用作栈时，性能优于 Stack，用作队列时，性能优于 LinkedList。
使用 ArrayDeque 有什么风险？
1）ArrayDeque 的容量为 2 的幂，存在一定的内存浪费。
ArrayDeque 核心操作的实现原理？
/**
* ArrayDeque 底层存储元素的对象数组，没有持有元素的 slot 总是 null，
* 对象数组总是至少有一个可用的 slot（尾部 slot 总是 null）
*/
transient Object[] elements;
/**
* 头部元素的索引
*/
transient int head;
/**
* 尾部元素的索引
*/
transient int tail;
/**
* 创建一个可用容量为 15 的空 ArrayDeque 实例
*/
public ArrayDeque() {
elements = new Object[16];
}
/**
* 创建一个可用容量为 numElements 的空 ArrayDeque 实例
*/
public ArrayDeque(int numElements) {
elements =
/**
* 1）numElements < 1 时，值为 1
* 2）numElements == Integer.MAX_VALUE 时，值为 Integer.MAX_VALUE
* 3）否则值为 numElements+1
*/
new Object[numElements < 1 ? 1 :
numElements == Integer.MAX_VALUE ? Integer.MAX_VALUE :
numElements + 1];
}
单向队列相关操作
/**
* 将元素插入到单向队列尾部
*/
@Override
public boolean offer(E e) {
return offerLast(e);
}
/**
* 将元素插入到双向队列尾部
*/
@Override
public boolean offerLast(E e) {
addLast(e);
return true;
}
/**
* 将目标元素添加到单向队列尾部
*/
@Override
public void addLast(E e) {
if (e == null) {
throw new NullPointerException();
}
// 读取底层对象数组
final Object[] es = elements;
// 由于 tail 总是为 null，可以直接新增元素
es[tail] = e;
// 累加尾部索引值，如果尾部和头部索引重叠，则需要执行扩容
if (head == (tail = ArrayDeque.inc(tail, es.length))) {
// 底层数组扩容
grow(1);
}
}
/**
* 基于 modulus 循环递增目标索引 i
*/
static final int inc(int i, int modulus) {
// 如果索引递增后，超出数组的有效索引值，则循环移动到数组头部
if (++i >= modulus) {
i = 0;
}
return i;
}
/**
* 递增 ArrayDeque 可用容量，以至少能容纳 needed 个新元素
*/
private void grow(int needed) {
// 读取旧长度
final int oldCapacity = elements.length;
int newCapacity;
/**
* 计算需要扩大的容量值
* 1）旧容量 < 64，则执行【双倍+2】扩容
* 2）否则执行 1.5 倍向下取整扩容
*/
final int jump = oldCapacity < 64 ? oldCapacity + 2 : oldCapacity >> 1;
/**
* 1）扩容值 < 所需可用容量
* 2）新容量 > Integer.MAX_VALUE - 8
*/
if (jump < needed
|| (newCapacity = oldCapacity + jump) - MAX_ARRAY_SIZE > 0) {
// 进行二次扩容
newCapacity = newCapacity(needed, jump);
}
// 拷贝原数组并写入
final Object[] es = elements = Arrays.copyOf(elements, newCapacity);
// Exceptionally, here tail == head needs to be disambiguated
/**
* 1）尾部索引在前
* 2）头部和尾部重合
* 并且头部元素不为 null
*/
if (tail < head || tail == head && es[head] != null) {
// 计算新增加的可用容量值
final int newSpace = newCapacity - oldCapacity;
// head 处以及之后的所有元素整体右移 oldCapacity - head 个位置，使得数组元素连续
System.arraycopy(es, head,
es, head + newSpace,
oldCapacity - head);
// 将原来填充元素的 slot 置为 null
for (int i = head, to = head += newSpace; i < to; i++) {
es[i] = null;
}
}
}
/** Capacity calculation for edge conditions, especially overflow. */
private int newCapacity(int needed, int jump) {
final int oldCapacity = elements.length, minCapacity;
// 1）【旧容量+所需新容量】超出，Integer.MAX_VALUE - 8
if ((minCapacity = oldCapacity + needed) - MAX_ARRAY_SIZE > 0) {
if (minCapacity < 0) {
throw new IllegalStateException("Sorry, deque too big");
}
// 返回 Integer.MAX_VALUE
return Integer.MAX_VALUE;
}
// 2）批量添加集合中元素时触发，所需容量 > 新扩容容量，返回【旧容量+所需容量】
if (needed > jump) {
return minCapacity;
}
/**
* 走到这里满足三个条件
* 1）need <= jump
* 2）oldCapacity + needed <= MAX_ARRAY_SIZE
* 3）oldCapacity + jump >= MAX_ARRAY_SIZE
*/
return oldCapacity + jump - MAX_ARRAY_SIZE < 0
? oldCapacity + jump
: MAX_ARRAY_SIZE;
}
/**
* 将目标元素添加到单向队列尾部，添加成功返回 true
*/
@Override
public boolean add(E e) {
addLast(e);
return true;
}
- 查看队列头部元素：peek、element【单向队列为空时抛出 NoSuchElementException 异常】
/**
* 查看单向队列的头部元素
*/
@Override
public E peek() {
return peekFirst();
}
@Override
public E peekFirst() {
return ArrayDeque.elementAt(elements, head);
}
/**
* 返回底层对象数组中指定索引处的元素
*/
@SuppressWarnings("unchecked")
static final <E> E elementAt(Object[] es, int i) {
return (E) es[i];
}
/**
* 单向队列为空时抛出 NoSuchElementException 异常
*/
@Override
public E element() {
return getFirst();
}
- 移除并返回头部元素：poll、remove【单向队列为空时抛出 NoSuchElementException 异常】
/**
* 移除并返回单向队列的头部元素，如果队列为空，则返回 null
*/
@Override
public E poll() {
return pollFirst();
}
@Override
public E pollFirst() {
final Object[] es;
final int h;
// 读取头部元素
final E e = ArrayDeque.elementAt(es = elements, h = head);
if (e != null) {
// 如果元素存在，则将头部置为 null
es[h] = null;
// 循环递增头部索引
head = ArrayDeque.inc(h, es.length);
}
return e;
}
/**
* 单向队列为空时抛出 NoSuchElementException 异常
*/
@Override
public E remove() {
return removeFirst();
}
双向队列相关操作
- 将元素添加到队列头部：offerFirst、addFirst
/**
* 将元素插入到双端队列的头部，插入成功返回 true
*/
@Override
public boolean offerFirst(E e) {
addFirst(e);
return true;
}
/**
* 将元素插入到双端队列的头部
*/
@Override
public void addFirst(E e) {
if (e == null) {
throw new NullPointerException();
}
final Object[] es = elements;
es[head = ArrayDeque.dec(head, es.length)] = e;
if (head == tail) {
grow(1);
}
}
/**
* 基于 modulus 循环递减目标索引
*/
static final int dec(int i, int modulus) {
if (--i < 0) {
// 如果小于 0，则移动到对象数组尾部
i = modulus - 1;
}
return i;
}
- 将元素添加到队列尾部：offerLast、addLast
/**
* 将元素插入到双端队列尾部，插入成功返回 true
*/
@Override
public boolean offerLast(E e) {
addLast(e);
return true;
}
/**
* 将目标元素添加到双端队列尾部
*/
@Override
public void addLast(E e) {
if (e == null) {
throw new NullPointerException();
}
// 读取底层对象数组
final Object[] es = elements;
// 由于 tail 总是为 null，可以直接新增元素
es[tail] = e;
// 累加尾部索引值，如果尾部和头部索引重叠，则需要执行扩容
if (head == (tail = ArrayDeque.inc(tail, es.length))) {
// 底层数组扩容
grow(1);
}
}
- 查看队列头部元素：peekFirst、getFirst【双向队列为空时抛出 NoSuchElementException 异常】
/**
* 查看双端队列的头部元素
*/
@Override
public E peekFirst() {
return ArrayDeque.elementAt(elements, head);
}
/**
* @throws NoSuchElementException {@inheritDoc}
*/
@Override
public E getFirst() {
final E e = ArrayDeque.elementAt(elements, head);
if (e == null) {
throw new NoSuchElementException();
}
return e;
}
- 查看队列尾部元素：peekLast、getLast【双向队列为空时抛出 NoSuchElementException 异常】
/**
* 查看双端队列的尾部元素
*/
@Override
public E peekLast() {
final Object[] es;
// 由于 tail 总是 null，实际的尾部元素在 tail-1 索引处
return ArrayDeque.elementAt(es = elements, ArrayDeque.dec(tail, es.length));
}
/**
* @throws NoSuchElementException {@inheritDoc}
*/
@Override
public E getLast() {
final Object[] es = elements;
final E e = ArrayDeque.elementAt(es, ArrayDeque.dec(tail, es.length));
if (e == null) {
throw new NoSuchElementException();
}
return e;
}
- 移除并返回队列头部元素:pollFirst、removeFirst【双向队列为空时抛出 NoSuchElementException 异常】
/**
* 移除并返回双端队列的头部元素
*/
@Override
public E pollFirst() {
final Object[] es;
final int h;
// 读取头部元素
final E e = ArrayDeque.elementAt(es = elements, h = head);
if (e != null) {
// 如果元素存在，则将头部置为 null
es[h] = null;
// 循环递增头部索引
head = ArrayDeque.inc(h, es.length);
}
return e;
}
/**
* @throws NoSuchElementException {@inheritDoc}
*/
@Override
public E removeFirst() {
final E e = pollFirst();
if (e == null) {
throw new NoSuchElementException();
}
return e;
}
- 移除并返回队列尾部元素：pollLast、removeLast【双向队列为空时抛出 NoSuchElementException 异常】
/**
* 移除并返回双端队列的尾部元素
*/
@Override
public E pollLast() {
final Object[] es;
final int t;
// 读取尾部元素
final E e = ArrayDeque.elementAt(es = elements, t = ArrayDeque.dec(tail, es.length));
if (e != null) {
// 如果存在，则将其置为 null，同时更新尾部索引
es[tail = t] = null;
}
return e;
}
/**
* @throws NoSuchElementException {@inheritDoc}
*/
@Override
public E removeLast() {
final E e = pollLast();
if (e == null) {
throw new NoSuchElementException();
}
return e;
}
栈相关操作
/**
* 元素入栈
*/
@Override
public void push(E e) {
addFirst(e);
}
/**
* 元素出栈，如果栈为空，则抛出 NoSuchElementException 异常
*/
@Override
public E pop() {
return removeFirst();
}
/**
* 查看单向队列/栈的头部元素
*/
@Override
public E peek() {
return peekFirst();
}
/**
* 返回 ArrayDeque 中的元素个数
*/
@Override
public int size() {
return ArrayDeque.sub(tail, head, elements.length);
}
/**
* ArrayDeque 是否为空
*/
@Override
public boolean isEmpty() {
return head == tail;
}