1.8 Java 队列 Queue、双端队列 Deque

优质

小牛编辑

116浏览

2023-12-01

queue

在java5中新增加了java.util.Queue接口，用以支持队列的常见操作。该接口扩展了java.util.Collection接口。除了基本的 Collection 操作外，队列还提供其他的插入、提取和检查操作。每个方法都存在两种形式：一种抛出异常（操作失败时），另一种返回一个特殊值（null 或 false，具体取决于操作）。

    抛出异常   返回特殊值
插入 add(e)     offer(e)
移除 remove()   poll()
检查 element()  peek()

队列通常（但并非一定）以 FIFO（先进先出）的方式排序各个元素。不过优先级队列和 LIFO 队列（或堆栈）例外，前者根据提供的比较器或元素的自然顺序对元素进行排序，后者按 LIFO（后进先出）的方式对元素进行排序。

在 FIFO 队列中，所有的新元素都插入队列的末尾，移除元素从队列头部移除。

Queue使用时要尽量避免Collection的add()和remove()方法，而是要使用offer()来加入元素，使用poll()来获取并移出元素。它们的优点是通过返回值可以判断成功与否，add()和remove()方法在失败的时候会抛出异常。如果要使用前端而不移出该元素，使用element()或者peek()方法。

offer 方法可插入一个元素，否则返回 false。这与 Collection.add 方法不同，该方法只能通过抛出未经检查的异常使添加元素失败。
remove() 和 poll() 方法可移除和返回队列的头。到底从队列中移除哪个元素是队列排序策略的功能，而该策略在各种实现中是不同的。remove() 和 poll() 方法仅在队列为空时其行为有所不同：remove() 方法抛出一个异常，而 poll() 方法则返回 null。
element() 和 peek() 返回，但不移除，队列的头。

Queue 实现通常不允许插入 null 元素，尽管某些实现（如 LinkedList）并不禁止插入 null。即使在允许 null 的实现中，也不应该将 null 插入到 Queue 中，因为 null 也用作 poll 方法的一个特殊返回值，表明队列不包含元素。

值得注意的是LinkedList类实现了Queue接口，因此我们可以把LinkedList当成Queue来用。

import java.util.Queue;    
import java.util.LinkedList;    

public class TestQueue {    
    public static void main(String[] args) {    
        Queue<String> queue = new LinkedList<String>();    
        queue.offer("Hello");    
        queue.offer("World!");    
        queue.offer("你好！");    
        System.out.println(queue.size());    
        String str;    
        while((str=queue.poll())!=null){    
            System.out.print(str);    
        }    
        System.out.println();    
        System.out.println(queue.size());    
    }    
}

Deque

一个线性 collection，支持在两端插入和移除元素。

名称 deque 是“double ended queue（双端队列）”的缩写，通常读为“deck”。大多数 Deque 实现对于它们能够包含的元素数没有固定限制，但此接口既支持有容量限制的双端队列，也支持没有固定大小限制的双端队列。

    抛出异常         返回特殊值       抛出异常        返回特殊值
插入 addFirst(e)     offerFirst(e)   addLast(e)     offerLast(e) 
移除 removeFirst()   pollFirst()     removeLast()   pollLast()
检查 getFirst()      peekFirst()     getLast()      peekLast()

此接口定义在双端队列两端访问元素的方法。提供插入、移除和检查元素的方法。因为此接口继承了队列接口Queue，所以其每种方法也存在两种形式：一种形式在操作失败时抛出异常，另一种形式返回一个特殊值（null 或 false，具体取决于操作）。

a、在将双端队列用作队列时，将得到 FIFO（先进先出）行为。将元素添加到双端队列的末尾，从双端队列的开头移除元素。从 Queue 接口继承的方法完全等效于 Deque 方法，如下表所示：

 queue方法   等效Deque方法
 add(e)     addLast(e)
 offer(e)   offerLast(e)
 remove()  removeFirst()
  poll()    pollFirst()
  element() getFirst()
  peek()    peekFirst()

b、用作 LIFO（后进先出）堆栈。应优先使用此接口而不是遗留 Stack 类。在将双端队列用作堆栈时，元素被推入双端队列的开头并从双端队列开头弹出。堆栈方法完全等效于 Deque 方法，如下表所示：

 堆栈方法   等效Deque方法
 push(e)   addFirst(e)
 pop()     removeFirst(e)
 peek()    peekFirst()