03-ArrayDeque

1. 概述

2. 用法

ArrayDeque 有如下构造方法：

public ArrayDeque() {
  elements = new Object[16];
}
public ArrayDeque(int numElements) {
  allocateElements(numElements);
}
public ArrayDeque(Collection<? extends E> c) {
  allocateElements(c.size());
  addAll(c);
}

numElements 表示元素个数，初始分配会至少容纳这么多元素，但空间不是正好 numElements 这么大。

3. 基本原理

ArrayDeque 有如下实例变量：

private transient E[] elements;
private transient int head;
private transient int tail;

elements 就是存储元素的数组。ArrayDeque 的高效来源于 head 和 tail 这两个成员变量，他们使得物理上简单的从头到尾的数组变成了一个逻辑上循环的数组，避免了在头尾操作时的移动。

3.1 循环数组

对于一般数组而言，比如 arr ，第一个元素为 arr[0] ，最后一个为 arr[arr.length - 1] 。但对于 ArrayDeque 中的数组，它是一个逻辑上的循环数组，所谓循环是指元素到数组尾之后可以接着从数组头开始，数组的长度，第一个和最后一个元素都与这个 head 和 tail 这两个变量有关，具体来说：

1. 如果 head 与 tail 相同，则数组为空，长度为 0
2. 如果 tail 大于 head ，则第一个元素为 elements[head] ，最后一个元素为 elements[tail - 1] ，长度为 tail - head ，元素索引从head 到 tail - 1
3. 如果 tail 小于 head ，且为 0 ，则第一个元素为 elements[head] ，最后一个元素为 elements[elements.length - 1] ，元素索引从 head 到 elements[elements.length -1]
4. 如果 tail 小于 head ，且大于 0 ，会形成循环，第一个元素为 elements[head] ，最后一个元素是 elements[tail - 1]，元素索引从 head 到 elements.length - 1 ，然后再从 0 到 tail - 1