JDK源码-Queue系列

Queue

• queue默认采用的是FIFO原则.add,offer操作都是将元素添加到队列末尾.remove,poll操作返回的都是queue的头元素.
• queue为empty时,remove,element操作将会throws NoSuchElementException,而poll,peek操作将会返回null.
• queue的容量满足时,继承自Collection的add方法,将会throw new IllegalStateException("Queue full")；而offer方法描述的是一种正常情况,例如将元素插入固定容量的队列时很容易无法插入.

Deque

• 双端队列:double ended queue
• 包含方法:

• 适用场景:
  一般场景,LinkedList,链表双端队列,允许元素为null；ArrayDeque,数组双端队列,不允许元素为null.
  并发场景下,使用BlockingDeque接口下的一些实现.

ArrayDeque

• 人如其名,ArrayDeque底层是通过一个循环数组实现的.

方法剖析

• void allocateElements(int numElements)
  通过传入的numElements,初始化底层存储数组.

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];
    }

其中,最关键的地方是其中的位或运算.首先,那一大串的位或运算的目的是为了得到传入的numElements的下一个2的次方数.比如传入的10,则得到16；传入16,得到32.那么经过五次的位或运算和右移运算就能够得到2^k-1的数了.看下图:

最后,得到的数加1即可.这样运算的目的是为了提高效率,毕竟计算机对二进制数的处理是最快的.

• void addFirst(E e)
  向队列头部添加元素.这里要注意的有几点,插入头的时候,有可能head正好是指向数组第一个元素,这时候就会发生越界问题.

head = (head - 1) & (elements.length - 1),这个与操作完美的解决了越界问题.
由于数组大小elements.length无论在初始化或者扩容时,都是的2的倍数,所以这里-1之后,剩下的所有位上都是1,与head-1与操作之后,正好达到了取模的操作.
即当head-1大于0,则(head - 1) & (elements.length - 1)等于head；当head-1 等于-1,(head - 1) & (elements.length - 1).元素此时放到数组的最后一个位置.

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

当head=tail时,说明数组容量已经被用光了,就设计到了扩容的问题.

• void doubleCapacity()
  该方法会将原来数组容量扩充为两倍,扩充的容量如果超过计算机整数的限制,就会抛出异常.扩充的操作其实是对原来的数据copy了两次,第一次是将头部的位置到数组的尾部的数据copy到新的数组,第二次将头部的位置到数组的首部的数据跟着copy到新的数组.

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;
    }

• void addLast(E e)
  在队列尾部添加元素,直接会添加到数组对应的tail下标的位置.因为tail默认会指向数据中空的位置,则不用考虑越界的问题.
  当该tail+1大于elements.length - 1时,tail会指向0

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

• E pollFirst()
  从头部删除元素时,获取到头部坐标,将对应位置元素置为null,并将head移至上一个下标,head小于0时,则变为数组长度-1

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;
    }