2.3 ArrayDeque

Wu Jun 2018-12-18 21:52:58
05 Java > 00 Java 基础 > 06 集合

Stack已过时,队列LinkedList效率不高,栈和队列首选ArrayDeque

1 总体介绍

1.1 Deque 接口

ArrayDeque实现了Deque接口,Deque继承Queue实现了Stack相关方法。

Deque的含义是“double ended queue”,即双端队列。既可当栈使用,也可当队列使用。

1) Deque 与 Queue 相对应的接口
Queue Method Deque Method 说明
add(e) addLast(e) 向队尾插入元素,失败则抛出异常
offer(e) offerLast(e) 向队尾插入元素,失败则返回false
remove() removeFirst() 获取并删除队首元素,失败则抛出异常
poll() pollFirst() 获取并删除队首元素,失败则返回null
element() getFirst() 获取但不删除队首元素,失败则抛出异常
peek() peekFirst() 获取但不删除队首元素,失败则返回null
1)Deque 与 Stack 对应的接口
Stack Method Deque Method 说明
push(e) addFirst(e) 向栈顶插入元素,失败则抛出异常
offerFirst(e) 向栈顶插入元素,失败则返回false
pop() removeFirst() 获取并删除栈顶元素,失败则抛出异常
pollFirst() 获取并删除栈顶元素,失败则返回null
peek() getFirst() 获取但不删除栈顶元素,失败则抛出异常
peekFirst() 获取但不删除栈顶元素,失败则返回null

以上接口分为“添加”,“删除”,“取值”三类,都有两套接口,一套失败抛异常,一套失败返回特殊值。

1.2 ArrayDeque

ArrayDeque 底层通过“循环数组”实现。非线程安全,不允许 null 元素。

head 指向首端第一个有效元素,tail 指向尾端第一个可以插入元素的空位

ArrayDeque_base.png

2 方法剖析

2.1 添加

空间问题在插入之后解决,因为 tail 总是指向下一个可插入的空位,也就意味着 elements数组至少有一个空位,所以插入元素的时候不用考虑空间问题。

1)addFirst()

addFirst(E e)是在head前插入元素。 elements[–head] = e 。

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

addLast(E e)是在tail的位置插入元素。elements[tail] = e;

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

下标越界时 head = (head - 1) & (elements.length - 1) 取余。
因为 elements.length 必需是 2 的指数倍,elements - 1 就是二进制低位全 1 ,跟 head - 1 相与之后就起到了取模的作用,如果 head - 1 为负数(其实只可能是-1),则相当于对其取相对于elements.length的补码。

4)扩容

扩容函数doubleCapacity(),逻辑是申请一个更大的数组(原数组的两倍),然后将原数组复制过去。

ArrayDeque_doubleCapacity.png

复制分两次进行,第一次复制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;
}

2.2 删除

1)pollFirst()

pollFirst()删除并返回head处的元素。

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

pollLast()删除并返回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;
}

2.3 取值

1)peekFirst()

peekFirst()返回但不删除head处的元素。

public E peekFirst() {
    return elements[head]; // elements[head] is null if deque empty
}
2)peekLast()

peekLast()返回但不删除tail前的元素。

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