队列是一种先进先出(First In First Out)的数据结构。队列常常用于实现排队、调度等功能或者流程。Java标准库提供了java.util.Queue类和java.util.Deque类,帮助开发人员实现队列的功能。Queue类与Deque类的区别是,Deque是一个双向队列,可以向队列的两端添加或者提取元素。Deque的全称为Double Ended Queue。
Java标准库中包含的、与Queue接口相关的类的结构如下图所示。
图一 Queue接口的结构图
Queue接口提供了三类操作:向队尾添加元素、队首删除元素和查看队首的元素。为了方便开发人员使用这些方法,Queue接口以两种形式提供了上述三种功能。这两种形式的区别是当操作失败时,一种形式通过方法的返回值表达操作失败;而另一种形式则会抛出异常。
从下面的表中可以看出,
方法功能 | 抛出异常 | 返回失败值 |
---|---|---|
添加元素 | 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
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
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;
}
...
}
本章介绍了Java标准库中java.util.Queue接口和java.util.Deque接口的使用方法。它们提供了队列的接口;Queue是一种传统的队列,支持先进先出;Deque是一种双向队列,支持从队列头部和尾部插入和删除元素。本章还介绍了优先级队列java.util.Priority。它将所有的元素保存在堆中,允许开发人员指定如何比较元素之间的优先级。
注册用户登陆后可留言