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
,具体取决于操作),接口的常规结构如下表所示。
操作类型 | 抛出异常 | 返回特殊值 |
---|---|---|
插入 |
add(e)
|
offer(e)
|
移除 |
remove()
|
poll()
|
检查 |
element()
|
peek()
|
队列通常(但不一定)以FIFO(先进先出)方式对元素进行排序,优先级队列除外,它们根据元素的值对元素进行排序 — 有关详细信息,请参阅“对象排序”部分。无论使用什么排序,队列的头部都是通过调用 remove
或 poll
移除的元素。在FIFO队列中,所有新元素都插入队列的尾部,其他类型的队列可能使用不同的放置规则,每个 Queue
实现都必须指定其排序属性。
Queue
实现可以限制它所拥有的元素数量,这样的队列被称为有界, java.util.concurrent
中的某些 Queue
实现是有界的,但 java.util
中的实现不是。
Queue
从 Collection
继承的 add
方法插入一个元素,除非它违反了队列的容量限制,在这种情况下它会抛出 IllegalStateException
。 offer
方法,仅用于有界队列,与 add
不同之处仅在于它通过返回 false
来表示插入元素失败。
remove
和 poll
方法都移除并返回队列的头部,确切地移除哪个元素是队列的排序策略的函数,仅当队列为空时, remove
和 poll
方法的行为才有所不同,在这些情况下, remove
抛出 NoSuchElementException
,而 poll
返回 null
。
element
和 peek
方法返回但不移除队列的头部,它们之间的差异与 remove
和 poll
的方式完全相同:如果队列为空,则 element
抛出 NoSuchElementException
,而 peek
返回 null
。
队列实现通常不允许插入 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); } } }
在以下示例中,优先级队列用于对元素集合进行排序,同样,这个程序是人为的,因为没有理由使用它来支持集合中提供的排序方法,但它说明了优先级队列的行为。
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; }