PriorityQueue
介绍&操作
PriorityQueue和Queue的区别在于，它的出队顺序与元素的优先级有关，对PriorityQueue调用remove()或poll()方法，返回的总是优先级最高的元素。
要使用PriorityQueue，我们就必须给每个元素定义“优先级”。我们以实际代码为例，先看看PriorityQueue的行为：
public class Main {public static void main(String[] args) {Queue<String> q = new PriorityQueue<>();// 添加3个元素到队列:q.offer("apple");q.offer("pear");q.offer("banana");System.out.println(q.poll()); // appleSystem.out.println(q.poll()); // bananaSystem.out.println(q.poll()); // pearSystem.out.println(q.poll()); // null,因为队列为空}
}我们放入的顺序是"apple"、"pear"、"banana"，但是取出的顺序却是"apple"、"banana"、"pear"，这是因为从字符串的排序看，"apple"排在最前面，"pear"排在最后面。
因此，放入PriorityQueue的元素，必须实现Comparable接口，PriorityQueue会根据元素的排序顺序决定出队的优先级。
如果我们要放入的元素并没有实现Comparable，PriorityQueue允许我们提供一个Comparator对象来判断两个元素的顺序。我们以银行排队业务为例，实现一个PriorityQueue：
public class Main {public static void main(String[] args) {Queue<User> q = new PriorityQueue<>(new UserComparator());// 添加3个元素到队列:q.offer(new User("Bob", "A10"));q.offer(new User("Alice", "A2"));q.offer(new User("Boss", "V1"));System.out.println(q.poll()); // Boss/V1System.out.println(q.poll()); // Bob/A1System.out.println(q.poll()); // Alice/A2System.out.println(q.poll()); // null,因为队列为空}
}
/**
*实现PriorityQueue的关键在于提供的UserComparator对象，它负责比较两个元素的大小（较小的在前）。UserComparator总是把V开头的号码优先返回，只有在开头相同的时候，才比较号码大小。
*/
class UserComparator implements Comparator<User>{public int compare(User user1,User user2) {if(user1.number.charAt(0) == user2.number.charAt(0)){//比较A A 或者V Vreturn Integer.parseInt(user1.number.substring(1))-Integer.parseInt(user2.number.substring(1));}else if (user1.number.charAt(0) == 'V'){return -1;}else{return 1;}}
}class User {public final String name;public final String number;public User(String name, String number) {this.name = name;this.number = number;}public String toString() {return name + "/" + number;}
}Deque
介绍
允许两头都进，两头都出，这种队列叫双端队列（Double Ended Queue），学名Deque。
Java集合提供了接口Deque来实现一个双端队列，它的功能是：
-
既可以添加到队尾，也可以添加到队首；
-
既可以从队首获取，又可以从队尾获取。
比较一下Queue和Deque出队和入队的方法：
可以看出，对于添加元素到队尾的操作，Queue提供了add()/offer()方法，而Deque提供了addLast()/offerLast()方法。添加元素到对首、取队尾元素的操作在Queue中不存在，在Deque中由addFirst()/removeLast()等方法提供。
注意到Deque接口实际上扩展自Queue：
public interface Deque<E> extends Queue<E> {...
} 因此，Queue提供的add()/offer()方法在Deque中也可以使用，但是，使用Deque，最好不要调用offer()，而是调用offerLast()，这样方面我们一眼看出来这个事添加到队尾
Deque是一个接口，它的实现类有ArrayDeque和LinkedList。
我们发现LinkedList真是一个全能选手，它即是List，又是Queue，还是Deque。但是我们在使用的时候，总是用特定的接口来引用它，这是因为持有接口说明代码的抽象层次更高，而且接口本身定义的方法代表了特定的用途。
// 不推荐的写法:
LinkedList<String> d1 = new LinkedList<>();
d1.offerLast("z");
// 推荐的写法：
Deque<String> d2 = new LinkedList<>();
d2.offerLast("z");可见面向抽象编程的一个原则就是：尽量持有接口，而不是具体的实现类。