队列接口
原文: https://docs.oracle.com/javase/tutorial/collections/interfaces/queue.html
Queue
是用于在处理之前保持元素的集合。除了基本的Collection
操作外,队列还提供额外的插入,移除和检查操作。接下来是Queue
接口。
public interface Queue<E> extends Collection<E> {
E element();
boolean offer(E e);
E peek();
E poll();
E remove();
}
每个Queue
方法以两种形式存在:(1)如果操作失败则抛出异常,(2)如果操作失败,则另一个返回特殊值(null
或false
,具体取决于操作)。接口的常规结构在下表中说明。
Queue Interface Structure
| 操作类型 | 引发异常 | 返回特殊值 |
| —- | —- | —- |
| 插入 | add(e)
| offer(e)
|
| 去掉 | remove()
| poll()
|
| 检查 | element()
| peek()
|
队列通常(但不一定)以 FIFO(先进先出)方式对元素进行排序。优先级队列除外,它们根据值对元素进行排序 - 有关详细信息,请参阅对象排序部分)。无论使用什么顺序,队列的头部都是通过调用remove
或poll
来删除的元素。在 FIFO 队列中,所有新元素都插入队列的尾部。其他类型的队列可能使用不同的放置规则。每个Queue
实现都必须指定其排序属性。
Queue
实现可以限制它所拥有的元素数量;这种队列被称为有界。 java.util.concurrent
中的一些Queue
实现是有界的,但java.util
中的实现不是。
Queue
方法Queue
继承自Collection
,除非它违反队列的容量限制,否则会插入一个元素,在这种情况下它会抛出IllegalStateException
。 offer
方法仅用于有界队列,与add
的不同之处仅在于它表示无法通过返回false
来插入元素。
remove
和poll
方法都删除并返回队列的头部。确切地删除哪个元素是队列的排序策略的函数。 remove
和poll
方法仅在队列为空时才会有所不同。在这种情况下,remove
抛出NoSuchElementException
,而poll
返回null
。
element
和peek
方法返回但不删除队列的头部。它们以与remove
和poll
完全相同的方式彼此不同:如果队列为空,element
抛出NoSuchElementException
,而peek
返回null
。
Queue
实现通常不允许插入null
元素。为实现Queue
而进行改造的LinkedList
实现是一个例外。由于历史原因,它允许null
元素,但您应该避免利用它,因为null
被poll
和peek
方法用作特殊返回值。
队列实现通常不定义equals
和hashCode
方法的基于元素的版本,而是从Object
继承基于身份的版本。
Queue
接口没有定义阻塞队列方法,这在并发编程中很常见。这些等待元素出现或空间可用的方法在接口 java.util.concurrent.BlockingQueue
中定义,它扩展了Queue
。
在以下示例程序中,队列用于实现倒数计时器。队列预先加载了从命令行上指定的数字到 0 的所有整数值,按降序排列。然后,从队列中删除值并以一秒的间隔打印。该程序是人为的,因为在不使用队列的情况下执行相同的操作会更自然,但它说明了在后续处理之前使用队列来存储元素。
import java.util.*;
public class Countdown {
public static void main(String[] args) throws InterruptedException {
int time = Integer.parseInt(args[0]);
Queue<Integer> queue = new LinkedList<Integer>();
for (int i = time; i >= 0; i--)
queue.add(i);
while (!queue.isEmpty()) {
System.out.println(queue.remove());
Thread.sleep(1000);
}
}
}
在以下示例中,优先级队列用于对元素集合进行排序。同样,这个程序是人为的,因为没有理由使用它来支持Collections
中提供的sort
方法,但它说明了优先级队列的行为。
static <E> List<E> heapSort(Collection<E> c) {
Queue<E> queue = new PriorityQueue<E>(c);
List<E> result = new ArrayList<E>();
while (!queue.isEmpty())
result.add(queue.remove());
return result;
}