死磕 java集合之ArrayDeque源码分析

public interface Deque<E> extends Queue<E> {    // 添加元素到队列头    void addFirst(E e);    // 添加元素到队列尾    void addLast(E e);    // 添加元素到队列头    boolean offerFirst(E e);    // 添加元素到队列尾    boolean offerLast(E e);    // 从队列头移除元素    E removeFirst();    // 从队列尾移除元素    E removeLast();    // 从队列头移除元素    E pollFirst();    // 从队列尾移除元素    E pollLast();    // 查看队列头元素    E getFirst();    // 查看队列尾元素    E getLast();    // 查看队列头元素    E peekFirst();    // 查看队列尾元素    E peekLast();    // 从队列头向后遍历移除指定元素    boolean removeFirstOccurrence(Object o);    // 从队列尾向前遍历移除指定元素    boolean removeLastOccurrence(Object o);    // *** 队列中的方法 ***    // 添加元素，等于addLast(e)    boolean add(E e);     // 添加元素，等于offerLast(e)    boolean offer(E e);    // 移除元素，等于removeFirst()    E remove();    // 移除元素，等于pollFirst()    E poll();    // 查看元素，等于getFirst()    E element();    // 查看元素，等于peekFirst()    E peek();    // *** 栈方法 ***    // 入栈，等于addFirst(e)    void push(E e);    // 出栈，等于removeFirst()    E pop();    // *** Collection中的方法 ***    // 删除指定元素，等于removeFirstOccurrence(o)    boolean remove(Object o);    // 检查是否包含某个元素    boolean contains(Object o);    // 元素个数    public int size();    // 迭代器    Iterator<E> iterator();    // 反向迭代器    Iterator<E> descendingIterator();}

// 存储元素的数组transient Object[] elements; // non-private to simplify nested class access// 队列头位置transient int head;// 队列尾位置transient int tail;// 最小初始容量private static final int MIN_INITIAL_CAPACITY = 8;

// 默认构造方法，初始容量为16public ArrayDeque() {    elements = new Object[16];}// 指定元素个数初始化public ArrayDeque(int numElements) {    allocateElements(numElements);}// 将集合c中的元素初始化到数组中public ArrayDeque(Collection<? extends E> c) {    allocateElements(c.size());    addAll(c);}// 初始化数组private void allocateElements(int numElements) {    elements = new Object[calculateSize(numElements)];}// 计算容量，这段代码的逻辑是算出大于numElements的最接近的2的n次方且不小于8// 比如，3算出来是8，9算出来是16，33算出来是64private static int calculateSize(int numElements) {    int initialCapacity = MIN_INITIAL_CAPACITY;    // Find the best power of two to hold elements.    // Tests "<=" because arrays aren't kept full.    if (numElements >= initialCapacity) {        initialCapacity = numElements;        initialCapacity |= (initialCapacity >>>  1);        initialCapacity |= (initialCapacity >>>  2);        initialCapacity |= (initialCapacity >>>  4);        initialCapacity |= (initialCapacity >>>  8);        initialCapacity |= (initialCapacity >>> 16);        initialCapacity++;        if (initialCapacity < 0)   // Too many elements, must back off            initialCapacity >>>= 1;// Good luck allocating 2 ^ 30 elements    }    return initialCapacity;}

// 从队列头入队public void addFirst(E e) {    // 不允许null元素    if (e == null)        throw new NullPointerException();    // 将head指针减1并与数组长度减1取模    // 这是为了防止数组到头了边界溢出    // 如果到头了就从尾再向前    // 相当于循环利用数组    elements[head = (head - 1) & (elements.length - 1)] = e;    // 如果头尾挨在一起了，就扩容    // 扩容规则也很简单，直接两倍    if (head == tail)        doubleCapacity();}// 从队列尾入队public void addLast(E e) {    // 不允许null元素    if (e == null)        throw new NullPointerException();    // 在尾指针的位置放入元素    // 可以看到tail指针指向的是队列最后一个元素的下一个位置    elements[tail] = e;    // tail指针加1，如果到数组尾了就从头开始    if ( (tail = (tail + 1) & (elements.length - 1)) == head)        doubleCapacity();}

private void doubleCapacity() {    assert head == tail;    // 头指针的位置    int p = head;    // 旧数组长度    int n = elements.length;    // 头指针离数组尾的距离    int r = n - p; // number of elements to the right of p    // 新长度为旧长度的两倍    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);    // 将旧数组下标0到head之间的元素拷贝到新数组中    System.arraycopy(elements, 0, a, r, p);    // 赋值为新数组    elements = a;    // head指向0，tail指向旧数组长度表示的位置    head = 0;    tail = n;}

// 从队列头出队public E pollFirst() {    int h = head;    @SuppressWarnings("unchecked")    // 取队列头元素    E result = (E) elements[h];    // 如果队列为空，就返回null    if (result == null)        return null;    // 将队列头置为空    elements[h] = null;     // Must null out slot    // 队列头指针右移一位    head = (h + 1) & (elements.length - 1);    // 返回取得的元素    return result;}// 从队列尾出队public E pollLast() {    // 尾指针左移一位    int t = (tail - 1) & (elements.length - 1);    @SuppressWarnings("unchecked")    // 取当前尾指针处元素    E result = (E) elements[t];    // 如果队列为空返回null    if (result == null)        return null;    // 将当前尾指针处置为空    elements[t] = null;    // tail指向新的尾指针处    tail = t;    // 返回取得的元素    return result;}

public void push(E e) {    addFirst(e);}public E pop() {    return removeFirst();}