Java集合(三)：Queue队列

前面介绍了列表，其中包括List接口和LinkedList链表和ArrayList数组列表。这节介绍一个也很常见的数据结构：队列。

我们知道，队列是一个可以从尾部添加新元素、从头部删除元素的数据结构。对于有两个头的队列，即双端队列，可以让人们有效的在头部和尾部同时添加或删除元素。不过，队列不支持在中间添加元素。这节将介绍两个队列接口：Queue接口和双端队列接口Deque，还有实现类：ArrayDeque和优先级队列PriorityQueue。

1 队列：Queue接口

Queue接口设计了一些可以在队列头部删除元素、在尾部添加元素的方法。这个接口比较简单，一共只有6个方法，分别如下：

（1）添加元素

boolean add(E e);
boolean offer(E e);

这两个方法都在尾部添加一个值为e的元素。如果队列没有满，将给定的元素添加到这个队列的尾部并返回true。不同的是如果队列满了，add方法会抛出一个IllegalStateException异常，而offer方法返回false。

（2）删除并返回元素

E remove();
E poll();

这两个方法删除队列头部的元素。如果队列非空，这两个方法删除头部元素后并返回这个元素。不同的是如果队列是空的，remove方法抛出一个NoSuchElementException异常，而poll方法返回false。

（3） 获得头部元素

E element();
E peek();

这两个方法都会返回头部的元素，而都不删除头部元素。不同的是如果队列是空的，element方法抛出一个NoSuchElementException异常，而peek方法返回null。

2 双端队列：Deque接口及ArrayDeque类

一般的队列只能在头部删除元素、在尾部添加元素，即只有一个端。而双端队列有两个端，支持在两端同时添加或删除元素。Deque接口是Java SE 6引入的，并由ArrayDeque类和LinkedList类实现，这两个类都提供了双端队列，并在必要的时候可以增加队列的长度。其实，还有一种队列，叫做有限队列，当然也包括有限双端队列，这两个队列不在本文的讨论之内。

2.1 Deque接口

Deque接口在Queue接口的基础之上增加了一些针对双端添加和删除元素的方法，这些方法根据出错时的行为也可以分为几组。这些方法就是在Queue接口中的方法名后面加上“First”和“Last”表明在哪端操作。这些方法整理如下：

（1）添加元素

void addFirst(E e);
void addLast(E e);
boolean offerFirst(E e);
boolean offerLast(E e);

这四个方法在头部或尾部添加给定的元素。如果队列满了，前两个方法将抛出一个IllegalStateException异常，后两个方法返回false。

（2）删除并返回元素

E removeFirst();
E removeLast();
E pollFirst();
E pollLast();

这四个方法删除头部或尾部的元素并返回。如果队列为空，前两个方法将抛出一个NoSuchElementException异常，后两个方法返回null。

（3）返回但不删除元素

E getFirst();
E getLast();
E peekFirst();
E peekLast();

这四个方法返回头部或尾部的元素，但不删除。如果队列为空，前两个方法将抛出一个NoSuchElementException异常，后两个方法返回null。

2.2 ArrayDeque类

ArrayDeque类实现了Deque接口，是一个双端队列。不像LinkedList是一个双向链表，ArrayDeque是一个双向数组。这么说有点不准确，应该是，ArrayDeque的底层实现是一个循环数组：

transient Object[] elements;
transient int head;
transient int tail;

什么是循环数组？对于普通的数组，下标为0的元素代表数组的第一个元素，下标最大的元素代表数组的最后一个元素，这是固定的，对于在尾部添加和删除元素的队列操作来说还可以，但是对于同时也要在头部添加和删除元素就不适合了，因为这时必须移动头部元素后面的所有元素。而循环数组就解决了这个问题。

循环数组的基本思路是头下标和尾下标不是固定的。即这样：

其中中间的部分是队列中的元素。从这里我们可以看出，队列中的元素还是在数组中的连续部分存储的。两边空的地方可以扩展队列。如果要在头部添加或删除一个元素，只需要使头下标head左移或右移一位即可，对于尾部的操作也是如此。这样就避免了真个数组的移动，提高了性能。

可以如果头部一直添加，或尾部一直添加，导致左面或右面不够了怎么办？这时就体现出循环数组的循环特点来了。具体的做法是，如果添加头部时左面没空间了，那么就在右面添加，就像这样：

数组的总长度固定，保证能够容纳所有元素的情况下，两个下标（head和tail）就像这样来回循环着。

那么在这两种情况下，队列中的元素个数怎么计算呢？

对于上面那种情况很容易，元素个数就是tail-head+1。下面这种情况就不是那么清晰了。可以先算中间空余的部分，然后用总长度减去空余的。中间空余的部分的长度是head-tail-1，那么元素个数就是length-(head-tail-1)。

事实上，ArrayDeque类的实现者有个更好的方法，使用位运算：

public int size() {
    return (tail - head) & (elements.length - 1);
}

这样就计算了元素的个数，很神奇。

可是，head和tail总有相等的时候。一种情况是队列中没有元素，这时head==tail，就像这样：

另一种情况是，head循环后一直增加，一直增加到tail：

这两种情况tail都等于head，看ArrayDeque类的isEmpty方法：

public boolean isEmpty() {
    return head == tail;
}

这又是怎么判断到底是空呢还是满呢？

事实上，ArrayDeque类的实现者不会让第二种情况发生。因为ArrayDeque是一个可变长度队列，即如果空间不够，程序会自动扩大数组的容量为原来的2倍，然后将原来的元素复制到新的数组中。

还有一点，初始化时这个数组的长度是8，如果满了就扩大为原来的2倍，因此数组的长度一直是2的幂。

这个双端队列的基本操作方法都很简单，这里就不过多叙述。

虽然双端队列只可以在两端做添加和删除操作，但ArrayDeque类还增加了两个方法可以在中间删除给定的元素：

public boolean removeFirstOccurrence(Object o)
public boolean removeLastOccurrence(Object o)

第一个方法删除第一次出现给定对象的元素（第一次出现即从head开始到tail结束）；第二个方法删除最后一次出现给定对象的元素。

由于双端队列的特殊性（head可能比tail大），如果要从head到tail遍历队列，需要这样：

int mask=elements.length-1;
int i=head;
while(i!=tail)
{
    dosomething with elements[i];
    i=(i+1)&mask;
}

不过这样的话tail的那个元素没有遍历到。

ArrayDeque类中还定义了两个迭代器，一个是正向的Iterator迭代器，通过方法iterator返回；另一个是反向迭代器DescendingIterator，通过方法descendingIterator返回。关于迭代器的部分在上一节LinkedList部分讲到了，这里不过多重复。ArrayDeque类内部实现Iterator接口的内部类分别是：

private class DeqIterator implements Iterator<E>
private class DescendingIterator implements Iterator<E>

这两个类实现了next和hasNext方法。

3 优先级队列：PriorityQueue

优先级队列中的元素可以按照任意的顺序插入，却总是按照排序的顺序进行检索。也就是说，无论何时调用remove方法，总会获得当前优先级队列中最小的元素。然而，优先级队列并没有对所有的元素进行排序。如果用迭代的方式处理这些元素，并不需要对它们进行排序。优先级队列使用了一个优雅且高效的数据结构，称为堆（heap）。堆是一个可以自我调节的二叉树，对树执行添加（add）和删除（remove）操作，可以让最小的元素移动到根，而不必花时间对元素进行排序。

PriorityQueue类的底层是使用数组保存数据的：

transient Object[] queue;
private int size = 0;

其中size保存元素的个数。使用数组保存一个二叉树，对于一个节点下标为n，则左儿子的下标为2*n+1，右儿子下标为2*(n+1)。而队列中的最小元素保存在queue[0]中。

PriorityQueue即可以保存实现了Comparable接口的类对象，也可以保存在构造器中提供比较器的对象。比如，下面的代码使用自定义比较器构造一个优先级队列：

PriorityQueue<Student> pq=new PriorityQueueM<>(new Comparator<Student>(){
      public int compare(Student s1,Student s2){
        return s1.getScore()-s2.getScore();
        }
}
);

这个比较器比较两个学生的成绩。这是一个匿名内部类。

在最小堆中，最重要的操作就是添加元素或删除元素后如何调整这个堆。基本上，如果添加一个元素，可以先将这个元素放在最下面，然后将这个元素向上移动，知道大于等于它的父节点或称为根节点；还可以将这个元素放在根节点位置，然后将这个元素向下移动，直到小于等于子节点或称为一个叶节点。

下面是PriorityQueue类中实现的上移和下移代码，对我们的编程很有帮助：

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

@SuppressWarnings("unchecked")
private void siftUpComparable(int k, E x) {
    Comparable<? super E> key = (Comparable<? super E>) x;
    while (k > 0) {
        int parent = (k - 1) >>> 1;
        Object e = queue[parent];
        if (key.compareTo((E) e) >= 0)
            break;
        queue[k] = e;
        k = parent;
    }
    queue[k] = key;
}

@SuppressWarnings("unchecked")
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;
        queue[k] = e;
        k = parent;
    }
    queue[k] = x;
}

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

@SuppressWarnings("unchecked")
private void siftDownComparable(int k, E x) {
    Comparable<? super E> key = (Comparable<? super E>)x;
    int half = size >>> 1;        // loop while a non-leaf
    while (k < half) {
        int child = (k << 1) + 1; // assume left child is least
        Object c = queue[child];
        int right = child + 1;
        if (right < size &&
            ((Comparable<? super E>) c).compareTo((E) queue[right]) > 0)
            c = queue[child = right];
        if (key.compareTo((E) c) <= 0)
            break;
        queue[k] = c;
        k = child;
    }
    queue[k] = key;
}

@SuppressWarnings("unchecked")
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;
}

使用优先级队列的典型示例是任务调度。每一个任务都有一个优先级，任务以随机顺序添加到队列中。每当启动一个新的任务时，都将优先级最高的任务从队列中删除（习惯上将1设为最高优先级）。

下面的代码展示了PriorityQueue类的使用：

import java.util.*;
public class PriorityQueueTest {
    public static void main(String[] args) {
        PriorityQueue<GregorianCalendar> pq=new PriorityQueue<>();
        pq.add(new GregorianCalendar(1906,Calendar.DECEMBER,9));
        pq.add(new GregorianCalendar(1815,Calendar.DECEMBER,10));
        pq.add(new GregorianCalendar(1903,Calendar.DECEMBER,3));
        pq.add(new GregorianCalendar(1910,Calendar.JUNE,22));

        System.out.println("Iterating over elements...");
        for(GregorianCalendar date:pq){
            System.out.println(date.get(Calendar.YEAR));
        }
        System.out.println("Removing elements...");
        while(!pq.isEmpty()){
            System.out.println(pq.remove().get(Calendar.YEAR));
        }
    }
}

结果如下：