java集合 ArrayDeque源码详细分析

问题

（1）什么是双端队列？

（2）arraydeque是怎么实现双端队列的？

（3）arraydeque是线程安全的吗？

（4）arraydeque是有界的吗？

简介

双端队列是一种特殊的队列，它的两端都可以进出元素，故而得名双端队列。

arraydeque是一种以数组方式实现的双端队列，它是非线程安全的。

继承体系

通过继承体系可以看，arraydeque实现了deque接口，deque接口继承自queue接口，它是对queue的一种增强。

public interface deque<e> extends queue<e> {
 // 添加元素到队列头
 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);
// *** 队列中的方法 ***
 // 添加元素，等于addlast(e)
 boolean add(e e);
 // 添加元素，等于offerlast(e)
 boolean offer(e e);
 // 移除元素，等于removefirst()
 e remove();
 // 移除元素，等于pollfirst()
 e poll();
 // 查看元素，等于getfirst()
 e element();
 // 查看元素，等于peekfirst()
 e peek();
// *** 栈方法 ***
// 入栈，等于addfirst(e)
 void push(e e);
 // 出栈，等于removefirst()
 e pop();
// *** collection中的方法 ***
 // 删除指定元素，等于removefirstoccurrence(o)
 boolean remove(object o);
 // 检查是否包含某个元素
 boolean contains(object o);
 // 元素个数
 public int size();
 // 迭代器
 iterator<e> iterator();
 // 反向迭代器
 iterator<e> descendingiterator();
}

deque中新增了以下几类方法：

（1）*first，表示从队列头操作元素；

（2）*last，表示从队列尾操作元素；

（3）push(e)，pop()，以栈的方式操作元素的方法；

源码分析

主要属性

// 存储元素的数组
transient object[] elements; // non-private to simplify nested class access
// 队列头位置
transient int head;
// 队列尾位置
transient int tail;
// 最小初始容量
private static final int min_initial_capacity = 8;

从属性我们可以看到，arraydeque使用数组存储元素，并使用头尾指针标识队列的头和尾，其最小容量是8。

主要构造方法

// 默认构造方法，初始容量为16
public arraydeque() {
 elements = new object[16];
}
// 指定元素个数初始化
public arraydeque(int numelements) {
 allocateelements(numelements);
}
// 将集合c中的元素初始化到数组中
public arraydeque(collection<? extends e> c) {
 allocateelements(c.size());
 addall(c);
}
// 初始化数组
private void allocateelements(int numelements) {
 elements = new object[calculatesize(numelements)];
}
// 计算容量，这段代码的逻辑是算出大于numelements的最接近的2的n次方且不小于8
// 比如，3算出来是8，9算出来是16，33算出来是64
private static int calculatesize(int numelements) {
 int initialcapacity = min_initial_capacity;
 // find the best power of two to hold elements.
 // tests "<=" because arrays aren't kept full.
 if (numelements >= initialcapacity) {
 initialcapacity = numelements;
 initialcapacity |= (initialcapacity >>> 1);
 initialcapacity |= (initialcapacity >>> 2);
 initialcapacity |= (initialcapacity >>> 4);
 initialcapacity |= (initialcapacity >>> 8);
 initialcapacity |= (initialcapacity >>> 16);
 initialcapacity++;

 if (initialcapacity < 0) // too many elements, must back off
 initialcapacity >>>= 1;// good luck allocating 2 ^ 30 elements
 }
 return initialcapacity;
}

通过构造方法，我们知道默认初始容量是16，最小容量是8。

入队

入队有很多方法，我们这里主要分析两个，addfirst(e)和addlast(e)。

// 从队列头入队
public void addfirst(e e) {
 // 不允许null元素
 if (e == null)
 throw new nullpointerexception();
 // 将head指针减1并与数组长度减1取模
 // 这是为了防止数组到头了边界溢出
 // 如果到头了就从尾再向前
 // 相当于循环利用数组
 elements[head = (head - 1) & (elements.length - 1)] = e;
 // 如果头尾挨在一起了，就扩容
 // 扩容规则也很简单，直接两倍
 if (head == tail)
 doublecapacity();
}
// 从队列尾入队
public void addlast(e e) {
 // 不允许null元素
 if (e == null)
 throw new nullpointerexception();
 // 在尾指针的位置放入元素
 // 可以看到tail指针指向的是队列最后一个元素的下一个位置
 elements[tail] = e;
 // tail指针加1，如果到数组尾了就从头开始
 if ( (tail = (tail + 1) & (elements.length - 1)) == head)
 doublecapacity();
}

（1）入队有两种方式，从队列头或者从队列尾；

（2）如果容量不够了，直接扩大为两倍；

（3）通过取模的方式让头尾指针在数组范围内循环；

（4）x & (len - 1) = x % len，使用&的方式更快；

扩容

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];
 // 将旧数组head之后的元素拷贝到新数组中
 system.arraycopy(elements, p, a, 0, r);
 // 将旧数组下标0到head之间的元素拷贝到新数组中
 system.arraycopy(elements, 0, a, r, p);
 // 赋值为新数组
 elements = a;
 // head指向0，tail指向旧数组长度表示的位置
 head = 0;
 tail = n;
}

扩容这里迁移元素可能有点绕，请看下面这张图来理解。

出队

出队同样有很多方法，我们主要看两个，pollfirst()和polllast()。

// 从队列头出队
public e pollfirst() {
 int h = head;
 @suppresswarnings("unchecked")
 // 取队列头元素
 e result = (e) elements[h];
 // 如果队列为空，就返回null
 if (result == null)
 return null;
 // 将队列头置为空
 elements[h] = null; // must null out slot
 // 队列头指针右移一位
 head = (h + 1) & (elements.length - 1);
 // 返回取得的元素
 return result;
}
// 从队列尾出队
public e polllast() {
 // 尾指针左移一位
 int t = (tail - 1) & (elements.length - 1);
 @suppresswarnings("unchecked")
 // 取当前尾指针处元素
 e result = (e) elements[t];
 // 如果队列为空返回null
 if (result == null)
 return null;
 // 将当前尾指针处置为空
 elements[t] = null;
 // tail指向新的尾指针处
 tail = t;
 // 返回取得的元素
 return result;
}

（1）出队有两种方式，从队列头或者从队列尾；

（2）通过取模的方式让头尾指针在数组范围内循环；

（3）出队之后没有缩容哈哈^^

栈

前面我们介绍deque的时候说过，deque可以直接作为栈来使用，那么arraydeque是怎么实现的呢？

public void push(e e) {
 addfirst(e);
}

public e pop() {
 return removefirst();
}

是不是很简单，入栈出栈只要都操作队列头就可以了。

总结

（1）arraydeque是采用数组方式实现的双端队列；

（2）arraydeque的出队入队是通过头尾指针循环利用数组实现的；

（3）arraydeque容量不足时是会扩容的，每次扩容容量增加一倍；

（4）arraydeque可以直接作为栈使用；

彩蛋

双端队列与双重队列？

双端队列（deque）是指队列的两端都可以进出元素的队列，里面存储的是实实在在的元素。

双重队列（dual queue）是指一种队列有两种用途，里面的节点分为数据节点和非数据节点，它是linkedtransferqueue使用的数据结构。

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持。