Queue - 隊列
Queue 是一個 FIFO(First-in First-out, 先進先出)的資料結構,併發(concurrent)中經常使用,可以安全地將對象從一個任務傳給另一個任務。
程式碼實現
Python
Queue 和 Stack 在 Python 中都是用 list
,[]
實現的。 在python 中list是一個dynamic array, 可以通過append
在list的尾部添加元素, 通過pop()
在list的尾部彈出元素實現Stack
的FILO
, 如果是pop(0)
則彈出頭部的元素實現Queue
的FIFO
。
queue = [] # same as list()
size = len(queue)
queue.append(1)
queue.append(2)
queue.pop(0) # return 1
queue[0] # return 2 examine the first element
Methods
\ | methods |
---|---|
Insert | queue.append(e) |
Remove | queue.pop(0) |
Examine | queue[0] |
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 - 優先隊列
應用程式常常需要處理帶有優先級的業務,優先級最高的業務首先得到服務。因此優先隊列這種資料結構應運而生。優先隊列中的每個元素都有各自的優先級,優先級最高的元素最先得到服務;優先級相同的元素按照其在優先隊列中的順序得到服務。
優先隊列可以使用陣列或鏈表實現,從時間和空間覆雜度來說,往往用二叉堆(Binary heap)來實現。
Python
Python 中提供heapq
的lib來實現 priority queue. 提供push
和pop
兩個基本操作和heapify
初始化操作.
\ | methods | time complexity |
---|---|---|
enqueue | heapq.push(queue, e) | |
dequeue | heapq.pop(queue) | |
init | heapq.heapify(queue) | |
peek | queue[0] |
Java
Java 中提供PriorityQueue
類,該類是 Interface Queue 的另外一種實現,和LinkedList
的區別主要在於排序行為而不是性能,基於 priority heap 實現,非synchronized
,故多執行緒(Multi-thread)下應使用PriorityBlockingQueue
. 預設為自然序(小根堆),需要其他排序方式可自行實現Comparator
接口,選用合適的構造器初始化。使用叠代器遍歷時不保證有序,有序訪問時需要使用Arrays.sort(pq.toArray())
.
不同方法的時間覆雜度:
- enqueuing and dequeuing:
offer
,poll
,remove()
andadd
- - Object:
remove(Object)
andcontains(Object)
- - retrieval:
peek
,element
, andsize
- .
Deque - 雙端隊列
雙端隊列(deque,全名double-ended queue)可以讓你在任何一端添加或者移除元素,因此它是一種具有隊列和堆疊性質的資料結構。
Python
Python 的list
就可以執行類似於deque
的操作, 但是效率會過於慢。 為了提升數據的處理效率, 一些高效的資料結構放在了collections
中。 在collections
中提供了deque
的類, 如果需要多次對list
執行頭尾元素的操作, 請使用deque
。
dq = collections.deque();
Methods
\ | methods | time complexity |
---|---|---|
enqueue left | dq.appendleft(e) | |
enqueue right | dq.append(e) | |
dequeue left | dq.popleft() | |
dequeue right | dq.pop() | |
peek left | dq[0] | |
peek right | dq[-1] |
Java
Java 在1.6之後提供了 Deque 介面,既可使用ArrayDeque
(陣列)來實現,也可以使用LinkedList
(鏈表)來實現。前者是一個數組外加首尾索引,後者是雙向鏈表。
Deque<Integer> deque = new ArrayDeque<Integer>();
Methods
First Element (Head) | Last Element (Tail) | |||
Throws exception | Special value | Throws exception | Special value | |
Insert | `addFirst(e)` | `offerFirst(e)` | `addLast(e)` | `offerLast(e)` |
Remove | `removeFirst()` | `pollFirst()` | `removeLast()` | `pollLast()` |
Examine | `getFirst()` | `peekFirst()` | `getLast()` | `peekLast()` |
其中offerLast
和 Queue 中的offer
功能相同,都是從尾部插入。