Queue

Queue 是实现了一个先进先出（FIFO：First In First Out）的有序表，也是非常常用的。

它和 List 的区别在于，List 可以在任意位置添加和删除元素，而 Queue 只有两个操作：

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

常用方法

队列接口 Queue 定义了以下几个方法：

• int size()：获取队列长度；
• boolean add(E)/boolean offer(E)：添加元素到队尾；
• E remove()/E poll()：获取队首元素并从队列中删除；
• E element()/E peek()：获取队首元素但并不从队列中删除。

两套方法的区别在于：前面一套在执行失败的时候会抛出异常，后面一套会返回 false 或 null，按需选择。

演示下：

    Queue<String> q = new LinkedList<>();
    q.offer("apple");
    q.offer("banana");
    q.offer("pear");
    System.out.println(q.poll()); //apple
    System.out.println(q.poll()); //banana
    System.out.println(q.poll()); //pear
    System.out.println(q.poll()); //null


    q.offer("apple");
    System.out.println(q.peek()); //apple
    System.out.println(q.peek()); //apple
    System.out.println(q.peek()); //apple

其他注意事项：

• 可以，但不要把 null 添加到队列中，否则 poll() 方法返回 null 时，很难确定是取到了 null 元素还是队列为空
• 对于具体的实现类，有的 Queue 有最大队列长度限制，有的 Queue 没有
• LinkedList 即实现了 List 接口，又实现了 Queue 接口

PriorityQueue

有时候，我们会用到优先队列，而用 Queue 是实现不了的，因此我们可以用 PriorityQueue，其内部是根据 Comparable 接口来决定顺序。例如

    Queue<String> q = new PriorityQueue<>();
    q.offer("apple");
    q.offer("pear");
    q.offer("banana");
    System.out.println(q.poll()); //apple
    System.out.println(q.poll()); //banana
    System.out.println(q.poll()); //pear

我们放入的顺序是 "apple"、"pear"、"banana"，但是取出的顺序却是 "apple"、"banana"、"pear"，这是因为从字符串的排序看，"apple" 排在最前面，"pear" 排在最后面。

因此，放入 PriorityQueue 的元素，必须实现 Comparable 接口，或者在创建 PriorityQueue 的时候提供一个 Comparator 对象。

Deque

Queue 是队列，只能一头进，另一头出。如果把条件放松一下，允许两头都进，两头都出，这种队列叫双端队列（Double Ended Queue），学名 Deque。

Deque 是一个接口，它的实现类有 ArrayDeque 和 LinkedList。

Deque 常用方法：

• addLast(E e) / offerLast(E e)：添加元素到队尾
• E removeFirst() / E pollFirst()：取队首元素并删除
• E getFirst() / E peekFirst()：取队首元素但不删除
• addFirst(E e) / offerFirst(E e)： 添加元素到队首
• E removeLast() / E pollLast()：取队尾元素并删除
• E getLast() / E peekLast()：取队尾元素但不删除

Queue 提供的 add()/offer() 方法在 Deque 中也可以使用，但是最好使用 Deque 的方法。

演示如下：

    Deque<String> deque = new LinkedList<>();
    deque.offerLast("A"); // A
    deque.offerLast("B"); // A <- B
    deque.offerFirst("C"); // C <- A <- B
    System.out.println(deque.pollFirst()); // C, 剩下A <- B
    System.out.println(deque.pollLast()); // B, 剩下A
    System.out.println(deque.pollFirst()); // A
    System.out.println(deque.pollFirst()); // null