Java 队列
Queue接口继承自Collection接口，除了最基本的Collection的方法之外，它还支持额外的 添加、删除 和 检查 操作。
队列 Queue
Queue的方法概述(设计思想)如下：
| 方法 \ 形式 | 抛异常 | 返回特殊值 |
|---|---|---|
| 添加元素 | add(e) | offer(e) |
| 删除元素 | remove() | poll() |
| 检查元素 | element() | peek() |
Queue源码
package java.util;
/**
* 设计用于在处理前保存元素的集合。
* 除了基本的收集操作外，队列还提供额外的插入、提取和检查操作。
*
* 这些方法都有两种形式：一种是在操作失败时抛出异常，另一种是返回特殊值（null或false，取决于操作）。
* 后一种形式的插入操作专门设计用于容量受限的队列实现；在大多数实现中，插入操作不会失败。
*
* 队列通常(但不一定)以FIFO(先进先出)方式对元素进行排序。
* 例外情况包括优先级队列
*
* 该接口是Java集合框架的成员。
*/
public interface Queue<E> extends Collection<E> {
/**
* 如果可以在不违反容量限制的情况下立即将指定元素插入此队列，在成功时返回 true，
* 如果当前没有可用空间则抛出 IllegalStateException。
*
* @param e 要添加的元素
* @return
* @throws IllegalStateException 如果由于容量限制，此时无法添加元素
* @throws ClassCastException 如果指定元素的类阻止将其添加到此队列中
* @throws NullPointerException 如果指定的元素为null，并且此队列不允许使用null元素
* @throws IllegalArgumentException 如果此元素的某些属性阻止将其添加到此队列中
*/
boolean add(E e);
/**
* add(e) 的优化版
* 在队列容量满了添加时不抛异常
* 其它和add(e)都一样
*/
boolean offer(E e);
/**
* 检索并删除此队列的头部。
* 队列为空会抛异常
*
* @return 队列头结点
* @throws NoSuchElementException 如果队列为空
*/
E remove();
/**
* 检索并删除此队列的头部，如果此队列为空，则返回 null。
*
* @return 队列头结点，队列为空时返回null
*/
E poll();
/**
* 检索但不删除此队列的头部。
* 如果此队列为空，抛异常 NoSuchElementException 。
*
* @return 队列头结点
* @throws NoSuchElementException 如果队列为空
*/
E element();
/**
* element()优化版
*
* 检索但不删除此队列的头部，如果此队列为空，则返回 null。
*
* @return 队列头结点，队列为空时返回null
*/
E peek();
}双端队列 Deque
Deque方法概述
| 方法 \ 形式 | (头结点)抛异常 | (头节点)返回特殊值 | (尾结点)抛异常 | (尾结点)返回特殊值 |
|---|---|---|---|---|
| 添加元素 | addFirst(e) | offerFirst(e) | addLast(e) | offerLast(e) |
| 移除元素 | removeFirst() | pollFirst() | removeLast() | pollLast() |
| 检查元素 | getFirst() | peekFirst() | getLast() | peekLast() |
Deque接口扩展了 Queue接口。当deque用作队列时，会产生FIFO（先进先出）行为。
队列 和 双端队列 方法对比
| 队列方法 | 等效 双端队列方法 |
|---|---|
| add(e) | addLast(e) |
| offer(e) | offerLast(e) |
| remove() | removeFirst() |
| poll() | pollFirst() |
| element() | getFirst() |
| peek() | peekFirst() |
双端队列也可以用作 LIFO(后进先出)堆栈。应优先使用此接口而不是旧的 Stack 类。
当双端队列用作堆栈时，从双端队列的开头推送和弹出元素。
Stack 方法等价于 Deque 方法
Stack和Deque方法的比较
| 栈方法 | 等效 双端队列方法 |
|---|---|
| push(e) | addFirst(e) |
| pop(e) | removeFirst(e) |
| peek() | getFirst() |
Deque源码
package java.util;
/**
* deque是“双端队列”的缩写
* 支持在两端插入和移除元素的线性集合。
*/
public interface Deque<E> extends Queue<E> {
/**
* 在此双端队列的前面插入指定元素
* 队列满了会抛异常 IllegalStateException
*/
void addFirst(E e);
/**
* 在此双端队列末尾插入指定元素
* 队列满了会抛异常 IllegalStateException
*/
void addLast(E e);
/**
* 在此双端队列的前面插入指定元素
* 队列满了会失败
*/
boolean offerFirst(E e);
/**
* 在此双端队列末尾插入指定元素
* 队列满了会失败
*/
boolean offerLast(E e);
/**
* 移除首个元素
*
* 队列为空抛异常 NoSuchElementException
*/
E removeFirst();
/**
* 移除队列最后一个元素
*
* 队列为空抛异常 NoSuchElementException
*/
E removeLast();
/**
* 移除首个元素
*
* 队列为空返回null
*/
E pollFirst();
/**
* 移除最后一个元素
*
* 队列为空返回null
*/
E pollLast();
/**
* 检索但不删除此双端队列的第一个元素。
*
* 队列为空抛异常 NoSuchElementException
*/
E getFirst();
/**
* 检索但不删除此双端队列的最后一个元素。
*
* 队列为空抛异常 NoSuchElementException
*/
E getLast();
/**
* 检索但不删除此双端队列的第一个元素。
*
* 队列为空返回null
*/
E peekFirst();
/**
* 检索但不删除此双端队列的最后一个元素。
*
* 队列为空返回null
*/
E peekLast();
/**
* 从此双端队列中删除第一次出现的指定元素。
* 如果双端队列不包含该元素，则它保持不变。
*/
boolean removeFirstOccurrence(Object o);
/**
* 从此双端队列中删除最后一次出现的指定元素。
* 如果双端队列不包含该元素，则它保持不变。
*/
boolean removeLastOccurrence(Object o);
// 队列方法
boolean add(E e);
boolean offer(E e);
E remove();
E poll();
E element();
E peek();
boolean addAll(Collection<? extends E> c);
// 栈方法
/**
* 将元素推送到此双端队列表示的堆栈上(队列头部)
*
* 容量满了抛异常 IllegalStateException
*
* 等效于 addFirst
*/
void push(E e);
/**
* 从双端队列表示的堆栈中弹出一个元素。换句话说，删除并返回此双端队列的第一个元素。
*
* 队列为空抛异常 NoSuchElementException
*
* 等效于 removeFirst()
*/
E pop();
// 集合方法
/**
* 从双端队列中删除第一次出现的指定元素。
* 如果双端队列不包含该元素，则它保持不变。
*
* 等效于 removeFirstOccurrence(Object)
*/
boolean remove(Object o);
/**
* 如果此双端队列包含指定元素，则返回 true。
*/
boolean contains(Object o);
/**
* 返回队列的长度
*/
int size();
/**
* 以正确的顺序返回此双端队列中元素的迭代器。
*
* 元素将按从第一个(头)到最后一个(尾)的顺序返回。
*/
Iterator<E> iterator();
/**
* 以相反的顺序返回此双端队列中元素的迭代器。
*
* 元素将按从最后(尾)到第一个(头)的顺序返回。
*/
Iterator<E> descendingIterator();
}