Java集合ArrayDeque类实例分析
作者:lqh 时间:2022-06-19 18:25:06
Java集合ArrayDeque类实例分析
前言
ArrayDeque类是双端队列的实现类,类的继承结构如下面,继承自AbastractCollection(该类实习了部分集合通用的方法,其实现了Collection接口),其实现的接口Deque接口中定义了双端队列的主要的方法,比如从头删除,从尾部删除,获取头数据,获取尾部数据等等。
public class ArrayDeque<E> extends AbstractCollection<E>
implements Deque<E>, 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;
这里根据注释中提及,必须是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);
return result;
}
感谢阅读,希望能帮助大家,谢谢大家对本站的支持!
来源:http://blog.csdn.net/wangyang1354/article/details/57081920
![](/images/zang.png)
![](/images/jiucuo.png)
猜你喜欢
Mybatis下的SQL注入漏洞原理及防护方法解析
![](https://img.aspxhome.com/file/2023/2/63082_0s.png)
Java框架---Spring详解
![](https://img.aspxhome.com/file/2023/5/61825_0s.jpg)
c#测试本机sql运算速度的代码示例分享
C#(int)中Convert、Parse、TryParse的区别
简单解析java方法在调用在内存中的执行过程
![](https://img.aspxhome.com/file/2023/6/59756_0s.png)
C#值类型、引用类型中的Equals和==的区别浅析
![](https://img.aspxhome.com/file/2023/3/98283_0s.png)
详解Vue响应式的部分实现
数组实现Java 自定义Queue队列及应用操作
![](https://img.aspxhome.com/file/2023/0/60380_0s.png)
MyBatis查询数据,赋值给List集合时,数据缺少的问题及解决
![](https://img.aspxhome.com/file/2023/1/88201_0s.png)
Java面向对象实现汽车租赁系统
![](https://img.aspxhome.com/file/2023/8/64428_0s.jpg)
Java真题实练掌握哈希表的使用
![](https://img.aspxhome.com/file/2023/9/59079_0s.png)
Spring Batch入门教程篇
![](https://img.aspxhome.com/file/2023/4/83014_0s.png)
Java Bean与xml互相转换的方法分析
AQS同步组件Semaphore信号量案例剖析
![](https://img.aspxhome.com/file/2023/3/60483_0s.png)
Java NIO实例UDP发送接收数据代码分享
Android Google AutoService框架使用详解
![](https://img.aspxhome.com/file/2023/3/89513_0s.png)
Android文本输入框(EditText)输入密码时显示与隐藏
java实现在线聊天系统
Java程序顺序结构中逻辑控制语句详解流程
![](https://img.aspxhome.com/file/2023/2/79912_0s.jpg)
Spring Security 实现用户名密码登录流程源码详解
![](https://img.aspxhome.com/file/2023/8/64058_0s.png)