特点：元素有序，可重复。包含以下几个常用的实现类：
这里后两者都实现了Queue接口的子接口Deque，由于LinkedList类已在先前的文章中总结完毕，故在此处省略。
PriorityQueue
- 基于二叉堆实现
- 按照入队元素的大小重新排序，最小的元素最先出队列（最小堆）
- 默认排序方式为升序排序
- 线程不安全
构造方法
1
PriorityQueue<E> nums = new PriorityQueue<>();
常用方法
| 方法类型 | 具体方法 | 描述 |
|---|---|---|
| 添加元素 | add(E e) offer(E e) | 向优先队列中添加元素，当队列已满会抛异常 向优先队列中添加元素，当队列已满会返回 false |
| 访问元素 | element() peek() | 获取队头元素，队列为空时抛异常 获取队头元素，队列为空时返回 null |
| 删除元素 | remove() poll() | 删除队头元素并返回，队列为空时抛异常 删除队头元素并返回，队列为空时返回 null |
| 其他 | size() contains(E e) toArray() | 返回队列长度 判断队列中是否包含指定元素 将队列转化为数组并返回 |
代码示例：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
import java.util.*;
public class priorityqueue{
public static void main(String[] args){
/* initialization */
PriorityQueue<Integer> nums = new PriorityQueue<>();
/* add, offer */
for (int i = 10; i > 0; i--){
nums.offer(i);
}
print("offer:", nums);
nums.add(0);
print("add:", nums);
/* element, peek */
print("element(default):", nums.element());
print("peek(default):", nums.peek());
/* remove, poll */
print("remove:", nums.remove());
print("poll:", nums.poll());
/* size */
print("size:", nums.size());
/* contains */
print("contains 7:", nums.contains(7));
print("contains 100:", nums.contains(100));
}
public static void print(String prompt, PriorityQueue<Integer> nums){
System.out.println(String.format("%-30s %-30s", prompt, nums));
}
public static void print(String prompt, Object num){
System.out.println(String.format("%-30s %-30s", prompt, num));
}
public static void print(String prompt, boolean contain){
System.out.println(String.format("%-30s %-30s", prompt, contain));
}
}
输出：
1
2
3
4
5
6
7
8
9
offer: [1, 2, 5, 4, 3, 9, 6, 10, 7, 8]
add: [0, 1, 5, 4, 2, 9, 6, 10, 7, 8, 3]
element(default): 0
peek(default): 0
remove: 0
poll: 1
size: 9
contains 7: true
contains 100: false
遍历方式
遍历队列的方式：
1
2
3
4
Iterator<Integer> iter = nums.iterator();
while (iter.hasNext()){
print("iter:", iter.next());
}
输出：
1
2
3
4
5
6
7
8
9
10
11
iter: 0
iter: 1
iter: 5
iter: 4
iter: 2
iter: 9
iter: 6
iter: 10
iter: 7
iter: 8
iter: 3
比较器（Comparator）
通过使用Comparator，我们可以自定义队列中元素的排序方式。使用时需要创建自定义的比较器类，令其实现Comparator接口，示例如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class CustomComparator implements Comparator<Integer>{
@Override
public int compare(Integer n1, Integer n2){
if (n1 > n2){
return -1;
}
else if (n1 == n2){
return 0;
}
else{
return 1;
}
}
}
这里看到通过Comparator接口实现的自定义类中存在一个compare方法，它的作用是用来定义参数的排序方式。更具体地说，这个方法返回一个具有三种可能性的值 （正、负、零），分别代表第一个参数大于、小于、等于第二个参数。而这里可以看到当n1 > n2时返回负值，说明此时在这个自定义的比较器类中正常情况下越大的整数会被识别为越小的值，也即倒序排列。将这个自定义的排序方式应用到优先队列中的方式如下：
1
PriorityQueue<Integer> nums = new PriorityQueue<>(new CustomComparator());
此时这个优先队列实际上成为了一个最大堆。最后看一下实现的效果：
1
2
3
4
for (int i = 0; i < 10; i++){
nums.offer(i);
}
System.out.println(String.format("%-10s %-10s", "nums:", nums));
输出：
1
nums: [9, 8, 5, 6, 7, 1, 4, 0, 3, 2]
ArrayDeque
- 基于数组实现
- 查找快，增删慢
- 线程不安全
- 可以用作栈，效率高于Stack
- 可以用作队列，效率高于LinkedList
构造方法
1
ArrayDeque<Integer> nums = new ArrayDeque<>();
常用方法
| 方法类型 | 具体方法 | 描述 | 是否抛异常 | 是否返回值 |
|---|---|---|---|---|
| 添加元素 | add(E e) addFirst(E e) addLast(E e) | 将指定元素添加至队尾 将指定元素添加至队头 将指定元素添加至队尾（与 add()等效） | 是 | 否，添加失败时抛异常 |
| 添加元素 | offer(E e) offerFirst(E e) offerLast(E e) | 将指定元素添加至队尾 将指定元素添加至队头 将指定元素添加至队尾 | 否 | 是，添加失败则返回false反之true |
| 访问元素 | getFirst() getLast() | 返回队头元素 返回队尾元素 | 是 | 是，队列为空时抛异常 |
| 访问元素 | peek() peekFirst() peekLast() | 返回队头元素 返回队头元素（与 peek()等效） 返回队尾元素 | 否 | 是，队列为空时返回null |
| 删除元素 | remove() removeFirst() removeLast() | 删除并返回队头元素 删除并返回队头元素（与 remove()等效）删除并返回队尾元素 | 是 | 是，队列为空时抛异常 |
| 删除元素 | poll() pollFirst() pollLast() | 删除并返回队头元素 删除并返回队头元素（与 poll()等效）删除并返回队尾元素 | 否 | 是，队列为空时返回null |
代码示例：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
import java.util.*;
public class arraydeque {
public static void main(String[] args){
/* initialization */
ArrayDeque<Integer> nums = new ArrayDeque<>();
nums.add(0);
print("initial arrayqueue:", nums);
System.out.println("");
/* add */
nums.add(1);
print("add 1:", nums);
nums.addFirst(2);
print("addFirst 2:", nums);
nums.addLast(3);
print("addLast 3:", nums);
System.out.println("");
/* offer */
nums.offer(4);
print("offer 4:", nums);
nums.offerFirst(5);
print("offerFirst 5:", nums);
nums.offerLast(6);
print("offerLast 6:", nums);
System.out.println("");
/* get */
print("getFirst:", nums.getFirst());
print("getLast:", nums.getLast());
System.out.println("");
/* peek */
print("peek:", nums.peek());
print("peekFirst:", nums.peekFirst());
print("peekLast:", nums.peekLast());
System.out.println("");
/* remove */
print("remove:", nums.remove());
print("removeFirst:", nums.removeFirst());
print("removeLast:", nums.removeLast());
System.out.println("");
/* poll */
print("poll:", nums.poll());
print("pollFirst:", nums.pollFirst());
print("pollLast:", nums.pollLast());
}
public static void print(String prompt, ArrayDeque<Integer> nums){
System.out.println(String.format("%-20s %-30s", prompt, nums));
}
public static void print(String prompt, Integer num){
System.out.println(String.format("%-20s %-30s", prompt, num));
}
}
输出：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
initial arrayqueue: [0]
add 1: [0, 1]
addFirst 2: [2, 0, 1]
addLast 3: [2, 0, 1, 3]
offer 4: [2, 0, 1, 3, 4]
offerFirst 5: [5, 2, 0, 1, 3, 4]
offerLast 6: [5, 2, 0, 1, 3, 4, 6]
getFirst: 5
getLast: 6
peek: 5
peekFirst: 5
peekLast: 6
remove: 5
removeFirst: 2
removeLast: 6
poll: 0
pollFirst: 1
pollLast: 4
遍历方式
同样还是采用Iterator：
1
2
3
4
Iterator<Integer> iter = nums.iterator();
while (iter.hasNext()){
print("iter:", iter.next());
}
输出：
1
2
3
4
5
6
7
iter: 5
iter: 2
iter: 0
iter: 1
iter: 3
iter: 4
iter: 6
