在堆栈和队列中存储元素
在队列层次结构中找到你的方向
Java SE 5 在集合框架中添加了一个新的接口: Queue 接口，在 Java SE 6 中由 Deque 接口进一步扩展。 Queue 接口是 Collection 接口的扩展。
推送、弹出和窥视
堆栈和队列结构是计算中的经典数据结构。堆栈也称为 LIFO 堆栈，其中 LIFO 代表后进先出。队列被称为 FIFO：先进先出。
这些结构非常简单，并为您提供了三个主要操作。
- push(element): 将元素添加到队列或堆栈中
- pop(): 从堆栈中删除元素，即添加的最新元素
- poll(): 从队列中删除元素，即添加的最旧元素
- peek(): 允许您查看您将使用 pop() 或 poll() 获取的元素，但不会将其从队列或堆栈中删除。
有两个原因可以解释这些结构在计算中的成功。第一个是它们的简单性。即使在计算的早期，实现这些也很简单。第二个是它们的实用性。许多算法使用堆栈来实现。
对队列和堆栈进行建模
集合框架为您提供了两个接口来对队列和堆栈进行建模
堆栈和队列在并发编程中也得到了广泛的应用。这些接口由更多接口进一步扩展，添加了此领域中很有用的方法。这些接口， BlockingQueue、 BlockingDeque 和 TransferQueue，位于集合框架和 Java 并发编程的交汇处，超出了本教程的范围。
Queue 和 Deque 接口在这三个基本操作中添加了行为，以处理两个极端情况。
- 队列可能已满，无法接受更多元素
- 队列可能为空，无法使用 pop、poll 或 peek 操作返回元素。
事实上，这个问题需要得到解答：实现应该如何在这两种情况下表现？
使用 Queue 对 FIFO 队列进行建模
Queue 接口为您提供了两种处理这些极端情况的方法。可以抛出异常，也可以返回特殊值。
以下是 Queue 提供给您的方法表。
| 操作 | 方法 | 队列已满或为空时的行为 |
|---|---|---|
| push | add(element) |
抛出 IllegalStateException |
offer(element) |
返回 false |
|
| poll | remove() |
抛出 NoSuchElementException |
poll() |
返回 false |
|
| peek | element() |
抛出 NoSuchElementException |
peek() |
返回 null |
使用 Deque 对 LIFO 堆栈和 FIFO 队列进行建模
Java SE 6 添加了 Deque 接口作为 Queue 接口的扩展。当然，在 Queue 中定义的方法仍然可以在 Deque 中使用，但 Deque 引入了一种新的命名约定。因此，这些方法已在 Deque 中复制，遵循此新的命名约定。
以下是 Deque 中为 FIFO 操作定义的方法表。
| FIFO 操作 | 方法 | 队列已满或为空时的行为 |
|---|---|---|
| push | addLast(element) |
抛出 IllegalStateException |
offerLast(element) |
返回 false |
|
| poll | removeFirst() |
抛出 NoSuchElementException |
pollFirst() |
返回 null |
|
| peek | getFirst() |
抛出 NoSuchElementException |
peekFirst() |
返回 null |
以下是 Deque 中为 LIFO 操作定义的方法表。
| LIFO 操作 | 方法 | 队列已满或为空时的行为 |
|---|---|---|
| push | addFirst(element) |
抛出 IllegalStateException |
offerFirst(element) |
返回 false |
|
| pop | removeFirst() |
抛出 NoSuchElementException |
pollFirst() |
返回 null |
|
| peek | getFirst() |
抛出 NoSuchElementException |
peekFirst() |
返回 null |
Deque 命名约定很简单，与 Queue 接口中遵循的命名约定相同。不过，有一个区别：窥视操作在 Deque 中分别命名为 getFirst() 和 getLast()，而在 Queue 中命名为 element()。
此外， Deque 还定义了您在任何队列或堆栈类中都期望的方法
push(element): 将给定的element添加到双端队列的头部pop(): 删除并返回双端队列头部处的元素poll(): 在双端队列的尾部执行相同的操作peek(): 向您显示双端队列尾部处的元素。
如果要 pop、poll 或 peek 的元素不存在，则这些方法将返回 null 值。
实现 Queue 和 Deque
集合框架为您提供了 Queue 和 Deque 的三种实现，它们位于并发编程空间之外
ArrayDeque: 它同时实现了这两个接口。此实现由数组支持。此类的容量会随着元素的添加而自动增长。因此，此实现始终接受新元素。LinkedList: 它也同时实现了这两个接口。此实现由链表支持，使访问其第一个和最后一个元素非常高效。LinkedList始终接受新元素。PriorityQueue: 它只实现了Queue。此队列由数组支持，该数组按其自然顺序或由Comparator指定的顺序对其元素进行排序。此队列的头部始终是队列中相对于指定排序的最小元素。此类的容量会随着元素的添加而自动增长。
远离 Stack 类
使用 JDK 提供的 Stack 类可能看起来很诱人。此类易于使用和理解。它具有三个预期方法 push(element)、 pop() 和 peek()，在您的代码中看到此类引用使其完全可读。
事实证明，此类是 Vector 类的扩展。在引入集合框架之前， Vector 是您使用列表的最佳选择。虽然 Vector 尚未弃用，但建议不要使用它。因此，建议不要使用 Stack 类。
Vector 类是线程安全的，Stack 类也是线程安全的。如果您不需要线程安全性，则可以安全地用 Deque 和 ArrayDeque 替换它们。如果您需要线程安全的堆栈，则应探索 BlockingQueue 接口的实现。
上次更新： 2021 年 9 月 14 日