ArrayDeque源码解析
源码 解析 ArrayDeque
2023-06-13 09:15:59 时间
转载请以链接形式标明出处: 本文出自:103style的博客
base on jdk_1.8.0_77
目录
ArrayDeque
简介ArrayDeque
的常量和成员变量介绍ArrayDeque
的构造函数ArrayDeque
相关的函数- 小结
- 参考文章
ArrayDeque简介
ArrayDeque
类是双端队列Deque
的实现类,类的继承结构如下:
public class ArrayDeque<E> extends AbstractCollection<E>
implements Deque<E>, Cloneable, Serializable
就其实现而言,ArrayDeque
采用了循环数组的方式来完成双端队列的功能。
ArrayDeque
有以下基本特征:
- 无限的扩展,自动扩展队列大小的。(当然在不会内存溢出的情况下。)
- 非线程安全的,不支持并发访问和修改。
- 支持
fast-fail
. - 作为栈使用的话比
Stack
要快. - 当队列使用比
LinkedList
要快。 null
元素被禁止使用。
ArrayDeque的常量和成员变量介绍
private static final int MIN_INITIAL_CAPACITY = 8; //初始化 elements 的 最小长度
transient Object[] elements; // ArrayDeque保存数据的数组
transient int head;// 第一个元素的位置
transient int tail;// 最后一个元素的位置
ArrayDeque的构造函数
- 数组默认的长度时
16
,当指定长度时,会通过allocateElements
计算 大于numElements
的最小2n
(n >=3)
为数组的长度。 为什么是2n
,和 HashMap 类似,通过index & (elements.length - 1)
计算索引。
public ArrayDeque() {
elements = new Object[16];
}
public ArrayDeque(int numElements) {
allocateElements(numElements);
}
public ArrayDeque(Collection<? extends E> c) {
allocateElements(c.size());
addAll(c);
}
private void allocateElements(int numElements) {
int initialCapacity = MIN_INITIAL_CAPACITY;
if (numElements >= initialCapacity) {
initialCapacity = numElements;
initialCapacity |= (initialCapacity >>> 1);
initialCapacity |= (initialCapacity >>> 2);
initialCapacity |= (initialCapacity >>> 4);
initialCapacity |= (initialCapacity >>> 8);
initialCapacity |= (initialCapacity >>> 16);
initialCapacity++;
if (initialCapacity < 0)
initialCapacity >>>= 1;
}
elements = new Object[initialCapacity];
}
ArrayDeque相关的函数
//添加到head前面
public void push(E e)
public boolean offerFirst(E e)
public void addFirst(E e)
//添加到tail后面
public boolean add(E e)
public boolean offerLast(E e)
public void addLast(E e)
//删除head所在位置的元素
public E pop()
public E remove()
public E poll()
public E removeFirst()
public E pollFirst()
//删除 tail所在位置的元素
public E removeLast()
public E pollLast()
//获取head所在位置的元素
public E element()
public E peek()
public E peekFirst()
//获取tail所在位置的元素
public E peekLast()
//获取队列元素的个数
public int size()
addFirst(E e)
- 因为
head
和tail
默认为0
,所以默认第一个元素存入的位置为element
数组的最后的索引位置。当head==tail
时,说明elements
数组满了,需要进行数组扩容,新数组长度是原来的2
倍,然后重新赋值head = 0
。
public void addFirst(E e) {
if (e == null)
throw new NullPointerException();
elements[head = (head - 1) & (elements.length - 1)] = e;
if (head == tail)
doubleCapacity();
}
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 = a;
head = 0;
tail = n;
}
addLast(E e)
addLast
即赋值tail
索引位置的值为e
,然后tail++
,当head==tail
时,同addFirst(E e)
进行数组扩容。
public void addLast(E e) {
if (e == null)
throw new NullPointerException();
elements[tail] = e;
if ( (tail = (tail + 1) & (elements.length - 1)) == head)
doubleCapacity();
}
pollFirst()、pollLast()、peekFirst()、peekLast()
- 返回对应索引的元素。
public E pollFirst() {
final Object[] elements = this.elements;
final int h = head;
@SuppressWarnings("unchecked")
E result = (E) elements[h];
// Element is null if deque empty
if (result != null) {
elements[h] = null; // Must null out slot
head = (h + 1) & (elements.length - 1);
}
return result;
}
public E pollLast() {
final Object[] elements = this.elements;
final int t = (tail - 1) & (elements.length - 1);
@SuppressWarnings("unchecked")
E result = (E) elements[t];
if (result != null) {
elements[t] = null;
tail = t;
}
return result;
}
public E peekFirst() {
// elements[head] is null if deque empty
return (E) elements[head];
}
public E peekLast() {
return (E) elements[(tail - 1) & (elements.length - 1)];
}
size()
public int size() {
return (tail - head) & (elements.length - 1);
}
小结
ArrayDeque
是带首尾标记
的数组实现的双端队列。
参考文章
以上
相关文章
- Element使用的async-validator表单校验库源码超详细解析
- react-router/v5之Router、Route、Redirect、Switch源码解析
- hostapd_acs 源码分析
- Mybatis原理解析之一 SqlSessionFactory生产(源码解析)
- React源码分析7-state计算流程和优先级
- 【Go】Chan 的使用和源码解析
- SpringBoot数据库配置源码解析:自动配置内部实现解析
- kubelet源码解析
- Android双端队列——ArrayDeque的实现&源码分析[通俗易懂]
- mybatis3源码解析--spring下mapper注册详解
- ArrayList源码解析
- react源码解析11.生命周期调用顺序1
- 软件测试|一键搞定centos7的docker+selenium+appium+jenkins+android_app源码打包成apk的环境搭建
- 详解HashMap源码解析(下)
- 择时荟萃(二):近10年比特币市场上的趋势策略(附源码)
- tp5源码解析--自动加载类
- 【EventBus】EventBus 源码解析 ( 事件发送 | 发布线程为 子线程 切换到 主线程 执行订阅方法的过程分析 )
- 【Linux 内核】进程管理 ( 系统调用简介 | 进程相关系统调用源码 )
- 【Android Gradle 插件】Gradle 构建机制 ⑤ ( 在 Android Studio 中查看 Android Gradle 插件源码 )
- HashMap源码解析详解编程语言
- Java项目实战之在线考试系统(带源码和解析)
- Java项目资源下载地址(包括源码和解析)
- How to Compile Redis from Source Code: A StepbyStep Guide(redis源码编译)
- 开发mssql:深入探索软件源码(mssql软件源码)
- 编写一个含二级目录的源码(Asp+JavaScript)
- JavaScript实现的石头剪刀布游戏源码分享