参考文章：JCFInternals
环境：JDK1.9

介绍：
ArrayDeque 实现了Deque接口，它既可以当作栈使用，也可以当作队列使用，底层实现是循环数组，未实现同步，无法存储null元素

实现功能：

  • size() ：获取当前元素个数
  • addFirst(T element)：在集合首端插入元素
  • addLast(T element)：在集合尾端插入元素
  • pollFirst()： 删除并返回集合首端元素
  • pollLast()： 删除并返回集合尾端元素
  • peekFirst()：返回集合首端元素
  • peekLast()：返回集合尾端元素
import java.lang.annotation.ElementType;

public class MyArrayDeque<T> {
    private Object[] elementData;
    private int head;
    private int tail;

    MyArrayDeque() {
        elementData = new Object[16];
    }

    public int size() {
        return (tail - head + elementData.length) & (elementData.length - 1);
    }

    // 在集合首端插入元素
    public void addFirst(T element) {
        // 不允许放 null
        if (element == null) {
            throw new NullPointerException();
        }
        // head 前移一位放 element
        elementData[head = ((head - 1) & (elementData.length - 1))] = element;
        // 满了，扩容
        if (head == tail) {
            grow();
        }
    }

    // 在集合尾端插入元素
    public void addLast(T element) {
        // 不允许放 null
        if (element == null) {
            throw new NullPointerException();
        }
        elementData[tail] = element;
        // 如果满了，扩容
        if ((tail = (tail + 1) & (elementData.length - 1)) == head) {
            grow();
        }
    }

    // 删除并返回集合首端元素
    public T pollFirst() {
        T res = (T) elementData[head];
        // 如果 res 是null，意味着此时集合为空
        if (res == null) {
            return null;
        }
        elementData[head] = null;
        head = ((head + 1) & (elementData.length - 1));
        return res;
    }

    // 删除并返回集合尾端元素
    public T pollLast() {
        int t = (tail - 1) & (elementData.length - 1);
        T res = (T) elementData[t];
        // 如果 res 是null，意味着此时集合为空
        if (res == null) {
            return null;
        }
        elementData[t] = null;
        tail = t;
        return res;
    }

    public T peekFirst() {
        return (T) elementData[head];
    }

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

    private void grow() {
        int p = head;
        int n = elementData.length;
        // head右边元素个数
        int r = n - p;
        // 扩容一倍
        int newCapacity = n << 1;
        if (newCapacity < 0) {
            throw new IllegalStateException("Sorry, deque too big");
        }
        Object[] a = new Object[newCapacity];
        // 将 [head,elementData.length) 的值复制到新数组的开头
        System.arraycopy(elementData, p, a, 0, r);
        // 将 [0,head) 的值复制到新数组的后面
        System.arraycopy(elementData, 0, a, r, p);
        elementData = (T[]) a;
        head = 0;
        tail = n;
    }

}