Java集合(三)：Queue队列

阳光穿透心脏的1/2处 2022-07-28 09:21 184阅读 0赞

前面介绍了列表，其中包括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的元素代表数组的第一个元素，下标最大的元素代表数组的最后一个元素，这是固定的，对于在尾部添加和删除元素的队列操作来说还可以，但是对于同时也要在头部添加和删除元素就不适合了，因为这时必须移动头部元素后面的所有元素。而循环数组就解决了这个问题。

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

![20160413142917315][]

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

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

![20160413143417742][]

数组的总长度固定，保证能够容纳所有元素的情况下，两个下标（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，就像这样：

![20160413145049220][]

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

![20160413145235861][]

这两种情况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));
            }
        }
    }

结果如下：

![20160413170220896][]

[20160413142917315]: /images/20220724/b49c53696f454a8e945e9f70747841e5.png
[20160413143417742]: /images/20220724/bb30870b0d9b43bfa1c6329a9ffeac91.png
[20160413145049220]: /images/20220724/4e8e815738cc4747a82fb110f51d7344.png
[20160413145235861]: /images/20220724/6478e9c9a06641efb557dafd4f2e499e.png
[20160413170220896]: /images/20220724/e2db8ed34098415b81e262458db91717.png