全网稀有！！！基于JDK11的 ArrayDeque 源码超详细分析
程序员文章站
2022-07-14 16:09:35
...
ArrayDeque源码分析
文章目录
一、基本介绍
-
ArrayDeque是一种以数组方式实现的双端队列，它是非线程安全的
- 双端队列是一种特殊的队列，它的两端都可以进出元素，故而得名双端队列
-
ArrayDeque使用的是循环数组，如下图所示：
从上图中可以看到，head指向首端第一个有效元素，tail指向尾端第一个可以插入元素的空位；因为是循环数组，所以head不一定总等于0，tail也不一定总是比head大
-
ArrayDeque不允许添加null值
-
可以当作队列来使用，也可以当作栈来使用
- 官方推荐使用ArrayDeque用作栈和队列
- 做栈（Stack）时性能比
Stack好，做队列（Queue）时性能比LinkedList好
-
继承体系
通过继承体系可以看到，ArrayDeque实现了Deque接口，Deque接口继承自Queue接口，它是对Queue的一种增强，Deque接口源码如下所示：
public interface Deque<E> extends Queue<E> { /****************** 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(); // 从队列头向后遍历移除指定元素 boolean removeFirstOccurrence(Object o); // 从队列尾向前遍历移除指定元素 boolean removeLastOccurrence(Object o); /******************** Queue接口中的方法 *******************/ // 添加元素，等于addLast(e) boolean add(E e); // 添加元素，等于offerLast(e) boolean offer(E e); // 移除元素，等于removeFirst() E remove(); // 移除元素，等于pollFirst() E poll(); // 查看元素，等于getFirst() E element(); // 查看元素，等于peekFirst() E peek(); // 添加参数集合中的元素 boolean addAll(Collection<? extends E> c); /************************* 栈方法 *************************/ // 入栈，等于addFirst(e) void push(E e); // 出栈，等于removeFirst() E pop(); /******************** Collection中的方法 *******************/ // 删除指定元素，等于removeFirstOccurrence(o) boolean remove(Object o); // 检查是否包含某个元素 boolean contains(Object o); // 元素个数 int size(); // 迭代器 Iterator<E> iterator(); // 反向迭代器 Iterator<E> descendingIterator(); }观察上述源码可知，Deque中新增了以下几类方法：
- * First，表示从队列头操作元素
- * Last，表示从队列尾操作元素
- push(e)，pop()，以栈的方式操作元素
二、源码分析
1. 成员属性
//存储元素的数组
transient Object[] elements;
//头节点的索引值
transient int head;
//尾节点的索引值
transient int tail;
//数组的最大容量
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
2. 构造方法
//空参构造器
public ArrayDeque() {
elements = new Object[16]; //数组默认容量是16
}
//指定初始容量的构造器
public ArrayDeque(int numElements) {
elements =
new Object[(numElements < 1) ? 1 :
(numElements == Integer.MAX_VALUE) ? Integer.MAX_VALUE :
numElements + 1];
}
//数组容量 = 指定的容量 + 1
//数组的最小容量是1
//指定初始数据的构造器
public ArrayDeque(Collection<? extends E> c) {
this(c.size());
copyElements(c);
}
3. 入队方法
3.1 addFirst(E e)方法
addFirst(E e) 方法源码如下：
//从队列头部添加元素
public void addFirst(E e) {
//不允许添加null值
if (e == null)
throw new NullPointerException();
final Object[] es = elements;
//调用dec方法找到新的头节点位置，并将e插入
es[head = dec(head, es.length)] = e;
//如果头尾指向同一个节点，就调用grow方法扩容
if (head == tail)
grow(1); //扩容方法之后会讲述
}
dec(int i, int modulus) 方法源码如下：
有两种情况：
-
如果原头节点不是数组首元素，如下图所示：
将head向前移动一位，成为新的头节点
-
如果原头节点是数组首元素
数组的最后一个元素作为头节点，第二个元素是数组首元素
//参数i表示原头节点的索引值
//参数modulus表示原数组的长度
static final int dec(int i, int modulus) {
//如果原头节点是数组首元素
if (--i < 0) i = modulus - 1;
//返回新的头节点索引
return i;
}
3.2 addLast(E e)方法
addLast(E e) 方法源码如下：
//从队列尾添加元素
public void addLast(E e) {
if (e == null)
throw new NullPointerException();
final Object[] es = elements;
//tail指向尾端第一个可以插入元素的空位，所以tail的索引可以直接添加元素
es[tail] = e;
//如果头尾指向同一个节点，就调用grow方法扩容
//调用inc方法得到新的尾索引
if (head == (tail = inc(tail, es.length)))
grow(1);
}
inc(int i, int modulus) 方法源码如下：
有两种情况：
-
如果原尾索引不是数组最后一个元素的位置，如下图所示：
新尾索引 = 原尾索引 + 1
-
如果原尾索引是数组最后一个元素的位置
新尾索引是数组第一个元素的位置，即0
//参数i表示原尾索引
//参数modulus表示原数组长度
static final int inc(int i, int modulus) {
//如果原尾索引是数组最后一个元素的位置
if (++i >= modulus) i = 0;
//返回新尾索引
return i;
}
4. 扩容方法
扩容思路图示，仅思路，详细过程并不完全准确：
grow(int needed) 方法源码如下：
//入参needed为当前添加操作所需要的空间，当只添加一个元素时为1，添加多个元素时就是多个元素的长度
private void grow(int needed) {
final int oldCapacity = elements.length;
int newCapacity;
//如果原数组容量 < 64，新容量 = 旧容量的2倍 + 2
//如果原数组容量 >= 64，新容量 = 旧容量的1.5倍
int jump = (oldCapacity < 64) ? (oldCapacity + 2) : (oldCapacity >> 1);
if (jump < needed
|| (newCapacity = (oldCapacity + jump)) - MAX_ARRAY_SIZE > 0)
newCapacity = newCapacity(needed, jump);
//将旧数组的内容拷贝到扩容后的新数组中并赋值给elements和es
final Object[] es = elements = Arrays.copyOf(elements, newCapacity);
//此时仅仅将数组容量扩大，head和tail仍指向同一个节点
if (tail < head || (tail == head && es[head] != null)) {
//将旧数据复制到新的位置
int newSpace = newCapacity - oldCapacity;
System.arraycopy(es, head,
es, head + newSpace,
oldCapacity - head);
//将旧位置的旧数据全部清空
//head成为了新位置的首元素的位置
for (int i = head, to = (head += newSpace); i < to; i++)
es[i] = null;
}
}
5. 出队方法
5.1 pollFirst()方法
pollFirst() 方法源码如下：
public E pollFirst() {
final Object[] es;
final int h;
E e = elementAt(es = elements, h = head);
//elementAt方法返回es[h]，即head位置的元素
if (e != null) {
es[h] = null; //head位置的元素置为null
//head要么向后移动一位，要么成为数组首元素的位置，不再赘述
head = inc(h, es.length);
}
return e; //返回原head位置的元素
}
5.2 pollLast()方法
pollLast() 方法源码如下：
public E pollLast() {
final Object[] es;
final int t;
//调用dec方法，tail要么向前移动一位，要么成为数组尾元素的位置
E e = elementAt(es = elements, t = dec(tail, es.length));
if (e != null)
es[tail = t] = null; //tail位置的元素被赋予null值
return e; //返回tail位置原来还没有被赋予null值的元素
}
观察出队的两个方法的源码，发现出队之后没有缩容
6. 栈方法
6.1 push(E e)方法
push(E e) 方法源码如下：
public void push(E e) {
addFirst(e); //调用了addFirst方法从队列头部添加元素，不再赘述
}
6.2 pop()方法
pop() 方法源码如下：
public E pop() {
return removeFirst();
}
public E removeFirst() {
E e = pollFirst(); //调用了pollFirst方法弹出首元素，不再赘述
if (e == null)
throw new NoSuchElementException();
return e;
}
观察上述源码发现，ArrayDeque满足栈的特性，从队列头部增 / 删元素
下一篇： Linux 磁盘挂载共享