Stack & Queue 源码解析

可参考官方文档?

Java 中有 Stack 类，却没有 Queue 类，只有 Queue 接口。

在使用栈时，Java 官方已经不推荐使用 Stack，推荐使用 Deque 以及它的实现类（首选 ArrayDeque，其次 LinkedList ）, 如:?

Deque<Integer> stack = new ArrayDeque<Integer>();

Queue

Queue 接口继承自 Collection 接口，除了最基本的 Collection 的方法之外，它还支持额外的 insertion, extraction 和 inspection 操作。有两组格式，共6个方法：一组是抛出异常的实现；另外一组是返回值的实现，没有则返回null。?

Deque

Deque 双端队列，Deque 继承自 Queue 接口，除了支持Queue的方法之外，还支持 insert, remove 和 examine操作。两端（头尾）都可以进行操作，它同时也支持两组格式，一组是抛出异常的实现；另外一组是返回值的实现，没有则返回 null。共12个方法如下：

ArrayDeque

ArrayDeque 底层是用循环数组（Circular Array）实现，且非线程安全，当多个线程同时使用的时候，需要手动同步；另外，该容器不允许放入 null 元素。

对 ArrayDeque 的主要API进行分析：

/**
 * 扩容 2倍
 */
private void doubleCapacity() {
    assert head == tail;
    int p = head;
    int n = elements.length;
    // head 右边的元素个数
    int r = n - p; // number of elements to the right of p
    // 容量变为2倍
    int newCapacity = n << 1;
    if (newCapacity < 0)
        throw new IllegalStateException("Sorry, deque too big");
    Object[] a = new Object[newCapacity];
    // 复制 head 右边的元素
    System.arraycopy(elements, p, a, 0, r);
    // 复制 head 左边的元素
    System.arraycopy(elements, 0, a, r, p);
    // 规范指针位置
    elements = a;
    head = 0;
    tail = n;
}

/**
 * 向 Deque 首端插入元素
 */
public void addFirst(E e) {
    // Null elements are prohibited. 不允许插入空
    if (e == null)
        throw new NullPointerException();
    // 判断下标是否越界
    // head = 0 继续 addFirst
    // head = -1 则下标越界
    // (head - 1) & (elements.length - 1) 相当于取余, 解决了 head 为负值的问题
    // elements.length 一定为 2 的指数幂，elements.length - 1 相当于二进制地位全1
    // (head - 1) & (elements.length - 1) 之后就起到了取模作用，
    // 若 head - 1为负值，这里只可能是 -1，则相当于 elements.length - 1 的补码（除符号位外取反加1）
    // 可以带入值进行计算验证
    elements[head = (head - 1) & (elements.length - 1)] = e;
    // 判断空间是否够用，若不够，则扩容 2 倍
    if (head == tail)
        // 扩容
        doubleCapacity();
}

/**
 * 向 Deque 尾端插入元素
 */
public void addLast(E e) {
    // Null elements are prohibited. 不允许插入空
    if (e == null)
        throw new NullPointerException();
    // 赋值，因为 tail 总是指向下一个可以插入的空位，因此直接赋值即可
    elements[tail] = e;
    // 赋值完检查 Deque 空间是否满，若满，则扩容
    // 下标越界处理
    if ( (tail = (tail + 1) & (elements.length - 1)) == head)
        doubleCapacity();
}

/**
 * Inserts the specified element at the front of this deque.
 */
public boolean offerFirst(E e) {
    addFirst(e);
    return true;
}

/**
 * Inserts the specified element at the end of this deque.
 */
public boolean offerLast(E e) {
    addLast(e);
    return true;
}

/**
 * 删除并返回 Deque 首端元素，为空抛异常
 */
public E removeFirst() {
    E x = pollFirst();
    if (x == null)
        throw new NoSuchElementException();
    return x;
}

/**
 * 删除并返回 Deque 尾端元素，为空抛异常
 */
public E removeLast() {
    E x = pollLast();
    if (x == null)
        throw new NoSuchElementException();
    return x;
}

/**
 * 删除并返回 Deque 首端元素
 */
public E pollFirst() {
    int h = head;
    @SuppressWarnings("unchecked")
    E result = (E) elements[h];
    // Element is null if deque empty
    // deque 为空，返回 null
    if (result == null)
        return null;
    // 删除元素位置必须为空
    elements[h] = null;
    // 下标越界处理
    head = (h + 1) & (elements.length - 1);
    return result;
}

/**
 * 删除并返回 Deque 尾端元素，即 tail 上一个位置的元素
 */
public E pollLast() {
    // tail的上一个位置是最后一个元素
    int t = (tail - 1) & (elements.length - 1);
    @SuppressWarnings("unchecked")
    E result = (E) elements[t];
    if (result == null)
        return null;
    elements[t] = null;
    tail = t;
    return result;
}

/**
 * 返回但不删除 Deque 首端元素，即 head 位置处的元素，为空抛异常
 */
public E getFirst() {
    @SuppressWarnings("unchecked")
    E result = (E) elements[head];
    if (result == null)
        throw new NoSuchElementException();
    return result;
}

/**
 * 返回但不删除 Deque 尾端元素，即 head 位置处的元素，为空抛异常
 */
public E getLast() {
    @SuppressWarnings("unchecked")
    E result = (E) elements[(tail - 1) & (elements.length - 1)];
    if (result == null)
        throw new NoSuchElementException();
    return result;
}

/**
 * 返回但不删除 Deque 首端元素
 */
@SuppressWarnings("unchecked")
public E peekFirst() {
    // elements[head] is null if deque empty
    return (E) elements[head];
}

/**
 * 返回但不删除 Deque 尾端元素
 */
@SuppressWarnings("unchecked")
public E peekLast() {
    return (E) elements[(tail - 1) & (elements.length - 1)];
}