Java集合ArrayDeque类实例分析

Java集合ArrayDeque类实例分析

java集合ArrayDeque类实例分析

前言

ArrayDeque类是双端队列的实现类，类的继承结构如下面，继承自AbastractCollection（该类实习了部分集合通用的方法，其实现了Collection接口），其实现的接口Deque接口中定义了双端队列的主要的方法，比如从头删除，从尾部删除，获取头数据，获取尾部数据等等。

public class ArrayDeque extends AbstractCollection

implements Deque, Cloneable, Serializable

ArrayDeque基本特征

就其实现而言，ArrayDeque采用了循环数组的方式来完成双端队列的功能。

1. 无限的扩展，自动扩展队列大小的。（当然在不会内存溢出的情况下。）

2. 非线程安全的，不支持并发访问和修改。

3. 支持fast-fail.

4. 作为栈使用的话比比栈要快.

5. 当队列使用比linklist要快。

6. null元素被禁止使用。

ArrayDeque实现方法解读

最小初始化容量限制

/**

* The minimum capacity that we'll use for a newly created deque.

* Must be a power of 2.

*/

private static final int MIN_INITIAL_CAPACITY = 8;

这里根据注释中http://提及，必须是2的幂次。仅仅通过这里是不会知道为何要这样设定的。

public void addFirst(E e) {

if (e == null)

throw new NullPointerException();

elements[head = (head - 1) & (elements.length - 1)] = e;

if (head == tail)

doubleCapacity();

}

addFirst方法中使用了head-1和length-1相与的形式来计算，那么，length-1这里是多少，因为规定了length必须是2的幂次，所以length-1后二进制低位将全部为1，然后与head-1相与相当于对其进行取模。

扩容

之所以说该ArrayDeque容量无限制，是因为只要检测到head==tail的时候，就直接调用doubleCapacity方法进行扩容。

这个时候将数组展开，head和tail指向的是同一个位置，那么，因为是循环数组，所以head左边可能存在一部分元素为p个，右边也可能存在一部分数据r=n-p个，右边的部分复制到从0到r,左边的部分复制到从r到结束。这样原来的数据从0开始往下排列。

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];

System.arraycopy(elements, p, a, 0, r);

System.arraycopy(elements, 0, a, r, p);

elements = (E[])a;

head = 0;

tail = n;

}

删除元素

删除元素的基本思路为确定那一侧的数据少，少的一侧移动元素位置，这样效率相对于不比较更高些，然后，判断head是跨越最大值还是为跨越最大值，继而可以分两种不同的情况进行拷贝。但是该方法比较慢，因为存在数组的拷贝。

private boolean delete(int i) {

checkInvariants();

final E[] elements = this.elements;

final int mask = elements.length - 1;

final int h = head;

final int t = tail;

final int front = (i - h) & mask;

final int back = (t - i) & mask;

// Invariant: head <= i < tail mod circularity

if (front >= ((t - h) & mask))

throw new ConcurrentModificationException();

// Optimize for least element motion

// 为了最小的拷贝数据

if (front < back) {

// 递增的顺序时

if (h <= i) {

// 删除部分前面的向后移动

System.arraycopy(elements, h, elements, h + 1, front);

} else { // Wrap around

// 跨越最小与最大值

// 分两次拷贝

System.arraycopy(elements, 0, elements, 1, i);

// 最大的地方单独处理

elements[0] = elements[mask];

// 前面的部分向后移动一位

System.arraycopy(elements, h, elements, h + 1, mask - h);

}

elements[h] = null;

head = (h + 1) & mask;

return false;

} else {

// 递增的顺序时

if (i < t) { // Copy the null tail as well

// 拷贝i后面的部分数据前置

System.arraycopy(elements, i + 1, elements, i, back);

tail = t - 1;

} else { // Wrap around

// 跨越中间最大值的时候

// 后面向前拷贝

// 0处的值单独处置放在最大的下标处

// 后面的部分从1开始向前移动一个，原来的1在0处

System.arraycopy(elements, i + 1, elements, i, mask - i);

elements[mask] = elements[0];

System.arraycopy(elements, 1, elements, 0, t);

tail = (t - 1) & mask;

}

return true;

}

}

获取并删除元素

这里在举个简单点的例子，中间判断是不是null，可以看出该队列不支持null,通过把其值设为null就算是将其删除了。然后head向递增的方向退一位即可。

public E pollFirst() {

int h = head;

E result = elements[h]; // Element is null if deque empty

if (result == null)

return null;

elements[h] = null; // Must null out slot

head = (h + 1) & (elements.length - 1);

returnhttp:// result;

}

感谢阅读，希望能帮助大家，谢谢大家对本站的支持！

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。