10_standard_library_05_queue

第九十三章 Java标准库-队列(Queue)

1 概述

队列是一种先进先出(First In First Out)的数据结构。队列常常用于实现排队、调度等功能或者流程。Java标准库提供了java.util.Queue类和java.util.Deque类,帮助开发人员实现队列的功能。Queue类与Deque类的区别是,Deque是一个双向队列,可以向队列的两端添加或者提取元素。Deque的全称为Double Ended Queue。

Java标准库中包含的、与Queue接口相关的类的结构如下图所示。

图一 Queue接口的结构图

图一 Queue接口的结构图

2 java.util.Queue接口

Queue接口提供了三类操作:向队尾添加元素、队首删除元素和查看队首的元素。为了方便开发人员使用这些方法,Queue接口以两种形式提供了上述三种功能。这两种形式的区别是当操作失败时,一种形式通过方法的返回值表达操作失败;而另一种形式则会抛出异常。

从下面的表中可以看出,

  1. add()和offer()都能向队尾添加新元素。但是当失败时,add()方法会抛出异常,offer()则返回false,表示失败。
  2. 类似的,remove()和poll()方法从队列头部提取一个元素。当失败时,remove()抛出异常,而poll()则返回null。
  3. element()和peek()查看队列头部的元素。当失败时,element()抛出异常;peek()则返回null。
方法功能抛出异常返回失败值
添加元素add()offer()
删除元素remove()poll()
查看元素element()peek()

如下是一段使用Queue接口的代码示例。我们将LinkedList对象当作Queue对象来用,将所有的元素存放在LinkedList对象中。

Queue<Integer> queue = new LinkedList<Integer>();
queue.add(1);
queue.add(2);

System.out.println(queue.remove()); // 打印元素1

3 java.util.Deque接口

Deque接口是一个双向队列接口。Deque支持在队列头部和尾部添加或者删除元素。如果使用得当,Deque能实现队列的功能和堆栈的功能。

与Queue类似的是,Deque也提供了两种形式的接口来表达失败:抛出异常和返回错误值。我们将接口总结如下。

方法功能抛出异常返回失败值
队首添加元素addFirst()offerFirst()
队首删除元素removeFirst()pollFirst()
队首查看元素getFirst()peekFirst()
队尾添加元素addLast()offerLast()
队尾删除元素removeLast()pollLast()
队尾查看元素getLast()peekLast()

如果对照着下表选择和使用上述方法,Deque也能完成队列的功能。

Queue接口名称对应的Deque接口名称
add()addLast()
offer()offerLast()
remove()removeFirst()
poll()pollFirst()
element()getFirst()
peek()peekFirst()

如果对照着下表选择和使用Deque的方法,还能完成堆栈的功能。

Stack接口名称对应的Deque接口名称
push()addFirst()
pop()removeFirst()
peek()getFirst()

如下是一段使用Deque接口的代码示例。我们将LinkedList对象当作Deque对象来用,将所有的元素存放在LinkedList对象中。

Deque<Integer> queue = new LinkedList<Integer>();
queue.addFirst(1);
queue.addFirst(2);

System.out.println(queue.removeFirst()); // 打印元素1

4 队列的实现

Java标准库提供了几种队列的实现。其中最常见的是LinkedList。LinkedList是一个双向链表,它不仅实现了List接口,还实现了Queue接口和Deque接口。我们在介绍List时讲解过LinkedList的实现原理,因此,本章不再累述。我们将讨论一下java.util.PriorityQueue的实现原理。

优先级队列(Priority Queue)是一种常见的队列类型,常用于调度算法的实现。在优先级队列中,元素并不严格按照先进先出的顺序处理,而是按照元素之间的优先级顺序排队。优先级是元素的一种特质,它可能是元素的一个属性值,也可能是元素的一种状态。Java标准库在PriorityQueue中提供了一个Comparator。开发人员无需声明什么是优先级,而只需要提供一个Comparator,比较元素的优先级即可。这也是一种策略模式的应用。

假如,我们有一个包含字符串元素的队列,每次走出队列的是队列中长度最小的元素的话,可以按照如下代码实现。

Comparator shortestFirst = Comparator.comparingInt​(String::length);
Queue<String> queue = new PriorityQueue<String>(;
queue.add("abc");
queue.add("ab");
queue.add("abcd");

System.out.println("The shortest string is " + queue.remove());

PriorityQueue的实现也很简洁。PriorityQueue中有一个数组类型的成员变量queue,保存着所有的元素。另一个成员变量comparator表示的是如何比较两个元素的优先级。当有新元素添加到队中时,offer()方法会调用siftUp()方法,确保在数组中的第一个元素是优先级最高的元素。因此,当调用peek()方法是,队首的元素放置在第0位。当调用poll()移除一个元素时,需要调用siftDown()方法再次进行调整。

// OpenJDK 15
package java.util;

public class PriorityQueue<E> extends AbstractQueue<E>
    implements java.io.Serializable {
    transient Object[] queue;

    final Comparator<? super E> comparator;

    public boolean add(E e) {
        return offer(e);
    }

    public boolean offer(E e) {
        if (e == null)
            throw new NullPointerException();
        modCount++;
        int i = size;
        if (i >= queue.length)
            grow(i + 1);
        siftUp(i, e);
        size = i + 1;
        return true;
    }

    public E poll() {
        final Object[] es;
        final E result;

        if ((result = (E) ((es = queue)[0])) != null) {
            modCount++;
            final int n;
            final E x = (E) es[(n = --size)];
            es[n] = null;
            if (n > 0) {
                final Comparator<? super E> cmp;
                if ((cmp = comparator) == null) // 将comparator赋值给cmp,并判断cmp是否为null
                    siftDownComparable(0, x, es, n);
                else
                    siftDownUsingComparator(0, x, es, n, cmp);
            }
        }
        return result;
    }

    public E peek() {
        return (E) queue[0];
    }
    ...
}

在比较元素优先级时,如果开发人员给定了Comparator对象,那么,PriorityQueue会使用这个Comparator对象比较两个对象的优先级大小。如果没有给定Comparator对象的话,PriorityQueue会按照优先级类型的自燃序排队。下面的代码仅展示了使用Comparator对象的情况。

实际上,成员变量queue构建了一个堆(heap)。当插入新元素时,(k-1) >>> 1实际上计算的是当前元素的父节点的位置。当当前元素的优先级大于父节点的优先级时就可以停止循环了。否则需要一直比较到根结点。当删除一个元素时,需要重新寻找一个次优元素。有关堆的工作原理可参考这里

// OpenJDK 15
package java.util;

public class PriorityQueue<E> extends AbstractQueue<E>
    implements java.io.Serializable {
    ...
    private static <T> void siftUpUsingComparator(int k, T x, Object[] es, Comparator<? super T> cmp) {
        while (k > 0) {
            int parent = (k - 1) >>> 1;
            Object e = es[parent];
            if (cmp.compare(x, (T) e) >= 0)
                break;
            es[k] = e;
            k = parent;
        }
        es[k] = x;
    }
    ...
    private static <T> void siftDownUsingComparator(int k, T x, Object[] es, int n, Comparator<? super T> cmp) {
        // assert n > 0;
        int half = n >>> 1;
        while (k < half) {
            int child = (k << 1) + 1;
            Object c = es[child];
            int right = child + 1;
            if (right < n && cmp.compare((T) c, (T) es[right]) > 0)
                c = es[child = right];
            if (cmp.compare(x, (T) c) <= 0)
                break;
            es[k] = c;
            k = child;
        }
        es[k] = x;
    }
    ...
}

5 小结

本章介绍了Java标准库中java.util.Queue接口和java.util.Deque接口的使用方法。它们提供了队列的接口;Queue是一种传统的队列,支持先进先出;Deque是一种双向队列,支持从队列头部和尾部插入和删除元素。本章还介绍了优先级队列java.util.Priority。它将所有的元素保存在堆中,允许开发人员指定如何比较元素之间的优先级。

 

上一章
下一章

注册用户登陆后可留言

Copyright  2019 Little Waterdrop, LLC. All Rights Reserved.