Java容器框架分析(四)——ArrayDeque源码分析

2017/2/23 posted in  Java  

ArrayDeque简介

Java中有一个叫做Stack的实现类,却没有Queue的实现类(只有Queue接口)。当需要使用栈时,Java官方已经不推荐使用Stack而是推荐使用更高效的ArrayDeque;既然Queue只是一个接口,当需要使用队列是也就首选ArrayDeque了,其次就是LinkedList啦。

Deque接口

要将栈和队列,首先需要介绍Deque接口,Deque全称Double Ended Queue,即双端队列。它既可以当做栈使用,也可以当做队列使用。
下标展示Deque和Queue的接口对照表:

Queue方法 Deque方法 方法说明
add(e) addLast(e) 向队尾插入元素,失败则抛出异常
offer(e) offerLast(e) 向队尾插入元素,失败则返回false
remove() removeFirst() 获取并删除队首元素,失败则抛出异常
poll() pollFrist() 获取并删除队首元素,失败则返回null
element() getFirst() 获取但不删除队首元素,失败则抛出异常
peek() peekFirst() 获取但不删除队首元素,失败则返回null

下表列出了Deque和Stack的接口对应关系:

Stack方法 Deque方法 方法说明
push(e) addFirst(e) 向栈顶插入元素,失败则抛出异常
- offerFirst(e) 向栈顶插入元素,失败则返回false
pop() removeFirst(e) 获取并删除栈顶元素,失败则抛出异常
- pollFirst() 获取并删除栈顶元素,失败则返回null
peek() getFirst() 获取但不删除栈顶元素,失败则抛出异常
- peekFirst() 获取但不删除栈顶元素,失败则返回null

上面两个表共定义了Deque的12个接口,添加、删除、查询都有2套接口,它们功能相同,区别就在于对于失败情况的处理方式是不同的。一套接口遇到失败就会抛出异常,另一套遇到失败会返回特殊值(false或者null)。除非某种实现对于容量有限制,大多数情况之下,添加操作是不会失败的。虽然上面列举了12个接口,但是无非就是对容器的两端进行添加、删除、查询操作。

ArrayDeque简介

ArrayDeque和LinkedList是Deque的两个通用实现,由于官方更加推荐使用ArrayDeque用作栈和队列,加之上一篇已经对LinkedList进行了讲解,本文着重讲解ArrayDeque的具体实现。
从名字就可以看出ArrayDeque的底层使用数组实现,为了满足可以在数组的两端插入或删除元素的要求,该数组还必须是循环的,即循环数组,也就是说数组的任何一点都可以被看作为终点或是起点。
ArrayDeque是线程不安全的,当多个线程同时操作时,需要程序员自己进行同步维护。另外,该容器不允许放入null值。

上图中我们看到,head指向首端第一个有效元素,tail指向尾端第一个可以插入元素的空位。因为是循环数组,所以head不一定总等于 0,tail也不一定总是比head大。

常用方法剖析

addFirst()

addFirst(E e)的作用是在Deque的首端插入元素,也就是在head之前插入元素,在空间足够且下标没有越界的情况之下需要将elements[--head] = e即可。

实际需要特别考虑的问题:1、空间是否够用;2、下标是否越界的问题。上图之中,如果head的位置为0之后,在调用addFirst()虽然空余空间还有但是head的值为-1,就造成了下标越界。下列代码很好的解决了这个问题:

public void addFirst(E e) {
    if (e == null)//不允许放入null
        throw new NullPointerException();
    elements[head = (head - 1) & (elements.length - 1)] = e;//2.下标是否越界
    if (head == tail)//1.空间是否够用
        doubleCapacity();//扩容
}

上述代码我们看到,空间问题是在插入之后解决的。因为tail总是指向下一个可插入的空位,也就意味着elements数组至少有一个空位,所以插入元素的时候不需要考虑空间问题。
下标越界的处理起来非常简单,head=(head-1)&(elements.length - 1)就可以了,这段代码相当于取余,同时解决了head为负值的情况。因为elements.length必须是2的指数倍,elements.length - 1就是二进制低位全1,跟head-1 进行 与(&)运算之后就起到了取模的作用,如果head-1为负数(只可能为-1),则相当于对其取相对于elements.length的补码。

下面再说扩容函数doubleCapacity(),其逻辑是申请一个长度为原数组两倍的新数组,然后将原数组复制过去。复制分两次进行,第一次复制head右边的元素,第二次复制head左边的元素。如图所示:

private void doubleCapacity() {
    assert head == tail;
    int p = head;
    int n = elements.length;
    int r = n - p; // head右边元素的个数
    int newCapacity = n << 1;//原空间的2倍
    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;
}

addLast()

addLast(E e)的作用是在Deque的尾端插入元素,也就是在tail的位置插入元素,由于tail总是指向下一个可以插入的空位,因此只需要element[tail] = e即可。插入完成之后再检查空间,如果空间已经用光,则调用doubleCapacity()进行扩容。

public void addLast(E e) {
    if (e == null)//不允许放入null
        throw new NullPointerException();
    elements[tail] = e;//赋值
    if ( (tail = (tail + 1) & (elements.length - 1)) == head)//下标越界处理
        doubleCapacity();//扩容
}

pollFirst()

pollFirst()的作用是返回并删除Deque的首部元素,也就是head位置的元素。如果容器不空,只需要直接返回elements[head]即可,当然还需要处理下标的问题,由于ArrayDeque不允许放入null值,则当elements[head]=null时,意味着容器为空。

public E pollFirst() {
    E result = elements[head];
    if (result == null)//null值意味着deque为空
        return null;
    elements[head] = null;//let GC work
    head = (head + 1) & (elements.length - 1);//下标越界处理
    return result;
}

pollLast()

pollLast()的作用是返回并删除Deque的尾端元素,也就是tail位置前面的那个元素。

public E pollLast() {
    int t = (tail - 1) & (elements.length - 1);//tail的上一个位置是最后一个元素
    E result = elements[t];
    if (result == null)//null值意味着deque为空
        return null;
    elements[t] = null;//let GC work
    tail = t;
    return result;
}

peekFirst()

peekFrist()的作用是返回但不删除Deque的首端元素,也就是head位置的元素,只需要直接返回element[head]即可。

public E peekFirst() {
    return elements[head]; // 如果Deque为空,则返回null
}

peekLast()

peekLast()的作用是返回单不删除Deque的尾端函数,也就是tail的前一个位置的元素,只需要处理一下坐标位置即可。

public E peekLast() {
    return elements[(tail - 1) & (elements.length - 1)];
}

声明

本系列博文装载自:https://github.com/CarpenterLee/JCFInternals
作者:CarpenterLee