[Java]-Collection源码分析-Queue

发表于 | 分类于 | 阅读次数

Queue是一个超级接口，继承关系如下：

有如下方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//将元素插入队列，往满队列里加入元素抛出异常
boolean add(E e);

//将元素插入队列，与add相比，在容量受限时应该使用这个，在满队列里加入元素返回false
boolean offer(E e);

//将队首的元素删除，队列为空则抛出异常
E remove();

//将队首的元素删除，队列为空则返回null
E poll();

//获取队首元素，但不移除，队列为空则抛出异常
E element();

//获取队首元素，但不移除，队列为空则返回null
E peek();

它的超级实现类AbstractQueue仅实现了add、remove和element三个方法,使其更安全。 add方法调用了offer, remove方法调用了poll， element调用了peek：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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();
}

Queue有一个子接口Deque（Double ended queue），双向队列。双向队列允许插队到队头，允许队尾离开。同时它实现了stack

1
2
3
4
5
//与addFirst()等价
void push(E e);

//与removeFirst()等价
E pop();

Queue实现类ArrayDeque

可动态调整大小的数组来实现了Deque，和ArrayList有点相似，但实现不同。ArrayDeque的动态大小总是2的次幂，而不是每次增长1.5倍。

成员变量

1
2
3
4
5
6
7
8
9
10
11
12
//存放元素，长度和capacity一致，并且总是2的次幂
//这一点，我们放在后面解释
transient Object[] elements; 

//capacity最小值，也是2的次幂
private static final int MIN_INITIAL_CAPACITY = 8;

//标记队首元素所在的位置
transient int head;

//标记队尾元素所在的位置
transient int tail;

##构造函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
//无参，默认大小16
public ArrayDeque() {
    elements = new Object[16];
}

//队列大小为参数
public ArrayDeque(int numElements) {
    allocateElements(numElements);
}

//集合为参数
public ArrayDeque(Collection<? extends E> c) {
    allocateElements(c.size());
    addAll(c);
}

//new一个大小为calculateSize(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;
}

在定义elements变量时说，其长度总是2的次幂，但用户传入的参数并不一定符合规则，所以就需要根据用户的输入，找到比它大的最近的2次幂。比如用户输入13，就把它调整为16，输入31，就调整为32，calculateSize就是完成了这样一个计算，位运算的代码解析可以看这个链接：
https://www.jianshu.com/p/1c1c3f24762e。这个方法让我们找到合适的2次幂。

|按位或

>>> 忽略符号位右移

方法

循环数组，添加元素，在队尾添加，在队头添加，位运算，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//在队首添加一个元素，非空
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();
}

&：按位与。两个数相与，只有都为1的时候才是1，一个正数m和一个数n与得m mod n，和-数与相当于取补码，所以说这个数组实际上是个循环队列。

队列满的情况就是tail == head，这时的扩容策略时直接翻倍。