Java源碼閱讀之ArrayDeque

Summary：

• public class ArrayDeque<E> extends AbstractCollection<E> implements Deque<E>, Cloneable, Serializabletail
• 對象中有一個Obejct[]數組；該數組的容量為2的幂
• tail指向的位置不存儲資料；head指向的位置是隊列中第一個資料;
• 數組可以擴容，擴容後大小為原數組長度的2倍
• 數組中存儲的資料有(tail-head)&(elements.length-1)
• 資料添加的位置是tail；之後tail=（tail+1）&(elements.length-1)
• 資料移出的位置是head；之後head=（head+1）&(elements.length-1)

Fields：

transient Object[] elements;
transient int head;
transient int tail;
private static final int MIN_INITIAL_CAPACITY = 8;
           

Constructor：

public ArrayDeque() {
        elements = new Object[16];
}
public ArrayDeque(int numElements) {
        allocateElements(numElements);
}
//将轉換的數改成2的幂；這樣能将取餘運算替換為邏輯與運算
private void allocateElements(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
        }
        elements = new Object[initialCapacity];
}
           

size()

//注意：這裡很巧妙！！
public int size() {
        return (tail - head) & (elements.length - 1);
}
           

isEmpty() 

public boolean isEmpty() {
        return head == tail;
}
           

addXX():

添加元素預設将其添加到隊列尾端
           

public boolean add(E e) {
        addLast(e);
        return true;
}
public void addFirst(E e) {
        if (e == null)
            throw new NullPointerException();
        elements[head = (head - 1) & (elements.length - 1)] = e;
        if (head == tail)
            doubleCapacity();
}
public void addLast(E e) {
        if (e == null)
            throw new NullPointerException();
        elements[tail] = e;
        if ( (tail = (tail + 1) & (elements.length - 1)) == head)
            doubleCapacity();
}
           

removeXX():

移除元素預設移除第一個;隊列空抛異常
           

public E remove() {
        return removeFirst();
}
public E removeFirst() {
        E x = pollFirst();
        if (x == null)
            throw new NoSuchElementException();
        return x;
}
           

pollXX():

移除第一個元素，隊列空則傳回null
           

public E pollFirst() {
        int h = head;
        @SuppressWarnings("unchecked")
        E result = (E) elements[h];
        // Element is null if deque empty
        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];
        if (result == null)
            return null;
        elements[t] = null;
        tail = t;
        return result;
}
           

擴容：

//擴容擴兩倍
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];
        System.arraycopy(elements, p, a, 0, r);
        System.arraycopy(elements, 0, a, r, p);
        elements = a;
        head = 0;
        tail = n;
}