# Queue - 隊列 Queue 是一個 FIFO（先進先出）的數據結構，并發中使用較多，可以安全地將對象從一個任務傳給另一個任務。 ### 編程實現 ### Java Queue 在 Java 中是 Interface, 一種實現是 LinkedList, LinkedList 向上轉型為 Queue, Queue 通常不能存儲 `null` 元素，否則與 `poll()` 等方法的返回值混淆。 ~~~ Queue<Integer> q = new LinkedList<Integer>(); int qLen = q.size(); // get queue length ~~~ #### Methods | 0:0 | Throws exception | Returns special value | |-----|-----|-----| | Insert | add(e) | offer(e) | | Remove | remove() | poll() | | Examine | element() | peek() | 優先考慮右側方法，右側元素不存在時返回 `null`. 判斷非空時使用`isEmpty()`方法，繼承自 Collection. ### Priority Queue - 優先隊列 應用程序常常需要處理帶有優先級的業務，優先級最高的業務首先得到服務。因此優先隊列這種數據結構應運而生。優先隊列中的每個元素都有各自的優先級，優先級最高的元素最先得到服務；優先級相同的元素按照其在優先隊列中的順序得到服務。 優先隊列可以使用數組或鏈表實現，從時間和空間復雜度來說，往往用二叉堆來實現。 ### Java Java 中提供`PriorityQueue`類，該類是 Interface Queue 的另外一種實現，和`LinkedList`的區別主要在于排序行為而不是性能，基于 priority heap 實現，非`synchronized`，故多線程下應使用`PriorityBlockingQueue`. 默認為自然序（小根堆），需要其他排序方式可自行實現`Comparator`接口，選用合適的構造器初始化。使用迭代器遍歷時不保證有序，有序訪問時需要使用`Arrays.sort(pq.toArray())`. 不同方法的時間復雜度： - enqueuing and dequeuing: `offer`, `poll`, `remove()` and `add` - O(logn)O(\log n)O(logn) - Object: `remove(Object)` and `contains(Object)` - O(n)O(n)O(n) - retrieval: `peek`, `element`, and `size` - O(1)O(1)O(1). ### Deque - 雙端隊列 雙端隊列（deque，全名double-ended queue）可以讓你在任何一端添加或者移除元素，因此它是一種具有隊列和棧性質的數據結構。 ### Java Java 在1.6之后提供了 Deque 接口，既可使用`ArrayDeque`（數組）來實現，也可以使用`LinkedList`（鏈表）來實現。前者是一個數組外加首尾索引，后者是雙向鏈表。 ~~~ Deque<Integer> deque = new ArrayDeque<Integer>(); ~~~ #### Methods <table class="calibre19"><tbody class="calibre23"><tr class="calibre21"><td class="calibre24"/> <td colspan="2" class="calibre24">First Element (Head)</td> <td colspan="2" class="calibre24">Last Element (Tail)</td> </tr><tr class="calibre25"><td class="calibre24"/> <td class="calibre24">Throws exception</td> <td class="calibre24">Special value</td> <td class="calibre24">Throws exception</td> <td class="calibre24">Special value</td> </tr><tr class="calibre21"><td class="calibre24">Insert</td> <td class="calibre24">`addFirst(e)`</td> <td class="calibre24">`offerFirst(e)`</td> <td class="calibre24">`addLast(e)`</td> <td class="calibre24">`offerLast(e)`</td> </tr><tr class="calibre25"><td class="calibre24">Remove</td> <td class="calibre24">`removeFirst()`</td> <td class="calibre24">`pollFirst()`</td> <td class="calibre24">`removeLast()`</td> <td class="calibre24">`pollLast()`</td> </tr><tr class="calibre21"><td class="calibre24">Examine</td> <td class="calibre24">`getFirst()`</td> <td class="calibre24">`peekFirst()`</td> <td class="calibre24">`getLast()`</td> <td class="calibre24">`peekLast()`</td> </tr></tbody></table> 其中`offerLast`和 Queue 中的`offer`功能相同，都是從尾部插入。 ### Reference - [優先佇列 - 維基百科，自由的百科全書](http://zh.wikipedia.org/zh/%E5%84%AA%E5%85%88%E4%BD%87%E5%88%97) - [雙端隊列 - 維基百科，自由的百科全書](https://zh.wikipedia.org/wiki/%E5%8F%8C%E7%AB%AF%E9%98%9F%E5%88%97)