Queue源码分析

作者: 都是浮云啊 | 来源:发表于2018-09-27 23:58 被阅读2次

Java ArrayDeque
LinkedList与Queue源码分析
GCD-源码分析
Queue源码分析
GCD底层源码分析
Queue、Deque、ArrayDeque源码分析
afl++ parallel分析
第四届中间件性能挑战赛冠军代码解析-复赛C代码
Python 源码分析：queue 队列模块
Python 源码分析：queue 队列模块！

前言：

队列在并发编程中使用的频率很高,正如生活中车辆在道路的行驶其实就类似并发。如果没有交通规则、红绿灯、交警这些,那交通很杂乱无章。所以才有了这一些列的车道。这些车道在笔者看来就类似一个个的队列，通过一个个的队列实现程序的有序进行，是实现并发的基础之一。那么什么是队列呢？

什么是Queue？
队列就是一个FIFO的数据结构，Queue和List以及Set属于同一级别都是继承Cllection接口。实际上Queue有多种实现，有的采用线性表，有的基于链表实现，它们都有着自己适配的场景。

队列有哪些功能？如何使用的？
Queue中的方法主要有下面6个，主要分为2种，这2种方法在处理失败的操作不同

a. 添加一个元素 boolean add(E e)VS boolean offer(E e) ，二者都是向队列的尾部添加一个元素，对于一些对队列的大小有限制的，当队列满了就拒绝元素加入了，此时add方法抛出异常，offer返回的是false无异常抛出。当然添加成功都是返回true。
b. 移除队首元素E remove(E e)VSE poll(E e)，当移除之前队列为空时,remove抛出异常，poll返回null无异常抛出
c. 查看队首元素E element()VSE peel()同样的，当队列为空时，element抛出异常,peek返回null无异常抛出。

1、Deque<E>
Deque是一个线性双端队列，支持在2端插入和移除元素，继承自
Queue，所以此接口可以定义队列的容量也可以不定义没有大小限制。此接口主要定义了双端队列2个端的元素操作，包含插入移除和检查等方法，遵循Queue的方法设计，每种方法存在2种形式，失败时抛异常和返回特殊值。看下方法对比，其实就相当于2个Queue接到一起的感觉。

void addFirst(E e); VS boolean offerFirst(E e);
void addLast(E e); VS boolean offerLast(E e);
E removeFirst(); VS E pollFirst();
E removeLast(); VS E pollLast();
E getFirst(); VS E peekFirst();
E getLast(); VS E peekLast();
以上方法全都见名知意，且对比也是如上述描述所说的。增加了2个挺实用的方法：
从双端队列移除第一次出现的指定元素boolean removeFirstOccurrence(Object o);
从双端队列移除最后一次出现的指定元素 boolean removeLastOccurrence(Object o);
除此之外还有一个很大的特点，重新定义了Queue中接口的方法
boolean contains(Object)判断双端队列是否包含元素

模仿栈的操作，后进先出（LIFO），提供如下方法：
void push(E e)把一个元素压栈,无空间时抛出IllegalStateException
E pop(); 出栈

2、AbstractQueue<E>
也是实现了Queue<E>的接口，在这个抽象类中对Queue<E>中的方法进行了简单的实现例如：

add方法,可以看到对于Queue所有的2种方式进行了相互的调用

  public boolean add(E e) {
        if (offer(e))
            return true;
        else
            throw new IllegalStateException("Queue full");
    }

  public E remove() {
        E x = poll();
        if (x != null)
            return x;
        else
            throw new NoSuchElementException();
    }

 public E element() {
        E x = peek();
        if (x != null)
            return x;
        else
            throw new NoSuchElementException();
    }

2、ArrayDeque<E>

ArrayDeque<e>是JDK6中引入的实现,如下源码所示,ArrayDeque同时拥有AbstractCollection<E>和Deque<E>的特性,本身队列是基于FIFO的，但是由于JDK6中Deque<E>接口的实现，ArrayDeque拥有了双端队列的特性可以在头部和尾部进行操作。

public class ArrayDeque<E> extends AbstractCollection<E>
                           implements Deque<E>, Cloneable, Serializable{
                           }

ArrayDeque的内部依然是数组elements，ArrayDeque通过头部索引-tail，尾部索引-tail、内部数组-elements维护队列的结构。底层重载了2个构造方法

//1.无参构造方法,默认初始一个长度为16的数组
 public ArrayDeque() {
        elements = new Object[16];
    }
//2.有参构造方法,当指定的长度小于8的时候，初始化一个长度为8的数组。若指定的长度大于8，根据一系列的运算规则，大于numElements最近的2的n方作为初始长度。例如numElements为11,则长度为16
public ArrayDeque(int numElements) {
        allocateElements(numElements);
    }
private void allocateElements(int numElements) {
        elements = new Object[calculateSize(numElements)];
    }
private 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;
    }
//3. 把几个单列集合作为参数进行构建初始化操作，并将集合加入到队列中。长度的规则同上2
public ArrayDeque(Collection<? extends E> c) {
        allocateElements(c.size());
        addAll(c);
    }