Queue

特点：FIFO（先进先出）
Queue和List的区别在于，List可以在任意位置添加和删除元素，而Queue只有两个操作：

  • 把元素添加到队列末尾；
  • 从队列头部取出元素。

在Java的标准库中，队列接口Queue定义了以下几个方法：

  • int size()：获取队列长度；
  • boolean add(E)/boolean offer(E)：添加元素到队尾；
  • E remove()/E poll()：获取队首元素并从队列中删除；
  • E element()/E peek()：获取队首元素但并不从队列中删除。 | 方法 | throw Exception | 返回false或null | | —- | —- | —- |

| 添加元素到队尾 | add(E e) | boolean offer(E e) |

| 取队首元素并删除 | E remove() | E poll() |

| 取队首元素但不删除 | E element() | E peek() |

LinkedList即实现了List接口，又实现了Queue接口，但是，在使用的时候，如果我们把它当作List，就获取List的引用，如果我们把它当作Queue，就获取Queue的引用：

  1. // 这是一个List:
  2. List<String> list = new LinkedList<>();
  3. // 这是一个Queue:
  4. Queue<String> queue = new LinkedList<>();

始终按照面向抽象编程的原则编写代码，可以大大提高代码的质量。

PriorityQueue

PriorityQueue实现了一个优先队列：从队首获取元素时，总是获取优先级最高的元素。
对于PriortyQueue，必须实现Comparable接口，它会根据元素的排序顺序决定出队的优先级
如果没有实现Comparable接口，可以提供一个Comparator对象来判断两个元素的顺序。

  1. import java.util.Comparator;
  2. import java.util.PriorityQueue;
  3. import java.util.Queue;
  4. public class Main {
  5.     public static void main(String[] args) {
  6.         Queue<User> q = new PriorityQueue<>(new UserComparator());
  7.         // 添加3个元素到队列:
  8.         q.offer(new User("Bob", "A1"));
  9.         q.offer(new User("Alice", "A2"));
  10.         q.offer(new User("Boss", "V1"));
  11.         System.out.println(q.poll()); // Boss/V1
  12.         System.out.println(q.poll()); // Bob/A1
  13.         System.out.println(q.poll()); // Alice/A2
  14.         System.out.println(q.poll()); // null,因为队列为空
  15.     }
  16. }
  18. class UserComparator implements Comparator<User> {
  19.     public int compare(User u1, User u2) {
  20.         if (u1.number.charAt(0) == u2.number.charAt(0)) {
  21.             // 如果两人的号都是A开头或者都是V开头,比较号的大小:
  22.             return u1.number.length() - u2.number.length() >0 ? 1 : u1.number.compareTo(u2.number);
  23.         }
  24.         if (u1.number.charAt(0) == 'V') {
  25.             // u1的号码是V开头,优先级高:
  26.             return -1;
  27.         } else {
  28.             return 1;
  29.         }
  30.     }
  31. }
  33. class User {
  34.     public final String name;
  35.     public final String number;
  37.     public User(String name, String number) {
  38.         this.name = name;
  39.         this.number = number;
  40.     }
  42.     public String toString() {
  43.         return name + "/" + number;
  44.     }
  45. }

Deque

Deque实现了一个双端队列（Double Ended Queue），它可以：

  • 将元素添加到队尾或队首：addLast()/offerLast()/addFirst()/offerFirst()；
  • 从队首／队尾获取元素并删除：removeFirst()/pollFirst()/removeLast()/pollLast()；
  • 从队首／队尾获取元素但不删除：getFirst()/peekFirst()/getLast()/peekLast()；
  • 总是调用xxxFirst()/xxxLast()以便与Queue的方法区分开；
  • 避免把null添加到队列。

Deque是一个接口，它的实现类有ArrayDeque和LinkedList。
LinkedList真是一个全能选手，它即是List，又是Queue，还是Deque。但是我们在使用的时候，总是用特定的接口来引用它，这是因为持有接口说明代码的抽象层次更高，而且接口本身定义的方法代表了特定的用途。

  1. // 不推荐的写法:
  2. LinkedList<String> d1 = new LinkedList<>();
  3. d1.offerLast("z");
  4. // 推荐的写法：
  5. Deque<String> d2 = new LinkedList<>();
  6. d2.offerLast("z");

可见面向抽象编程的一个原则就是：尽量持有接口，而不是具体的实现类。