Java|2.10 Java中Queue和Deque接口 2|集合篇|queue|java|队列|queue和

2.10.1 什么是Queue 正如数据结构中描述，queue是一种先进先出的数据结构，也就是first in first out。可以将queue看作一个只可以从某一段放元素进去的一个容器，取元素只能从另一端取，整个机制如下图所示，不过需要注意的是，队列并没有规定是从哪一端插入，从哪一段取出。

文章图片

2.10.2 什么是Deque
Deque英文全称是Double ended queue，也就是俗称的双端队列。就是说对于这个队列容器，既可以从头部插入也可以从尾部插入，既可以从头部获取，也可以从尾部获取，其机制如下图所示。

文章图片

2.10.3 Java中的Queue接口
此处需要注意，Java中的队列明确有从尾部插入，头部取出，所以Java中queue的实现都是从头部取出。

package java.util; public interface Queue extends Collection {//集合中插入元素 boolean add(E e); //队列中插入元素 boolean offer(E e); //移除元素，当集合为空，抛出异常 E remove(); //移除队列头部元素并返回，如果为空，返回null E poll(); //查询集合第一个元素，如果为空，抛出异常 E element(); //查询队列中第一个元素，如果为空，返回null E peek(); }

Queue接口方法	作用
boolean offer(E e)	往队列中插入元素
E poll()	队列中移除元素，并返回该元素
E peek()	获取队列头部元素，但不做修改

Java queue常常使用的方法如表格所示，对于表格中接口和表格中没有的接口方法区别为：队列的操作不会因为队列为空抛出异常，而集合的操作是队列为空抛出异常。
2.10.4 Deque接口

package java.util; public interface Deque extends Queue { //deque的操作方法 void addFirst(E e); void addLast(E e); boolean offerFirst(E e); boolean offerLast(E e); E removeFirst(); E removeLast(); E pollFirst(); E pollLast(); E getFirst(); E getLast(); E peekFirst(); E peekLast(); boolean removeFirstOccurrence(Object o); boolean removeLastOccurrence(Object o); // *** Queue methods *** boolean add(E e); boolean offer(E e); E remove(); E poll(); E element(); E peek(); // 省略一堆stack接口方法和collection接口方法 }

和Queue中的方法一样，方法名多了First或者Last，First结尾的方法即从头部进行操作，Last即从尾部进行操作。
2.10.5 Queue，Deque的实现类
【Java|2.10 Java中Queue和Deque接口】Java中关于Queue的实现主要用的是双端队列，毕竟操作更加方便自由，Queue的实现有PriorityQueue，Deque在java.util中主要有ArrayDeque和LinkedList两个实现类，两者一个是基于数组的实现，一个是基于链表的实现。在之前LinkedList文章中也提到过其是一个双向链表，在此基础之上实现了Deque接口。