文章目录

Queue简介

Queue简介

Queue，即队列，是一个先进先出(First In First Out, FIFO)的数据结构，在JCF中也有很好的支持。和之间的分析步骤一样，我们先看一下接口的设计，再深入到具体实现类。

1. Queue接口

相对于List接口来说，Queue接口中支持的方法相对就比较少了，接口代码如下：

public interface Queue<E> extends Collection<E> {
    boolean add(E e); 		// 往队尾添加一个元素，失败抛出异常
    boolean offer(E e);		// 往队尾添加一个元素，失败返回false
    
    E remove();				// 检索到队头元素并删除，返回该队头，失败抛出异常
    E poll();				// 检索到队头元素并删除，返回该队头，失败返回null
    
    E element();			// 检索到队头元素，并返回该队头，失败抛出异常
    E peek();				// 检索到队头元素，并返回该队头，失败返回null

}

Queue接口不支持存放null元素。

这里有个问题需要关注，原来自己用的时候也没仔细想过，为什么好像有两套功能一样的方法？即add()和offer(),remove()和poll()，element()和peek()的区别是什么？

原来，二者区别的就是在操作失败时的处理上，就好比有两套约定，在Collection接口中规定，如果add()操作失败，则抛出相应的异常; 而offer()方法则规定，如果操作失败，返回false。remove()和poll()，element()和peek()的区别类似。

方法	返回值处理	方法	返回值处理
add()	失败抛出异常，有`IllegalStateException`,`ClassCastException`和`NullPointerException`三种异常。	offer()	失败返回false
remove()	失败抛出`NoSuchElementException`异常。	poll()	失败返回null
element()	失败抛出`NoSuchElementException`异常。	peek()	失败返回null

2. Deque接口

说完Queue接口，很自然地就会涉及到Deque接口。Deque，即Double End Queue，双端队列，顾名思义，就是可以在队头和队尾进行插入或删除操作，我们看下接口的设计，这里我们也只列举一部分：

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

Okay，和我们的猜想一模一样，至于为什么也有两套一样的方法嘛，和上面在Queue中的解释完完全全一样。

3. ArrayDeque实现类

ArrayDeque类是实现了Deque接口的，常见的使用方法如下：

Deque<String> dq=new ArrayDeque<>();
dq.add("jack");
dq.add("andy");
dq.add("rose");
System.out.println(dq.toString());  // 输出 [jack, andy, rose]

dq.removeLast();
System.out.println(dq.toString());  // 输出 [jack, andy]

我们一步步分析一下这个类的具体实现源代码，先看下这个类实现的接口和类属性。

public class ArrayDeque<E> extends AbstractCollection<E>
                           implements Deque<E>, Cloneable, Serializable
{
    transient Object[] elements;   	// 队列中的元素，底层用数组实现的
    transient int head;				// 队头
    transient int first;			// 队尾
    
    /**
     * The minimum capacity that we'll use for a newly created deque.
     * Must be a power of 2.
     */
    private static final int MIN_INITIAL_CAPACITY = 8;
 	
    // ...
}

3.1 构造函数

ArrayDeque的构造函数有三个，方法签名分别是ArrayDeque()、ArrayDeque(int numElements)和ArrayDeque(Collection<? extends E> c)，我们一个个来分析一下。

ArrayDeque()

此构造函数的实现十分的简单粗暴，直接缺省地把数组的容量声明为16。
1
2
3
public ArrayDeque() {
elements = new Object[16];
}

ArrayDeque(int numElements)

这个构造函数的功能是创建一个容量为用户指定初始大小的双端队列，私有方法如下。

public ArrayDeque(int numElements) {
    allocateElements(numElements);
}

// 开辟空间函数
private void allocateElements(int numElements) {
    int initialCapacity = MIN_INITIAL_CAPACITY; // 最小的初始化容量为8
    // Find the best power of two to hold elements.
    // Tests "<=" because arrays aren't kept full.
    if (numElements >= initialCapacity) {  // 如果用户指定的初始化容量大于8
        initialCapacity = numElements;
        initialCapacity |= (initialCapacity >>>  1); // >>>是不带符号右移 ，>>是带符号右移
        initialCapacity |= (initialCapacity >>>  2);
        initialCapacity |= (initialCapacity >>>  4);
        initialCapacity |= (initialCapacity >>>  8);
        initialCapacity |= (initialCapacity >>> 16);
        initialCapacity++; // 找到这样一个k，使得2^k > numElements

        if (initialCapacity < 0)   // Too many elements, must back off
            initialCapacity >>>= 1;// Good luck allocating 2 ^ 30 elements
    }
    elements = new Object[initialCapacity];
}

可以看到，关键就在于allocateElements()函数。该方法首先会判断用户指定的初始容量numElements是否比MIN_INITIAL_CAPACITY（也就是8）小，如果比8小，就直接开辟8个空间；如果比8大的话，代码会找到这样一个$k$，使得$2^k > numElements$，也就是上面不断右移的作用，这里举个例子，因为在Java中一个int是用4个字节来表示的，这里举例只考虑了4个bit的情况，对应则只需要右移2次。

假设用户声明的大小为5，即initialCapacity = 0101。initialCapacity |= (initialCapacity >>> 1)后，initialCapacity = 0111；再次右移initialCapacity |= (initialCapacity >>> 2)后，initialCapacity = 0111；最后initialCapacity++，此时initialCapacity = 1000，对应的十进制数为-8，于是经过if判断再次右移一位，initialCapacity又等于 0100，即十进制4。

也就是说，实际队列能分配的最大初始容量其实也就是$2^{n-2}$，其中$n$为二进制位数，即在Deque中，最大也就允许用户初始化容量为$2^{30}$。

ArrayDeque(Collection<? extends E> c)

这个构造函数就比较简单了，和之前在List中的分析差不多，代码如下。
1
2
3
4
public ArrayDeque(Collection<? extends E> c) {
allocateElements(c.size());
addAll(c);
}

3.2 add相关操作

我们从最简单的add(E e)开始往下分析。

public boolean add(E e) {
    addLast(e);
    return true;
}

public void addLast(E e) {
    if (e == null)  // 不允许插入null
        throw new NullPointerException();
    elements[tail] = e; // 插入队尾
    
    if ( (tail = (tail + 1) & (elements.length - 1)) == head) // tail下标+1，尾巴和头相遇了，说明队列满了
        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];
    System.arraycopy(elements, p, a, 0, r);  // 把原队头右边的r个元素搬到新数组从0开头的位置
    System.arraycopy(elements, 0, a, r, p);   // 把原队尾左边的p个元素搬到新数组从r开头的位置
    elements = a;  
    head = 0; // 队头置为0
    tail = n; // 队尾置为n
}

从源码我们就可以知道，add(E e)方法默认是在队尾插入的（这也是必须的，因为这就是朴素队列的性质！），然后会调用addLast(E e)方法，在这里，是不允许插入null元素的，而在List中是允许存在null对象的，这个需要注意。插入一个元素后，如果队列满了，会进行扩容操作，这里用的是双倍扩容，并会相应地把原队头右边的r个元素搬到新数组从0开头的位置，并把原队尾左边的p个元素搬到新数组从r开头的位置。

有了上面的基础，我们再来看下addFirst(E e)方法，注意，这个方法只有在双端队列中才有，朴素的队列是不支持在队头插入元素的，这相当于我们平时生活中的”插队“操作，而且是直接插到最前面去。

public void addFirst(E e) {
    if (e == null)
        throw new NullPointerException();
    elements[head = (head - 1) & (elements.length - 1)] = e;  // head 下标-1
    if (head == tail)  // 如果head 和tail相遇，就扩容
        doubleCapacity();
}

总结：add操作的时间复杂度为$O(1)$。如果碰到要扩容的情况，则空间复杂度为$O(N)$,其中$N$为队列中当前容量。

3.3 offer相关操作

offer()就是对add()函数的一个包装，即在队尾添加一个元素。

// 操作成功返回true，如果入参e是null，还是会抛出NullPointerException异常
public boolean offer(E e) {
    return offerLast(e);
}

public boolean offerLast(E e) {
    addLast(e);
    return true;
}

很自然，offerFrst(E e)则是对addFrst(E e)的一个包装了。

public boolean offerFirst(E e) {
    addFirst(e);
    return true;
}

3.4 remove相关操作

删除相关的操作也比较多，有朴素队列中的remove()，默认是从队头删除一个。在实现了Deque接口的类中，你也可以在队尾删除一个元素，就好比一个人排队，排着排着等得不耐烦就溜了。我们也简单看下源码实现方式。

先看下removeLast()函数：

// 从队尾删除一个元素
public E removeLast() {
    E x = pollLast();
    if (x == null)
        throw new NoSuchElementException();
    return x;
}

// 从队尾删除
public E pollLast() {
    int t = (tail - 1) & (elements.length - 1); // tail的上一个位置是最后一个元素
    @SuppressWarnings("unchecked")
    E result = (E) elements[t];
    if (result == null)
        return null;
    elements[t] = null;
    tail = t;
    return result;
}

这里有个地方我们需要注意，在队列中，tail下标指向的那个元素其实是下一次添加时存放的位置，所以tail的上一个位置才是最后一个元素，于是在pollLast()函数中的操作就是先找到队尾那个元素，并保留。然后把队尾向前移动一个单位，最后返回之前保留的原队尾元素。

当然，朴素队列中的删除操作默认是从队首删除，代码也很类似。

public E remove() {
    return removeFirst();
}

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

public E pollFirst() {
    int h = head;  // 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;
}

poll()系列方法则是对remove()系列方法的包装。

总结：remove操作时间复杂度为$O(1)$，删除时是不会涉及到释放容量这一说法的。

3.5 peek相关操作

peek()就是返回队列的队首元素了，当返回值为null的时候，说明队列是空的。

public E peek() {
    return peekFirst();
}
public E peekFirst() {
    // elements[head] is null if deque empty
    return (E) elements[head];
}

peekFirst()、peekLast()的分析和前面类似，就不再赘述。element()系列方法则是对`peek()系列方法的包装。

4. LinkedList实现类

LinkedList即可以作为朴素队列Queue接口的实现类来使用，也可以作为双端队列Deque接口的实现类来使用。LinkedList的源码分析可以参阅之前的文章>>Java集合-List篇<<，LinkedList作为朴素队列来使用的代码如下：

Queue<String> q=new LinkedList<>();
q.add("jack");
q.add("andy");
q.add("rose");
System.out.println(q.toString());  // 输出 [jack, andy, rose]

q.remove();
System.out.println(q.toString());  // 输出 [andy, rose]

这里我们只再次看下相关方法是如何包装的。

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    // 添加元素操作
	public boolean add(E e) {
        linkLast(e);  // 尾插法
        return true;
    }

    // 删除元素操作
    public E remove() {
        return removeFirst();  // 删除第一个结点
    }
    
    // 得到队首结点
    public E peek() {
        final Node<E> f = first;
        return (f == null) ? null : f.item;
    }
    
    // ...
}

总结：对于一个底层用LinkedList实现的队列，其删除和添加操作的时间复杂度都是$O(1)$，空间复杂度也都是$O(1)$。

Java集合—Queue篇

Queue、Deque、LinkedList、ArrayDeque