七、Collection 子接口之 Queue

7.1 Queue 与 Deque 的区别

01、Queue

Queue 是单列队列，只能从一端插入元素，另一端删除元素，实现上一般遵循先进先出（FIFO）规则。

Queue 扩展了 Collection 的接口，根据因为容量问题而导致操作失败后处理方式的不同可以分为两类方法：

  1. 在操作失败后会抛出异常
  2. 返回特殊值
Queue 接口 抛出异常 返回特殊值
插入队尾 add(E e) 失败则抛出异常 offer(E e) 失败则返回 false
删除队首 remove() 失败则抛出异常 poll() 失败则返回 null
查询队首元素 element() 失败则抛出异常 peek() 失败则返回 null

02、Deque

·Deque（double ended queue）是双端队列·，在队列的两端均可以插入或删除元素，它既可以当做栈使用，也可以当做队列使用。

Deque 扩展了 Queue 的接口，增加了在队首和队尾进行插入和删除的方法，同样是根据失败后处理方式的不同分为两类：

Deque 接口 抛出异常 返回特殊值
插入队首 addFirst() 失败则抛出异常 offerFirst() 失败则返回 false
插入队尾 add(E e) 失败则抛出异常 offer(E e) 失败则返回 false
删除队首 removeFirst() 失败则抛出异常 pollFirst() 失败则返回 null
删除队尾 removeLast() 失败则抛出异常 pollLast() 失败则返回 null
查询队首元素 getFirst() 失败则抛出异常 peekFirst() 失败则返回 null
查询队尾元素 getLast() 失败则抛出异常 peekLast() 失败则返回 null

一共定义了 Deque 的 12 个接口，添加、删除、取值都有两套接口，它们功能相同，区别就是对失败情况的处理不同。

一套接口遇到失败就会抛出异常，另一套遇到失败就会返回特殊值（false 或 null）。除非某种实现对容量有限制，大多数情况下，添加操作是不会失效的。

03、Stack

Stack 接口 抛出异常
插入栈顶 push(e) 失败则抛出异常
删除栈顶元素 pop() 失败则抛出异常
获取栈顶元素 peek() 失败则抛出异常

7.2 ArrayDeque

ArrayDeque 和 LinkedList 是 Deque 的两个通用实现，官方更推荐使用 ArrayDeque 用作栈和队列。

从名字可以看出 ArrayDeque 底层是通过数组实现的，为了满足可以同时在数组两端插入或删除元素的需求，该数组还必须是循环的，即循环数组，也就是说数组的任何一点都可能被看做起点或者终点。

ArrayDeque 是非线程安全的，当多个线程同时使用的时候，需要手动同步，并且该容器中不允许存放 null 元素。

ArrayDeque 中 head 指向首端第一个有效元素，tail 指向尾端第一个可以插入元素的空位。因为是循环数组，所以 head 不一定总等于 0，tail 也不一定总是比 head 大：
在这里插入图片描述

01、addFirst()

addFirst(E e) 的作用就是在 Deque 的首端插入元素，也就是在 head 前面插入元素，在空间足够且下标没有越界的情况下，只需要将 elements[--head] = e 即可。
在这里插入图片描述

实际需要考虑：

  1. 空间是否够用
  2. 下标是否越界

在上面添加的过程中，head 已经为 0 了，如果再次调用 addFirst() 方法进行添加时，虽然空余空间还够用，但是 head 就会变成 -1，下标越界了。

扒一下 addFirst() 方法的源码：

public class ArrayDeque<E> extends AbstractCollection<E>
                           implements Deque<E>, Cloneable, Serializable
{
	public void addFirst(E e) {
		// 不允许放入 null 值
	    if (e == null)
	        throw new NullPointerException();
	    // 下标是否越界
	    elements[head = (head - 1) & (elements.length - 1)] = e;
	    // 收尾指针相同，空间不够用
	    if (head == tail)
	    	// 扩容
	        doubleCapacity();
	}
}

可以看到，空间问题是在插入之后解决的，因为 tail 总是指向下一个可以插入的空位，也就意味着 elements 数组至少有一个空位，所以插入元素的时候不用考虑空的问题。

下标越界的处理解决起来还是比较简单的：head = (head - 1) & (elements.length - 1)，这段代码相当于取余，同时解决了 head 为负数的问题。由于 elements 必须是 2 的指数倍，elements - 1就是二进制低位全 1，跟 head - 1 相与之后就起到了取模的作用 。如果 head - 1 为负数（实际上也只可能是 -1），则相当于对其取相对于 elements.length 的补码。

-1 的原码(最高位是符号位，0正1负)：1000 0001，补码(符号位不变，原码+1)：1111 1111
elements.length 一定是一个正数，正数的补码是其本身
取模运算，如果相对应位都是1，则结果为1，否则为0。

接着会调用扩容函数 doubleCapacity()，其逻辑是申请一个更大的数组（原数组的两倍），然后将原数组复制过去：

private void doubleCapacity() {
    assert head == tail;
    int p = head;
    int n = elements.length;
    // head 右边元素的个数
    int r = n - p; // number of elements to the right of p
    // 原空间的 2 倍
    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;
}

在这里插入图片描述

02、addLast()

addLast(E e) 的作用是在 Deque 的尾端插入元素，也就是在 tail 的位置插入元素，由于 tail 总是指向下一个可以插入的空位，因此只需要 elementd[tail] = e 即可。插入完成后再检查空间，如果空间已经用光，则可以调用 doubleCapacity() 进行扩容。
JavaSE进阶之（七）Collection 子接口之 Queue-小白菜博客
扒一下 addLast() 方法的源码：

public class ArrayDeque<E> extends AbstractCollection<E>
                           implements Deque<E>, Cloneable, Serializable
{
	public void addLast(E e) {
		// 不允许放入空值
	    if (e == null)
	        throw new NullPointerException();
	    // 赋值
	    elements[tail] = e;
	    // 下标越界处理，与 addFirst() 相同
	    if ( (tail = (tail + 1) & (elements.length - 1)) == head)
	    	// 扩容
	        doubleCapacity();
	}
}

03、pollFirst()

pollFirst() 方法的作用是删除并返回 Deque 首端元素，也就是 head 位置处的元素。如果容器不空，只需要直接返回 elements[head] 即可，但是下标越界问题仍然需要处理。由于 ArrayDeque 中不允许存放 null 值，当 elements[head] == null 时，意味着容器为空：

public class ArrayDeque<E> extends AbstractCollection<E>
                           implements Deque<E>, Cloneable, Serializable
{
	public E pollFirst() {
	    int h = head;
	    @SuppressWarnings("unchecked")
	    E result = (E) elements[h];
	    // Element is null if deque empty
	    // 如果为 null，说明容器为空
	    if (result == null)
	        return null;
	    elements[h] = null;     // Must null out slot
	    // 下标越界处理
	    head = (h + 1) & (elements.length - 1);
	    return result;
	}
}

04、pollLast()

pollLast() 的作用是删除并返回 Deque 尾端元素，也就是 tail 位置前面的那个元素：

public class ArrayDeque<E> extends AbstractCollection<E>
                           implements Deque<E>, Cloneable, Serializable
{
	public E pollLast() {
		// tail 的上一个位置是最后一个元素
        int t = (tail - 1) & (elements.length - 1);
        @SuppressWarnings("unchecked")
        E result = (E) elements[t];
        // null 值意味着 deque 为空
        if (result == null)
            return null;
        elements[t] = null;
        tail = t;
        return result;
    }
}

05、peekFirst()

peekFirst() 的作用是返回但不删除 Deque 首端元素，也就是 head 位置处的元素，直接返回 elements[head] 即可：

public class ArrayDeque<E> extends AbstractCollection<E>
                           implements Deque<E>, Cloneable, Serializable
{
	public E peekFirst() {
	    // elements[head] is null if deque empty
	    return (E) elements[head];
	}
}

06、peekLast()

peekLast() 的作用是返回但不删除 Deque 尾端元素，也就是 tail 位置前面的那个元素：

public class ArrayDeque<E> extends AbstractCollection<E>
                           implements Deque<E>, Cloneable, Serializable
{
	public E peekLast() {
	   return (E) elements[(tail - 1) & (elements.length - 1)];
	}
}

7.3 ArrayDeque 与 LinkedList 的区别

ArrayDeque 和 LinkedList 都实现了 Deque 接口，两个接口都具有队列的功能，其区别如下：

  1. ArrayDeque 是基于可变长的数组和双指针来实现，而 LinkedList 则通过链表来实现；
  2. ArrayDeque 不支持存储 null 数据，但 LinkedList 支持；
  3. ArrayDeque 是在 JDK 1.6 才被引入的，而 LinkedList 早在 JDK 1.2 时就已经存在；
  4. ArrayDeque 插入时可能存在扩容过程，不过均摊后的插入操作依然为 O(1)。虽然 LinkedList 不需要扩容，但是每次插入数据时均需要申请新的堆空间，均摊性能相比更慢；

从性能的角度上，选用 ArrayDeque 来实现队列要比 LinkedList 更好。

7.4 PriorityQueue

PriorityQueue 叫做优先队列，它的作用是能保证每次取出的元素都是队列中权值最小的（Java 的优先队列每次取最小元素，C++ 的优先队列每次取最大元素）。

这里的大小关系的评判可以通过元素本身的自然顺序（natural ordering），也可以通过构造时传入的比较器（Comparator，类似于 C++ 的仿函数）。

Java 中的 PriorityQueue 实现了 Queue 接口，不允许存放 null 元素；它是通过堆实现的，具体说是通过完全二叉树（complete binary tree）实现的小顶堆（任意一个非叶子节点的权值，都不大于其左右节点的权值），也就意味着可以通过数组来作为 PriorityQueue 的底层实现。

JavaSE进阶之（七）Collection 子接口之 Queue-小白菜博客
给每个元素按照层序遍历的方式进行了编号，会发现父节点和子节点的编号是由联系的：

leftNo = parentNo * 2 +1
rightNo = parentNo * 2 + 2
parentNo = (nodeNo - 1) / 2

由此可见，可以通过公式轻易地计算出某个节点的父节点及子节点的下标，这也就是为什么可以直接用数组来存储堆的原因。

PriorityQueue 的 peek() 和 element 操作是常数时间，add()、offer(), 无参数的 remove() 以及 poll() 方法的时间复杂度都是log(N)。

01、add() 和 offer()

add(E e) 和 offer(E e) 的语义相同，都是向优先队列中插入元素，只是 Queue 接口规定对插入失败时的处理不同，add(E e) 在插入失败时抛出异常，offer(E e) 在插入失败时则会返回 false。而对于 PriorityQueue 来说，这两个方法其实没有什么差别。

在上面的优先队列上插入一个元素：
JavaSE进阶之（七）Collection 子接口之 Queue-小白菜博客
新加入的元素可能会破坏小顶堆的性质，因此需要进行必要的调整：

public class PriorityQueue<E> extends AbstractQueue<E>
    implements java.io.Serializable {
	public boolean offer(E e) {
		// 不允许放入 null 值
        if (e == null)
            throw new NullPointerException();
        modCount++;
        int i = size;
        if (i >= queue.length)
        	// 自动扩容，类似于 Arraylist 里的 grow() 方法
            grow(i + 1);
        size = i + 1;
        if (i == 0)
        	// 队列原来为空，这是插入的第一个元素
            queue[0] = e;
        else
        	// 调整
            siftUp(i, e);
        return true;
    }
}

其中，扩容函数 grow() 类似于 ArrayList 里的 grow() 函数，就是再申请一个更大的数组，并将原数组的元素复制过去。

需要注意的是 siftUp(int k, E x) 方法，该方法用于插入元素 x 并维持堆的特性：

private void siftUp(int k, E x) {
    if (comparator != null)
        siftUpUsingComparator(k, x);
    else
        siftUpComparable(k, x);
}

private void siftUpUsingComparator(int k, E x) {
    while (k > 0) {
    	// parentNo = (nodeNo - 1) / 2
        int parent = (k - 1) >>> 1;
        Object e = queue[parent];
        // 调用比较器的比较方法
        if (comparator.compare(x, (E) e) >= 0)
            break;
        queue[k] = e;
        k = parent;
    }
    queue[k] = x;
}

调整的过程是这样的：从 k 指定的位置开始，将 x 逐层与当前点的 parent 进行比较并交换，直到满足 x >= queue[parent] 为止。

注意：这里的比较可以是元素的自然顺序，也可以是依靠比较器的顺序。

02、element() 和 peek()

element() 和 peek() 的语义完全相同，都是获取但不删除队首元素，也就是队列中权值最小的那个元素，二者唯一的区别就是当方法失败时 element() 抛出异常，peek() 返回null。

根据小顶堆的性质，堆顶那个元素就是全局最小的那个；由于堆用数组表示，根据下标关系，0 下标处的那个元素即是堆顶元素。所以直接返回数组 0 下标处的那个元素即可：
JavaSE进阶之（七）Collection 子接口之 Queue-小白菜博客
扒一下 peek() 方法的源码：

public E peek() {
	// 0 下标处的那个元素就是最小的那个
    return (size == 0) ? null : (E) queue[0];
}

03、remove() 和 poll()

remove() 和 poll() 方法的语义也完全相同，都是获取并删除队首元素，区别是当方法失败时 remove() 抛出异常，poll() 返回null。由于删除操作会改变队列的结构，为维护小顶堆的性质，需要进行必要的调整。
JavaSE进阶之（七）Collection 子接口之 Queue-小白菜博客
扒一下 poll() 方法的源码：

public E poll() {
    if (size == 0)
        return null;
    int s = --size;
    modCount++;
    // 0 下标处的那个元素是最小的那个
    E result = (E) queue[0];
    E x = (E) queue[s];
    queue[s] = null;
    if (s != 0)
    	// 调整
        siftDown(0, x);
    return result;
}

首先记录 0 下标处的元素，并用最后一个元素替换 0 下标位置的元素，之后调用 siftDown() 方法对堆进行调整，最后返回原来0下标处的那个元素（也就是最小的那个元素）。重点是 siftDown(int k, E x) 方法，这个方法的作用是从 k 指定的位置开始，将 x 逐层向下与当前点的左右孩子中较小的那个交换，直到 x 小于或等于左右孩子中的任何一个为止。

扒一下 siftDown(int k, E x) 方法的源码：

private void siftDown(int k, E x) {
    if (comparator != null)
        siftDownUsingComparator(k, x);
    else
        siftDownComparable(k, x);
}

private void siftDownUsingComparator(int k, E x) {
	// 相当于 half = size / 2 位运算效率高
    int half = size >>> 1;
    while (k < half) {
    	// 首先找到左右孩子中较小的那个，记录到 c 里，并用 child 记录其下标
    	// leftNo = parentNo * 2 + 1
        int child = (k << 1) + 1;
        Object c = queue[child];
        // reighNo = parentNo * 2 + 2 = leftNo + 1
        int right = child + 1;
        if (right < size &&
            comparator.compare((E) c, (E) queue[right]) > 0)
            c = queue[child = right];
        if (comparator.compare(x, (E) c) <= 0)
            break;
        // 用 c 把原来的值给覆盖掉
        queue[k] = c;
        k = child;
    }
    queue[k] = x;
}

04、remove(Obbject o)

remove(Object o) 方法用于删除队列中跟 o 相等的某一个元素（如果有多个相等，只删除一个），该方法不是 Queue 接口内的方法，而是 Collection 接口的方法。

由于删除操作会改变队列结构，所以要进行调整；又由于删除元素的位置可能是任意的，所以调整过程比其它函数稍加繁琐。具体来说，remove(Object o) 可以分为 2 种情况：

  1. 删除的是最后一个元素。直接删除即可，不需要调整。
  2. 删除的不是最后一个元素，从删除点开始以最后一个元素为参照调用一次 siftDown() 即可。

JavaSE进阶之（七）Collection 子接口之 Queue-小白菜博客
扒一下 remove(Obbject o)方法的源码：

public boolean remove(Object o) {
	// 通过遍历数组的方式找到第一个满足 o.equals(queue[i]) 元素的下标
    int i = indexOf(o);
    if (i == -1)
        return false;
    else {
        removeAt(i);
        return true;
    }
}

private E removeAt(int i) {
    // assert i >= 0 && i < size;
    modCount++;
    int s = --size;
    // 情况一
    if (s == i) // removed last element
        queue[i] = null;
    else {
        E moved = (E) queue[s];
        queue[s] = null;
        // 情况二
        siftDown(i, moved);
        if (queue[i] == moved) {
            siftUp(i, moved);
            if (queue[i] != moved)
                return moved;
        }
    }
    return null;
}

05、要点

PriorityQueue 是在 JDK 1.5 中被引入的，其中与 Queue 的区别在于元素出队顺序是与优先级相关的，即总是优先级最高的元素先出队。

要点：

  1. PriorityQueue 利用了二叉堆的数据结构来实现，底层使用可变长的数组来存储数据；
  2. PriorityQueue 通过堆元素的上浮和下沉，实现了在 O(log n) 的时间复杂度内插入元素和删除堆顶元素；
  3. PriorityQueue 是非线程安全的，且不支持存储 null 和 non-comoarable 的对象；
  4. PriorityQueue 默认是小顶堆，但可以接收一个 Comparator 作为构造参数，从而来自定义元素优先级的先后。