2.3 ArrayDeque

栈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 指向尾端第一个可以插入元素的空位

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()，逻辑是申请一个更大的数组（原数组的两倍），然后将原数组复制过去。

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