Java中的队列
Queue
API
| 功能 | 抛出异常 | 返回false或null |
|---|---|---|
| 添加 | add() | offer() |
| 查询不删除 | element() | peek() |
| 查询并删除 | remove() | poll() |
Deque
双端队列
| 功能 | 抛出异常 | 返回false或null |
|---|---|---|
| 添加到队列尾部 | add() | offer() |
| addLast() | offerLast() | |
| 添加到队列头部 | push() | |
| addFirst() | offerFirst() | |
| 查询不删除头部 | element() | peek() |
| getFirst() | peekFirst() | |
| 查询不删除尾部 | getLast() | peekLast() |
| 查询并删除头部 | remove()/pop() | poll() |
| removeFirst() | pollFirst() | |
| 查询并删除尾部 | removeLast() | pollLast() |
BlockingQueue
阻塞队列，线程安全
| 功能 | 抛出异常 | 返回false或null | 阻塞 | 阻塞等待，超时抛出异常 |
|---|---|---|---|---|
| 添加 | add() | offer() | put() | offer(E e,long timeout,TimeUnit unit) |
| 查询并删除 | take() | poll(long timeout,TimeUnit unit) |
其他API
int remainingCapacity()：返回剩余容量；
boolean remove(Object o)：删除一个指定元素，成功返回true；
boolean contains(Object o)：若队列包含指定元素，返回true；
int drainTo(Collection<? super E> c)：队列中删除所有元素，并将元素添加到指定集合；
int drainTo(Collection<? super E> c,int maxElements)：同上，可以指定最大元素数量；
BlockingDeque
阻塞队列和双端队列的结合；
新增的API
等待
takeFirst / take：查询并删除队列第一个元素，如果没有则阻塞；
takeLast：查询并删除队列最后一个元素，没有则阻塞；
putFirst / putLast：插入元素，若队列满则阻塞等待；
等待超时
offerFirst(E e, long timeout,TimeUnit unit)：添加元素到队首，若队列满则等待；
offer 或 offerLast(E e,long timeout,TimeUnit unit)：同上；
pollFirst(long timeout,TimeUnit unit)：查询并删除第一个元素，队列空则等待，超时则抛出错误；
pollLast(long timeout,TimeUnit unit)：同上；
LinkedBlockingDeque
链表实现的双端阻塞队列
ArrayBlockingQueue
数组实现的阻塞队列
可以给定容量和访问策略
- ArrayBlockingQueue(int capacity)
- ArrayBlockingQueue(int capacity,boolean fair)
- ArrayBlockingQueue(int capacity,boolean fair,Collection<?extends E> c)
PriorityBlockingQueue
优先队列的阻塞版本
不允许有null元素
SynchronousQueue
没有容量的同步队列。
一旦有消费或生产过程，就必须有相应的生产或消费过程，否则阻塞；
队列中没有容量，在这个队列中，不参与等待的API一律返回null，比如：
- remove、containsAll、removeAll、retainAll永远返回false；
- peek永远返回null。
可以指定访问策略
- SynchronousQueue()，创建一个不公平的同步队列；
- SynchronousQueue(boolean fair)，指定公平/不公平。
API
put(E e)：将元素添加到队列，然后阻塞等待另一个线程接收元素；
offer(E e, long timeout,TimeUnit unit)：将元素插入到队列中，等待消费者消费，超时则hole..；
offer(E e)：若有另一个线程在等待接收元素，则将元素插入到队列中，否则返回false；
take()：查询队列首元素，删除元素并返回，若队列中没有数据则阻塞等待；
poll(long timeout,TimeUnit unit)：查询队列首元素，删除元素并返回，若队列空则等待，超时返回null；
poll()：查询队列首元素，删除元素并返回，若队列空则返回null；
TransferQueue
这个队列可以实现生产者消费者程序，并协调消息使消息能够从生产者传输到消费者；
新增API
getWaitingConsumerCount()：获取等待的消费者数量；
hasWaitingConsumer()：获取是否有消费者在等待；
transfer()：将元素交给消费者，如果没有消费者，则等待；
tryTransfer()：将元素交给消费者，若没有消费者，则抛弃元素，返回false；
tryTransfer(E e,long timeout,Timeunit unit)：将元素交给消费者，若没有消费者，则等待，超时则抛弃元素，返回false；
LinkedTransferQueue
链表实现的TransferQueue。
特别的API
- transfer：将元素转移给消费者，若没有消费者，则等待；
- 将元素插入到队列尾部，然后等待消费者消费；
- tryTransfer(E e, long timeout, TimeUnit unit)：将元素插入队列，然后等待消费者消费；若超时，则取消阻塞，返回false；成功返回true；
- take：从队列的头中取出元素，若没有元素则等待；
- poll(long timeout, TimeUnit unit)：take的超时版本，从队列的头中取出元素，若没有元素则等待，超时返回null；
- poll()：从队列头部取出元素，若没有元素，则返回null；
- peek()：查询不删除队列头部元素，若队列空，则返回null；
AbstractQueue
API
add(E e)：添加元素，失败抛出异常；
addAll(Collection<? extends E> c)：添加元素，失败抛出异常；
clear：删除所有元素；
element：查询不删除头部元素；
remove：查询并删除头部元素；
ConcurrentLinkedQueue
基于链表，无界的线程安全队列；
LinkList
线程不安全，基于链表的队列；
PriorityQueue优先队列
特点
- 无限长的队列，并且动态增长，默认初始容量可以用构造参数initialCapacity参数覆盖；
- 不允许有NULL对象；
- 添加到PriorityQueue的对象必须有可比性；
- 默认情况下，队列按自然顺序排序；
- 比较器可用于队列中对象的自定义排序；
- 线程不安全；
- add和poll方法复杂度：O(log(n))
API
boolean add(object) 将指定对象插入；
boolean offer(object) 将指定对象插入；
boolean remove(object) 从此队列删除指定元素的单个实例；
Object poll()：删除并返回队列的头部，若队列为空，返回null；
Object element()：获取队列头部；
Object peek()：获取队列头部；
clear()：从队列中删除所有元素；
comparator()：返回队列的比较器；
contains(Object o)：是否包含指定元素。
一些API的区别
add、remove、element：抛出异常；
offer、poll、peek：不抛出异常，返回null；
| 抛出异常 | 不抛出异常 | |
|---|---|---|
| 添加 | add | offer |
| 删除 | remove | poll |
| 获取首元素 | element | peek |