ArrayDeque是基于数组实现的无界双端队列。ArrayDeque中的数组没有容量限制,它们能根据需要增长以支持使用。需要注意的是ArrayDeque不是线程安全的,因此在没有外部同步的情况下,它们不支持多线程并发访问。
ArrayDeque用作栈时可能比Stack更快,用作队列时可能比LinkedList更快。
ArrayDeque禁止插入空元素。
ArrayDeque及其迭代器实现了Collection和Iterator接口的所有可选方法。
ArrayDeque是Java Collections Framework的一个成员。
1. ArrayDeque的声明ArrayDeque的接口和继承关系如下
public class ArrayDequeextends AbstractCollection
implements Deque, Cloneable, Serializable
…
}
完整的接口继承关系如下图所示。
编辑
从上述代码可以看出,ArrayDeque既实现了java.util.Deque 、java.lang.Cloneable、java.io.Serializable接口,又继承了java.util.AbstractCollection。
2. ArrayDeque的成员变量和构造函数以下是ArrayDeque的构造函数和成员变量。
// 元素数组
transient Object[] elements;
// 队列头索引
transient int head;
// 队列尾索引
transient int tail;
// 数组最大容量
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
public ArrayDeque() {
elements = new Object[16 + 1];
}
public ArrayDeque(int numElements) {
elements =
new Object[(numElements < 1) ? 1 :
(numElements == Integer.MAX_VALUE) ? Integer.MAX_VALUE :
numElements + 1];
}
public ArrayDeque(Collection
this(c.size());
copyElements(c);
}
从上述代码可以看出,构造函数有3种。构造函数中的参数含义如下
l numElements用于设置队列中内部数组的元素总数。如果没有指定,则会使用默认元素总数16。需要注意的是,实际数组的大小,是numElements+1。
l c用于设置最初包含给定集合的元素,按集合迭代器的遍历顺序添加
类成员elements是一个数组,用于存储队列中的元素。head和tail分别表示队头索引和队尾索引。
思考:为什么实际数组的实际数组的大小,是numElements+1?
3. ArrayDeque的核心方法以下对ArrayDeque常用核心方法的实现原理进行解释。
3.1. addLast(e)执行addLast(e)方法后有两种结果
l 队列未达到容量时,直接插入,没有返回值
l 队列达到容量时,先扩容,再插入,没有返回值
ArrayDeque的addLast(e)方法源码如下:
public void addLast(E e) {
if (e == null) // 判空
throw new NullPointerException();
final Object[] es = elements;
es[tail] = e;
if (head == (tail = inc(tail, es.length)))
grow(1); // 扩容
}
从上面代码可以看出,addLast(e)方法会先进行判空处理,而后再将元素插入。如果插入前判断容量不够,则会执行grow()方法进行扩容。
。
grow()方法源码如下:
private void grow(int needed) {
// overflow-conscious code
final int oldCapacity = elements.length;
int newCapacity;
// Double capacity if small; else grow by 50%
int jump = (oldCapacity < 64) ? (oldCapacity + 2) : (oldCapacity >> 1);
if (jump < needed
|| (newCapacity = (oldCapacity + jump)) - MAX_ARRAY_SIZE > 0)
newCapacity = newCapacity(needed, jump);
final Object[] es = elements = Arrays.copyOf(elements, newCapacity);
// Exceptionally, here tail == head needs to be disambiguated
if (tail < head || (tail == head && es[head] != null)) {
// wrap around; slide first leg forward to end of array
int newSpace = newCapacity - oldCapacity;
System.arraycopy(es, head,
es, head + newSpace,
oldCapacity - head);
for (int i = head, to = (head += newSpace); i < to; i++)
es[i] = null;
}
}
/** Capacity calculation for edge conditions, especially overflow. */
private int newCapacity(int needed, int jump) {
final int oldCapacity = elements.length, minCapacity;
if ((minCapacity = oldCapacity + needed) - MAX_ARRAY_SIZE > 0) {
if (minCapacity < 0)
throw new IllegalStateException("Sorry, deque too big");
return Integer.MAX_VALUE;
}
if (needed > jump)
return minCapacity;
return (oldCapacity + jump - MAX_ARRAY_SIZE < 0)
? oldCapacity + jump
: MAX_ARRAY_SIZE;
}
3.2. offerLast(e)执行offerLast(e)方法后有两种结果
l 队列未达到容量时,返回 true
l 队列达到容量时,先扩容,再返回 true
ArrayDeque的offerLast(e)方法源码如下:
public boolean offerLast(E e) {
addLast(e);
return true;
}
从上面代码可以看出,执行offerLast(e)方法直接调用的是addLast(e)
。
3.3. addLast(e)执行addFirst(e)方法后有两种结果
l 队列未达到容量时,直接插入,没有返回值
l 队列达到容量时,先扩容,再插入,没有返回值
ArrayDeque的addFirst(e)方法源码如下:
public void addFirst(E e) {
if (e == null) // 判空
throw new NullPointerException();
final Object[] es = elements;
es[head = dec(head, es.length)] = e;
if (head == tail)
grow(1); // 扩容
}
从上面代码可以看出,addFirst(e)方法会先进行判空处理,而后再将元素插入。如果插入前判断容量不够,则会执行grow()方法进行扩容。
。
3.4. pollFirst()执行pollFirst()方法后有两种结果:
l 队列不为空时,返回队首值并移除
l 队列为空时,返回 null
ArrayDeque的pollFirst()方法源码如下:
public E pollFirst() {
final Object[] es;
final int h;
E e = elementAt(es = elements, h = head);
if (e != null) {
es[h] = null;
head = inc(h, es.length);
}
return e;
}
从上面代码可以看出,执行pollFirst()方法时,分为以下几个步骤:
l 先取队列的队首元素。
l 如果队首元素不存在,直接返回null。
l 如果队首元素存在,则返回该元素同时移除元素。
3.5. removeFirst()执行removeFirst()方法后有两种结果:
l 队列不为空时,返回队首值并移除
l 队列为空时,抛出异常
ArrayDeque的removeFirst()方法源码如下:
public E removeFirst() {
E e = pollFirst();
if (e == null)
throw new NoSuchElementException();
return e;
}
从上面代码可以看出,removeFirst()方法直接调用了pollFirst()方法。如果pollFirst()方法返回结果为null,则抛出NoSuchElementException异常。
pollFirst()方法此处不再赘述。
3.6. peekFirst()执行peekFirst()方法后有两种结果:
l 队列不为空时,返回队首值但不移除
l 队列为空时,返回null
peekFirst()方法源码如下:
public E peekFirst() {
return elementAt(elements, head);
}
static final E elementAt(Object[] es, int i) {
return (E) es[i];
}
从上面代码可以看出,peekFirst()方法比较简单,直接就是获取了数组里面的索引为head的元素。
3.7. getFirst()执行getFirst()方法后有两种结果:
l 队列不为空时,返回队首值但不移除
l 队列为空时,抛出异常
getFirst()方法源码如下:
public E getFirst() {
E e = elementAt(elements, head);
if (e == null)
throw new NoSuchElementException();
return e;
}
从上面代码可以看出,执行getFirst()方法时,先是获取了数组里面的索引为head的元素。如果结果是null,则抛出NoSuchElementException异常。
4. ArrayDeque的单元测试ArrayDeque的单元测试如下:
package com.waylau.java.demo.datastructure;
import static org.junit.jupiter.api.Assertions.assertEquals;
import static org.junit.jupiter.api.Assertions.assertNull;
import static org.junit.jupiter.api.Assertions.assertThrows;
import static org.junit.jupiter.api.Assertions.assertTrue;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.NoSuchElementException;
import org.junit.jupiter.api.Test;
/**
* ArrayDeque Tests
*
* @since 1.0.0 2020年5月3日
* @author
最近更新
- 深拷贝和浅拷贝的区别(重点)
- 【Vue】走进Vue框架世界
- 【云服务器】项目部署—搭建网站—vue电商后台管理系统
- 【React介绍】 一文带你深入React
- 【React】React组件实例的三大属性之state,props,refs(你学废了吗)
- 【脚手架VueCLI】从零开始,创建一个VUE项目
- 【React】深入理解React组件生命周期----图文详解(含代码)
- 【React】DOM的Diffing算法是什么?以及DOM中key的作用----经典面试题
- 【React】1_使用React脚手架创建项目步骤--------详解(含项目结构说明)
- 【React】2_如何使用react脚手架写一个简单的页面?