- 这次来说一下
ArrayDeque,我们先看一下他的类关系图,其中忽略掉了一些标记性接口
-
我们看一下类的定义
public class ArrayDeque<E> extends AbstractCollection<E> implements Deque<E>, Cloneable, Serializable {...} -
从中我们可以看到他实现了
Deque接口,那么Deque是实现了Queue<E>接口,如下是两个接口中的部分方法Queue: boolean add(E e); boolean offer(E e); E remove(); E poll(); E element(); E peek(); Deque: void addFirst(E e); void addLast(E e); boolean offerFirst(E e); boolean offerLast(E e); E removeFirst(); E removeLast(); E pollFirst(); E pollLast(); ... - 从上面我们就可以看到在
Queue接口中只定义了关于队列的一些方法,一方进一方出,而在Deque中出现了xxFirst&xxLast一些操作方法,这样我们通过这些方法就不止可以进行队列的操作了,并且同时也支持了栈的操作,那么我们也注意到addFirst&addLast方法,能够在一个队列中的头尾都进行操作元素,所以ArrayDeque类可以支持双端队列和栈的所有操作 - 了解完他的继承实现关系,那么我们就正式的来看一下他的源码实现
属性
//保存元素的数组
transient Object[] elements;
//头指针
transient int head;
//尾指针
transient int tail;
//容量限制
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;- 从上我们就可以看到,
ArrayDeque的实现依旧是采用了数组实现,并且有一定的容量限制,我们接着往下看
构造
-
构造方法依旧是三个,分别是无参的,有初始化容量的,和以集合为参数创建实例的三种构造方法
public ArrayDeque() { elements = new Object[16]; } -
默认构造的默认容量为16,接着看其他的构造方法
public ArrayDeque(int numElements) { //如果参数小于1,那么就以1为默认初始化容量,否则再去比较容量是否等于Integer.MAX_VALUE //是的话就以Integer.MAX_VALUE为容量,否则就是参数值+1作为默认容量 elements = new Object[(numElements < 1) ? 1 : (numElements == Integer.MAX_VALUE) ? Integer.MAX_VALUE : numElements + 1]; } - 如上可以看到,即使我们传入了一些非法的参数,比如是负数情况下,
ArrayDeque依旧是不会报错的,并且我们得知了,ArrayDeque的最大初始化容量就是Integer.MAX_VALUE,如果既不是负数也不是最大值,那么就是以你参数+1作为长度进行初始化,为什么会将传入参数加一处理,因为如果你是参数为1的话,他加一处理后会常见两个长度的数组,此时head和tail都是指向0.而第二个null总是留给tail去用的 -
下面是以集合为参数的构造方法
public ArrayDeque(Collection<? extends E> c) { //调用上面分析的构造方法,以集合元素个数为默认初始化容量 this(c.size()); //将集合中元素拷贝到数组中 copyElements(c); } private void copyElements(Collection<? extends E> c) { //forEach是循环的方法,然后 :: 操作符是Java8新增的,所以这的意思是 //将集合中元素遍历,并且依次调用本类的addLast方法添加到数组中 //至于具体的addLast,我们马上就开始分析 c.forEach(this::addLast); }
问题
- 我们之前知道了
ArrayDeque是一个双端队列的实现,并且本类的实现是依靠数组的,那么我们就会想到这样的一个问题,当一个数组中被填充了一个元素,这时候head肯定是指向数组的下标0元素的,那么我们此时将头元素取出,然后数组index=0位置的元素就为null了,那么此时head必定会往后移一位,指向下一个元素,那么此时在添加tail指向肯定也是一步步往后移,那么之前释放掉的index=0的元素位置不就浪费了吗 ? 我们来看图来解释这个问题
- 图应该说的很明白了,所以我们现在遇到了这样的一个浪费的问题,那么
ArrayDeque给出的解决方案就是将数组作为一个逻辑上的循环数组使用,当head后移导致前面为null时,并且tail到达一个数组的最后位置,那么就去检查head前面的位置是否有空闲的,因为取出都是从head取,所以不会出现断断续续有数据的情况,所以他就要去判断数组位置是否为null,所以ArrayDeque是不允许插入null元素的
- 看图之后我们知道了大概的思路,所以我们知道了head不会总是0的,tail也不一定总是大于head的,那么对于
ArrayDeque最终是怎么实现调整的,我们来看他的源码实现 - 鉴于方法太多,我们就挑出最核心的方法说
add
public boolean add(E e) {
//默认将元素添加到数组最后面
addLast(e);
return true;
}
public void addLast(E e) {
if (e == null)
throw new NullPointerException();
//保存引用
final Object[] es = elements;
//tail的实现保证永远指向最后一个元素的下一个null位置
//所以可以直接进行插入
es[tail] = e;
//这个方法可以说是很巧妙了,主要目的是在于判断是否还有空余位置插入元素
//是否需要扩容,并且还确定tail的指向
if (head == (tail = inc(tail, es.length)))
grow(1);
}
static final int inc(int i, int modulus) {
if (++i >= modulus) i = 0;
return i;
}- 理解
inc方法有点不容易,所以我们画图来说
- 从上图,我们就非常清楚了inc的方法的巧妙,也清楚了add方法的流程
分清数组的First和Last
ArrayDeque<String> stringArrayDeque = new ArrayDeque<>(4);
stringArrayDeque.addFirst("1");
stringArrayDeque.addLast("2");
sys(stringArrayDeque); //输出方法-
结果
[2, null, null, null, 1] - 所以数组的<-这边是Last,相反则是First
addFirst
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);//扩容
}
static final int dec(int i, int modulus) {
if (--i < 0) i = modulus - 1;
return i;
}- 经过了inc方法,dec方法我们看着就容易理解多了,其目的就是寻找head的插入位置,上图
- OK到这我们就完全了解了他们的实现了, 然后其中涉及到的grow方法我们没有说,下来我们来看一下
grow
private void grow(int needed) {
final int oldCapacity = elements.length;
int newCapacity;
// 如果容量小,则增加一倍,否则增加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
//如果tail和head之间还有位置
//或者数组满了和排除是初始化状态的数组
if (tail < head || (tail == head && es[head] != null)) {
//新增容量
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;
}
}
//边缘条件下的容量计算,特别是溢出
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;
}- 好了大概的逻辑我们就清楚了,实现扩容并不是只根据参数进行扩容而是进行多方面考虑,比如数组的大小
addAll
public boolean addAll(Collection<? extends E> c) {
final int s, needed;
//deque中的元素数加上集合中的元素数加上永远保证的一个null空间之和减去
//数组的长度,如果大于0表名数组不够,进行grow,否则就不grow
if ((needed = (s = size()) + c.size() + 1 - elements.length) > 0)
grow(needed);
//循环拷贝进去
copyElements(c);
return size() > s;
}
//返回此deque中的元素数
public int size() {
return sub(tail, head, elements.length);
}
static final int sub(int i, int j, int modulus) {
//判断是否是tail与head有null,让后分情况处理
if ((i -= j) < 0) i += modulus;
return i;
}- 到这add方法基本即结束了,下面是删除方法,删除方法有remove和poll,两者的区别在之前的文章提到过了,在这我就只分析一下remove好了
remove
public E remove() {
return removeFirst();
}
public E removeFirst() {
//还是调用了poll方法...
E e = pollFirst();
//其实poll方法跟remove方法只是缺了这个判断
if (e == null)
throw new NoSuchElementException();
return e;
}
public E pollFirst() {
final Object[] es;
final int h;
//返回数组索引i处的元素
E e = elementAt(es = elements, h = head);
//返回的元素不为null
if (e != null) {
//将它设置为null
es[h] = null;
//inc方法返回head下一个元素位置
head = inc(h, es.length);
}
//返回元素
return e;
}
//实现简单
static final <E> E elementAt(Object[] es, int i) {
return (E) es[i];
}- 还有根据OBject对象删除了,无非就是for循环去找,判断相等的办法是
equals - 对于
removeLast的实现就是采用了pollLast方法,里面的核心实现肯定一样,不同的是它使用dec方法,将tail做参数返回位置,别的其他都一样 - 删除了方法还有
delete,方法的区别是,i位置被删除后,元素后的整体会迁移 - 还有适应Java8出现的一些lambda方法,比如
removeIf,参数是Predicate函数接口,如果你了解lambda你就会知道这个怎样用了 - add方法是默认在last添加元素,而remove是在first删除,所以这两个方法就构成了一个队列的操作
- 下面介绍的push.pop就构成了一个栈的操作
push
-
没啥可说的了,都分析过了
public void push(E e) { 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); }
pop
-
也没啥可说的了
public E pop() { return removeFirst(); } //调用关系自己看一下吧 ,上面也有贴源码 - 所以到这我就将一核心办法给写了一下,当然这完全是自己的分析,也是第一次看,所以不对的地方请指正,谢谢您
总结
- 那么今天的分析比较令自己惊讶的地方就是inc这个方法,真的是十分的巧妙,而对于其他操作,只要了解一下堆栈是啥再继续在本子上画画图就出来了,那么今天介绍的
ArrayDeque是一个数组实现,有容量,不是线程安全,好像已经把他概括完了... - 对了, 源注释介绍本类的时候, 告诉了我们使用这个类比Stack和LinkedList要快
