AlexChen's Blog栈和队列概述
- 栈：先入后出（LIFO）
- 队列：先入先出（FIFO）
栈和队列是以底层容器完成其所有的工作，对外提供统一的接口，底层容器是可插拔的（也就是说我们可以控制使用哪种容器来实现栈和队列的功能）。
Java 里有一个叫做 Stack 的类，却没有叫做 Queue 的类 (它是个接口名字)。当需要使用栈时，Java 已不推荐使用 Stack，而是推荐使用更高效的 ArrayDeque；既然 Queue 只是一个接口，当需要使用队列时也就首选 ArrayDeque 了 (次选是 LinkedList)。
常用的栈和队列的实现
- ArrayDeque
- LinkedList
它们都实现了 Deque 接口，其中 ArrayDeque 底层用数组实现，LinkedList 底层采用链表实现。
Queue 接口
Queue 接口继承自 Collection 接口，除了最基本的 Collection 的方法之外，它还支持额外的 insertion, extraction 和 inspection 操作。这里有两组格式，共 6 个方法，一组是抛出异常的实现；另外一组是返回值的实现 (没有则返回 null)。
| Throws exception | Returns special value | |
|---|---|---|
| Insert | add(e) | offer(e) |
| Remove | remove() | poll() |
| Examine | element() | peek() |
Deque 接口
Deque是"double ended queue", 表示双向的队列，英文读作"deck". Deque 继承自 Queue 接口，除了支持 Queue 的方法之外，还支持insert, remove和examine操作，由于 Deque 是双向的，所以可以对队列的头和尾都进行操作，它同时也支持两组格式，一组是抛出异常的实现；另外一组是返回值的实现 (没有则返回 null)。共 12 个方法如下：
| First Element - Head | Last Element - Tail | |||
|---|---|---|---|---|
| Throws exception | Special value | Throws exception | Special value | |
| Insert | addFirst(e) | offerFirst(e) | addLast(e) | offerLast(e) |
| Remove | removeFirst() | pollFirst() | removeLast() | pollLast() |
| Examine | getFirst() | peekFirst() | getLast() | peekLast() |
Deque 与 Stack 和 Queue 对应方法
Deque的含义是“double ended queue”，即双端队列，它既可以当作栈使用，也可以当作队列使用。下表列出了Deque与Queue相对应的接口：
| Queue Method | Equivalent Deque Method | 说明 |
|---|---|---|
add(e) | addLast(e) | 向队尾插入元素，失败则抛出异常 |
offer(e) | offerLast(e) | 向队尾插入元素，失败则返回false |
remove() | removeFirst() | 获取并删除队首元素，失败则抛出异常 |
poll() | pollFirst() | 获取并删除队首元素，失败则返回null |
element() | getFirst() | 获取但不删除队首元素，失败则抛出异常 |
peek() | peekFirst() | 获取但不删除队首元素，失败则返回null |
下表列出了Deque与Stack对应的接口：
| Stack Method | Equivalent Deque Method | 说明 |
|---|---|---|
push(e) | addFirst(e) | 向栈顶插入元素，失败则抛出异常 |
| 无 | offerFirst(e) | 向栈顶插入元素，失败则返回false |
pop() | removeFirst() | 获取并删除栈顶元素，失败则抛出异常 |
| 无 | pollFirst() | 获取并删除栈顶元素，失败则返回null |
peek() | getFirst() | 获取但不删除栈顶元素，失败则抛出异常 |
| 无 | peekFirst() | 获取但不删除栈顶元素，失败则返回null |