Android Java实用数据结构系列（三）：Queue（上篇）

传送门：Java（Android）数据结构汇总 -- 总纲

简介

这篇文章我们来整理下基于Queue接口实现的数据结构类。Queue（队列）的特性就是先进先出（FIFO）。所以它主要定义了一些队列的操作方法。另外还有个基于它的接口Deque。Deque同时具有队列和栈的特性，也就是即可以先进先出，也可以后进先出（LIFO）。

先来看一下Queue和Deque这两个接口的定义：

public interface Queue<E> extends Collection<E> {
    // 在队列尾部添加一个元素，如果添加失败（如超出了容量限制）则会抛出IllegalStateException异常
    boolean add(E e);
    // 在队列尾部添加一个元素，如果添加失败（如超出了容量限制）则会返回false，否则返回true
    boolean offer(E e);

    // 移除一个队列头部的元素，如果队列为空则返回null
    E poll();
    // 移除一个队列头部的元素，如果队列为空则抛出NoSuchElementException异常
    E remove();

    // 查看队列头部的元素（不会从队列中移除），如果队列为空则返回null
    E peek();
    // 查看队列头部的元素（不会从队列中移除），如果队列为空则抛出NoSuchElementException异常
    E element();
}

// Deque可理解为是一个同时支持队列和栈操作的有序容器，它的方法可分为三部分
public interface Deque<E> extends Queue<E> {
    // ============================ 第一部分：栈和队列的混合操作 ====================================
    // 在容器头部添加一个元素，如果添加失败（如超出了容量限制）则会抛出IllegalStateException异常
    void addFirst(E e);
    // 在容器头部添加一个元素，如果添加失败（如超出了容量限制）则会返回false，否则返回true
    boolean offerFirst(E e);

    // 在容器尾部添加一个元素，如果添加失败（如超出了容量限制）则会抛出IllegalStateException异常
    void addLast(E e);
    // 在容器尾部添加一个元素，如果添加失败（如超出了容量限制）则会返回false，否则返回true
    boolean offerLast(E e);

    // 移除容器头部的元素，如果容器为空则会抛出NoSuchElementException异常
    E removeFirst();
    // 移除容器头部的元素，如果容器为空则会返回nul
    E pollFirst();

    // 移除容器尾部的元素，如果容器为空则会抛出NoSuchElementException异常
    E removeLast();
    // 移除容器尾部的元素，如果容器为空则会返回null
    E pollLast();

    // 获取容器头部的元素（不会从容器中移除），如果容器为空则会抛出NoSuchElementException异常
    E getFirst();
    // 获取容器头部的元素（不会从容器中移除），如果容器为空则会返回nul
    E peekFirst();

    // 获取容器尾部的元素（不会从容器中移除），如果容器为空则会抛出NoSuchElementException异常
    E getLast();
    // 获取容器尾部的元素（不会从容器中移除），如果容器为空则会返回nul
    E peekLast();

    // 从容器头部开始查找第一个和指定元素相等的元素并将其移除，如果存在指定元素且成功移除则返回true，否则返回null
    boolean removeFirstOccurrence(Object o);

    // 从容器尾部开始查找第一个和指定元素相等的元素并将其移除，如果存在指定元素且成功移除则返回true，否则返回null
    boolean removeLastOccurrence(Object o);

    // ================================ 第二部分：队列操作 ========================================
    // 这部分请看前面的Queue接口注释
    boolean add(E e);
    boolean offer(E e);
    E poll();
    E remove();
    E peek();
    E element();

    // ================================= 第三部分：栈操作 =========================================
    // 压栈，往栈顶（容器头部）添加一个元素，如果添加失败（如超出了容量限制）则会抛出IllegalStateException异常
    void push(E e);

    // 出栈，取出栈顶（容器头部）元素，如果栈为空则会抛出NoSuchElementException异常
    E pop();

    // 和removeFirstOccurrence相等
    boolean remove(Object o);
}

可见，Queue和Deque定义的方法基本都是成对出现的。区别只是在与当处理失败的时候一个是抛出异常，一个是返回特定的值（null或false）。注意，这只是接口定义的建议，具体实现可能会稍有差别。比如LinkedList的实现里offer和add就是一样的：

public boolean offer(E e) {
    // offer方法直接调用的add方法
    return add(e);
}

在java.util包下Queue的实现类只有一个PriorityQueue，Deque的实现类有LinkedList和ArrayDeque。

一、PriorityQueue

PriorityQueue是一个优先队列，对于队列的特性大家都知道，那就是先进先出（FIFO）。而PriorityQueue则为我们提供了一种自定义权重的队列。使得出队列的顺序不再按照进入队列的顺序，而是按照自定义的权重进行出队。

明白了PriorityQueue的作用后我们再来分析下它的具体实现。PriorityQueue的存储结构是一个数组，但是它的逻辑结构却是一颗完整二叉树，具有小顶堆性质。

它需要在调用构造方法的时候指定一个Comparator，或则让要插入的元素实现Comparable接口。来看下具体源码：

// 用于存储元素的数组
transient Object[] queue;
...
public boolean add(E e) {
    // 可见它的add方法和offer方法的实现也是一样的
    return offer(e);
}

public boolean offer(E e) {
    // 可以看出，PriorityQueue是不支持null作为元素的
    if (e == null)
        throw new NullPointerException();

    modCount++;
    int i = size;
    if (i >= queue.length)
        // grow方法和前面讲的ArrayList里的功能一样，就是用来扩容的
        grow(i + 1);

    size = i + 1;
    if (i == 0)
        // 如果队列为空则直接将元素插入到队列头部即可
        queue[0] = e;
    else
        // 将元素插入到队列尾部并向上调整顺序
        siftUp(i, e);
    return true;
}

private void grow(int minCapacity) {
    int oldCapacity = queue.length;
    // 如果当前容量小于64，则进行双倍扩容，否则扩容为当前的1.5倍
    int newCapacity = oldCapacity + ((oldCapacity < 64) ?
                                     (oldCapacity + 2) :
                                     (oldCapacity >> 1));

    // 边界检查
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);

    // 新建一个newCapacity大小的数组，并将当前数组（queue）里面的元素复制过去，最后将新建的数组重新赋值queue
    queue = Arrays.copyOf(queue, newCapacity);
}

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) {
        // 找到当前节点的父节点位置
        int parent = (k - 1) >>> 1;
        // 父节点的值
        Object e = queue[parent];
        // 如果当前节点的值不小于父节点的值则退出循环
        if (comparator.compare(x, (E) e) >= 0)
            break;

        // 将当前节点和父节点交换位置
        // 这里没有将父节点的只修改为x，因为没有必要，下次循环直接用的是x和父节点比较
        // 这样可以少一次赋值操作，当最后找到了要插入的位置再进行赋值即可
        queue[k] = e;

        // 继续父节点和父节点的父节点比较
        k = parent;
    }

    // 最终x的位置
    queue[k] = x;
}

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); // 将最后一个元素放到第0个位置并向下调整顺序
    return result;
}

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

private void siftDownUsingComparator(int k, E x) {
    // 从第一个元素开始往下比较
    int half = size >>> 1;
    while (k < half) {
        // 找到该元素的左右子叶子节点元素
        int child = (k << 1) + 1;
        Object c = queue[child];
        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;

        // 否则交换节点数据，然后继续往下比较
        queue[k] = c;
        k = child;
    }
       
    queue[k] = x;
}

对于二叉树这里因为篇幅原因就不多讲，如果不懂的下来请自己查阅相关资料学习下。

PriorityQueue默认使用的是小顶堆，我们也可以使用自定义的Comparator（或Comparable）来实现大顶堆。

二、LinkedList

对于LinkedList我们在前面已经讲了它的一部分特性，ArrayList是通过对数组的封装来实现的动态数组，而LinkedList则可以理解为是用双向链表来实现的动态数组。其实LinkedList除了动态数组的特性之外，它还有Deque的特性，因为它也同时实现了Deque接口：

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 set(int index, E element) {
        checkElementIndex(index);
        Node<E> x = node(index);
        E oldVal = x.item;
        x.item = element;
        return oldVal;
    }

    public E remove(int index) {
        checkElementIndex(index);
        return unlink(node(index));
    }

    ...

   // Deque相关方法
    public void addFirst(E e) {
        linkFirst(e);
    }

    public void addLast(E e) {
        linkLast(e);
    }

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

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

    public E removeFirst() {
        final Node<E> f = first;
        if (f == null)
            throw new NoSuchElementException();
        return unlinkFirst(f);
    }

    public E removeLast() {
        final Node<E> l = last;
        if (l == null)
            throw new NoSuchElementException();
        return unlinkLast(l);
    }

    ...

    // 队列相关方法
    public boolean offer(E e) {
        return add(e);
    }

    public E poll() {
        final Node<E> f = first;
        return (f == null) ? null : unlinkFirst(f);
    }

    public E peek() {
        final Node<E> f = first;
        return (f == null) ? null : f.item;
    }

    ...

    // 栈相关方法
    public void push(E e) {
        addFirst(e);
    }

    public E pop() {
        return removeFirst();
    }
    ...
}

因为LinkedList内部使用的是双向链表，所以它借助双向链表可以双向遍历的特性很容易就能实现队列和栈的功能。

可见，LinkedList的功能还是非常强大的，即可以作为一个动态数组，也可以作为一个队列，还可以作为栈。

需要注意的是，LinkedList也是一个宽接口API，所以在使用它的时候一定要明白它每个方法的作用，尽量使用和功能对应的那套方法。如用LinkedList来作为栈时，尽量使用push、pop来进行压栈和出栈，就不要使用set和remove来操作了。又如当用LinkedList作为队列的时候就尽量使用offer、poll、peek等方法。

三、ArrayDeque

我们知道，实现队列的方式可以用数组也可以用链表。当用数组来实现的时候，可能会造成假溢出现象，导致数组的使用率降低，除非每次出队列的时候都将数组上的元素前移一位（但是这样性能是非常差的）。

假溢出：入队是插入到数组后面，出队是从数组前面出队。当数组后面的位置用完了的时候，如果数组前面有出队的元素，则前面出队后空出来的位置无法使用。这种就叫做假溢出。

ArrayDeque是一个循环队列（可以假想为数组是一个首尾相连的环状），它可以完美的将前面空闲的位置重新利用起来。

ArrayDeque有两个索引来指示队列开始位置和结束位置：

public class ArrayDeque<E> extends AbstractCollection<E>
                           implements Deque<E>, Cloneable, Serializable
{
    // 用于存放元素的数组
    transient Object[] elements;

    // 队列开始位置的索引，当队列为空时，head = tail = 0，即此时都指向数组第0个元素，
    // 否则永远指向队列的第一个元素（注意是队列的第一个元素，而不是数组的第一个元素）
    transient int head;

    // 队列结束位置的索引（最后一个元素的下一个位置）
    transient int tail;

    // 队列的最小容量
    private static final int MIN_INITIAL_CAPACITY = 8;

    public ArrayDeque() {
        // 注意：初始容量如果没有指定的话，并不是最小的8，而是16
        elements = new Object[16];
    }

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

    private void allocateElements(int numElements) {
        int initialCapacity = MIN_INITIAL_CAPACITY;
        // ArrayDeque和HashMap一样，要求内部数组的长度必须是2的冥（2的n次方）
        // 因为会涉及到对head和tail进行取模运算，如果数组长度是2的冥，则可以使用位运算来代替%运算，提高性能
        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];
    }
    ...
}

再来看下入队的源码：

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

public void addLast(E e) {
    // 可见，ArrayDeque是不允许null作为队列元素的
    if (e == null)
        throw new NullPointerException();

    // 因为tail指向的是最后一个元素的下一个位置，所以这里可以直接存储
    elements[tail] = e;

    // 将tail移动到下一个位置 -- 解释1
    // 
    // tail==head有两个含义，一个为队列为空，一个是队列满了。
    // 由于上面刚入队了一个元素，队列不可能为空，所以这里如果相等只能是队列满了
    if ( (tail = (tail + 1) & (elements.length - 1)) == head)
        // 进行双倍扩容（新数组长度为当前数组长度的两倍）
        doubleCapacity();
}

public void addFirst(E e) {
    if (e == null)
        throw new NullPointerException();
    elements[head = (head - 1) & (elements.length - 1)] = e;
    if (head == tail)
        // 这里和上面的情况一样，如果此时head和tail相等则必然是队列满了（不会是为空的情况）
        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);
    System.arraycopy(elements, 0, a, r, p);
    elements = a;

    // 扩容成功后重新设定head和tail指向的位置
    head = 0;
    tail = n;
 }

解释1：

1. 问题1：(tail + 1) & (elements.length - 1)是什么意思？

   其实就是取模的意思，和(tail + 1) % elements.length等价，但是效率比%运算符要高（详细介绍见HashMap篇）；

2. 这里应该是要将tail指向当前tail的下一个位置，为什么不直接用tail = tail + 1呐？

   取模运算是为了防止越界问题。比如数组长度为16，当前tail值为15，已经是数组最后一个元素了。如果直接用tail + 1，那么结果就是16，显然会下标越界，而且根据我们循环队列的思想这个时候tail应该指向队列第一个位置，也就是tail应该为0。而用取模运算就正好达到了这个需要：(15 + 1) % 16 = 0 。

在数组扩容成功后会重新排列元素，所以head和tail的位置都会变化且不再相等，这样也就可以在入队操作之外用head == tail来判断队列是否为空了。扩容过程如下：

总结

当使用栈的时候ArrayDeque比Stack快（在单线程中）；当使用队列的时候比LinkedList快。同样，ArrayDeque不是线程安全的。PriorityQueue则是一个可以自定义出队顺序的优先队列。