04.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