Queue 队列
Queue 接口的定义形式是：
public interface Queue<E> extends Collection<E>
队列可以让人们有效的在尾部添加一个元素，在头部删除一个元素。 是一种先入先出 （FIFO ） 的数据结构。
双端队列可以让人们有效的在头部和尾部同时添加或删除元素，不支持在队列中间添加元素。
在Java SE 6 中引入了Deque接口，并由 ArrayDeque 和 LinkedLisk 类实现。这两个类都提供了双端队列，而且在必要时可以增加队列的长度。
Collection接口继承树
由上图可以看出Queue类也可以用 LinkedList实现
Queue<E> queue = new LinkedList<E>();
1. API
类型方法名功能
booleanadd(E element)将元素element插入到队列的尾部booleanoffer(E element)将元素element插入到队列的尾部，如果队列已满，返回nullEremove()删除并返回队列头部元素Epoll()删除并返回队列头部元素，如果队列为空，返回nullEelement()返回队列头部元素，但是不会删除该元素Epeek()返回队列头部元素，但是不会删除该元素，如果队列为空，返回null
1.1 java.util.Queue< E > 5.0
boolean add(E element
)
boolean offer(E element
)
E
remove()
E
poll()
E
element()
E
peek()
注1：如果队列没有满， add 与 offer 方法会将给定的元素添加到队列的尾部并返回 true,如果队列已满，add方法将会抛出一个 IllegalStateException 异常，而offer方法会返回 false
注2：如果队列没有空，remove 与 poll 方法会删除并返回队列头部元素 ；如果队列为空，remove方法会抛出一个 NoSuchElementException异常，poll方法会返回 null
注3：如果队列没有空，element 与 peek 方法会返回队列头部元素，但是 不会删除 ；如果队列为空，element方法会抛出一个 NoSuchElementException异常，peek方法会返回 null
1.2 java.util.Deque< E > 6
类型方法名功能
voidaddFirst(E element)给定的对象添加到双端队列的头部voidaddLast(E element)给定的对象添加到双端队列的尾部booleanofferFirst(E element)给定的对象添加到双端队列的头部，如果队列满了，返回falsebooleanofferLast(E element)给定的对象添加到双端队列的尾部，如果队列满了，返回falseEremoveFirst()删除并返回队列头部的元素EremoveLast()删除并返回队列尾部的元素EpollFirst()删除并返回队列头部的元素，如果队列为空，返回nullEpollLast()删除并返回队列尾部的元素，如果队列为空，返回nullEgetFirst()返回队列头部元素，但是不会删除该元素EgetLast()返回队列尾部元素，但是不会删除该元素EpeekFirst()返回队列头部元素，但是不会删除该元素，如果队列为空，返回nullEpeekLast()返回队列尾部元素，但是不会删除该元素，如果队列为空，返回null
void addFirst(E element
)
void addLast(E element
)
boolean offerFirst(E element
)
boolean offerLast(E element
)
将给定的对象添加到双端队列的头部或尾部 。如果队列满了，前面两个方法将抛出一个
IllegalStateException 异常，后面两个方法返回false。
E
removeFirst()
E
removeLast()
E
pollFirst()
E
pollLast()
如果队列没有空，
删除并返回队列头部的元素 。如果队列为空，前面两个方法将抛出一个
NoSuchElemtentException 异常，而后面两个方法返回null。
E
getFirst()
E
getLast()
E
peekFirst()
E
peekLast()
如果队列没有空，返回队列头部的元素，
但不删除 。如果队列为空，前面两个方法将抛出一个
NoSuchElemtentException 异常，而后面两个方法返回null。
1.3 java.util.ArrayDeque< E > 5
ArrayDeque()
ArrayDeque(int initialCapacity
)
用初始容量(Initial Capacity) 16 或给定的初始容量构造一个
无限双端队列.
1.4 代码演示（用队列求交集）
当然求交集还可以运用hash散列的方式更快的求得；
package 数据结构
;
import java
.util
.*
;
public class Main {
public static void main(String
[] args
) {
Scanner cin
= new Scanner(System
.in
);
Queue
<Integer> q1
= new LinkedList<Integer>();
Queue
<Integer> q2
= new LinkedList<Integer>();
int n
= cin
.nextInt();
int tmp
= n
;
while(tmp
-->0) {
int s
= cin
.nextInt(),t
= cin
.nextInt();
for(int i
=s
;i
<t
;i
++) {
q1
.offer(i
);
}
}
tmp
= n
;
while(tmp
-->0) {
int s
= cin
.nextInt(),t
= cin
.nextInt();
for(int i
=s
;i
<t
;i
++) {
q2
.offer(i
);
}
}
int cnt
= 0;
while(!q1
.isEmpty() && !q2
.isEmpty()) {
if(q1
.peek() > q2
.peek())
q2
.poll();
else if(q1
.peek()<q2
.peek())
q1
.poll();
else {
cnt
++;
q1
.poll();
q2
.poll();
}
}
System
.out
.println(cnt
);
}
}
2. 优先级队列
2.1 优先队列的特点
优先级队列（priority queue）中的元素可以按照任意的顺序输入，却总是按照排序的顺序进行检索。也就是说，无论何时调用 poll 方法，总会获得当前优先级队列中最小的元素。然而，优先级队列并没有对所有的元素进行排序。
如果使用迭代的方式处理这些元素，并不需要对它们进行排序。优先级队列使用了一个优雅且高效的数据结构，称为堆 (heap) 。堆是一个可以可以自我调整的二叉树，对树执行 offer 和 poll 操作，可以让最小的元素移动到根，而不必花费时间对元素进行排序。与 TreeSet 一样，一个优先级队列既可以保存实现了 Comparable 接口的类对象，也可以保存在构造器中提供的 Comparator 对象。使用优先级队列的典型示例是任务调度。每一个任务有一个优先级，任务以随机顺序添 加到队列中。每当启动一个新的任务时，都将优先级最高的任务从队列中删除（由于习惯上 将 1设为“ 最高” 优先级，所以会将最小的元素删除)。与 TreeSet 中的迭代不同，这里的迭代并不是按照元素的排列顺序访问的。而删除却总是删掉剩余元素中优先级数最小的那个元素。
2.2 优先队列的方法
方法名功能
PriorityQueue()PriorityQueue(int initialCapacity)构造一个用于存放 Comparable 对象的优先级队列。ProrityQueue(int initialCapacity, Comparator ? super E> c)构造一个优先级队列，并用指定的比较器对元素进行排序。
2.3 示例代码
package 数据结构
;
import java
.util
.*
;
class Person
{
private String name
;
private int population
;
public Person() {};
public Person(String name
, int population
) {
this.name
= name
;
this.population
= population
;
}
public String
getName() {
return this.name
;
}
public int getPopulation() {
return this.population
;
}
public String
toString() {
return getName()+" - " + getPopulation();
}
}
public class Main {
public static void main(String
[] args
) {
Scanner cin
= new Scanner(System
.in
);
Comparator
<Person> cmp
= new Comparator<Person>() {
public int compare(Person arg0
, Person arg1
) {
int num_a
= arg0
.getPopulation();
int num_b
= arg1
.getPopulation();
if(num_a
< num_b
) return 1;
else if(num_a
> num_b
) return -1;
else return 0;
}
};
Queue
<Person> priorityQueue
= new PriorityQueue<Person>(11,cmp
);
Person p1
= new Person("p1",1);
Person p2
= new Person("p2",3);
Person p3
= new Person("p3",2);
Person p4
= new Person("p4",0);
priorityQueue
.offer(p1
);
priorityQueue
.offer(p2
);
priorityQueue
.offer(p3
);
priorityQueue
.offer(p4
);
System
.out
.println(priorityQueue
.poll().toString());
System
.out
.println(priorityQueue
.poll().toString());
System
.out
.println(priorityQueue
.poll().toString());
System
.out
.println(priorityQueue
.poll().toString());
}
}
运行结果：
结果分析：这里按照 Comparator 方法写的排序，如果改变 Comparator 方法 结果会改变；
未完持续……
参考文献 & 博客
Java核心技术 卷Ⅰ基础知识（原书第10版）/（美）凯S.霍斯特曼（Cay S. Horstmann）机械工业出版社Java程序设计教程算法导论 （原书第3版）/ （美）Thomas H.Cormen 机械工业出版社数据结构 java语言描述 （原书第3版）/ （美） Michael Main 机械工业出版社
https://www.cnblogs.com/vachester/p/5840217.html 堆和优先队列https://www.cnblogs.com/nayitian/p/3266090.html#collectionframe （Java：集合，Collection接口框架图）http://www.importnew.com/6932.html （Java优先队列（PriorityQueue）示例）https://blog.csdn.net/hiphopmattshi/article/details/7334487?utm_source=blogxgwz0 （java中PriorityQueue优先级队列 使用样例）https://blog.csdn.net/cquzhengdayday/article/details/72514900 （浅谈堆以及java优先队列的详细使用）
