队列 Queue 优先队列PriorityQueue 双端队列Deque

队列（Queue）是一种经常使用的集合。Queue实际上是实现了一个先进先出（FIFO：First In First Out）的有序表。它和List的区别在于，List可以在任意位置添加和删除元素，而Queue只有两个操作：

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

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

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

对于具体的实现类，有的Queue有最大队列长度限制，有的Queue没有。注意到添加、删除和获取队列元素总是有两个方法，这是因为在添加或获取元素失败时，这两个方法的行为是不同的。我们用一个表格总结如下：

	throw Exception	返回false或null
添加元素到队尾	add(E e)	boolean offer(E e)
取队首元素并删除	E remove()	E poll()
取队首元素但不删除	E element()	E peek()

优先队列PriorityQueue：

实现了Comparable接口即可存入该队列 会按照compare方法逻辑来优先取出优先级高的数据（包装类内部已实现compare）

使用：

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()); // apple
        System.out.println(q.poll()); // banana
        System.out.println(q.poll()); // pear
        System.out.println(q.poll()); // null,因为队列为空
    }
}

实现PriorityQueue的关键在于提供的UserComparator对象，它负责比较两个元素的大小（较小的在前）。UserComparator总是把V开头的号码优先返回，只有在开头相同的时候，才比较号码大小。

上面的UserComparator的比较逻辑其实还是有问题的，它会把A10排在A2的前面，请尝试修复该错误。

小结

PriorityQueue实现了一个优先队列：从队首获取元素时，总是获取优先级最高的元素。

PriorityQueue默认按元素比较的顺序排序（必须实现Comparable接口），也可以通过Comparator自定义排序算法（元素就不必实现Comparable接口）

使用Deque

Java集合提供了接口Deque来实现一个双端队列，它的功能是：

• 既可以添加到队尾，也可以添加到队首；
• 既可以从队首获取，又可以从队尾获取。

我们来比较一下Queue和Deque出队和入队的方法：

	Queue	Deque
添加元素到队尾	add(E e) / offer(E e)	addLast(E e) / offerLast(E e)
取队首元素并删除	E remove() / E poll()	E removeFirst() / E pollFirst()
取队首元素但不删除	E element() / E peek()	E getFirst() / E peekFirst()
添加元素到队首	无	addFirst(E e) / offerFirst(E e)
取队尾元素并删除	无	E removeLast() / E pollLast()
取队尾元素但不删除	无	E getLast() / E peekLast()

对于添加元素到队尾的操作，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()：

public class Main {
    public static void main(String[] args) {
        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
    }
}

小结

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

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