-
定義
僅可以在隊首進(jìn)行刪除吨艇，隊尾進(jìn)行插入的線性表晒旅，稱為隊列边坤。
-
特點
先入隊列挺庞，則先刪除（First In First Out），類似Stack
-
應(yīng)用
鍵盤的輸入輸出
廣度優(yōu)先搜索等算法的實現(xiàn)
-
Swift的實現(xiàn)（普通）
struct Queue<T> {
//這里可以用鏈表代替
private var array = Array<T>()
//判空
var isEmpty: Bool {
return array.isEmpty
}
//隊列中元素個數(shù)
var count: Int {
return array.count
}
//查看隊首元素
var front: T? {
return array.first
}
//入隊
mutating func enqueque(_ element: T) {
array.append(element)
}
//出隊
mutating func dequeue() -> T? {
guard !isEmpty else { return nil }
return array.removeFirst()
}
}
現(xiàn)在實現(xiàn)的這個隊列就可以工作了舅踪，但是還有些地方是不太完美的纽甘。
- 1.當(dāng)enqueue(入隊)操作時，因為是將新的元素加到數(shù)組的尾部抽碌，所以入隊的時間復(fù)雜對為O(1)贷腕。
原因：在Swift中，在數(shù)組的后面咬展，會預(yù)留出一些空的位置
var queue = Queue<String>()
queue.enqueque("a")
queue.enqueque("b")
queue.enqueque("c")
//實際在數(shù)組中情況為
["a", "b", "c", **, **, **]
//** 就是預(yù)留出來的內(nèi)存泽裳，以備將來插入新的元素
queue.enqueque("d") 后
// 實際情況為
["a", "b", "c", "d", **, **]
Array的這種機(jī)制也會有問題，因為在數(shù)組的末端只會預(yù)留少量的位置破婆，當(dāng)最后一個預(yù)留的位置也被插入新的元素后涮总，就需要將整個數(shù)組中的元素一起拷貝，到一個新的擁有更多位置的數(shù)組中祷舀，這時的時間復(fù)雜度為O(n)瀑梗，但是這種情況只是偶爾發(fā)生，所以平均的時間復(fù)雜對還是O(1)裳扯。
2.當(dāng)dequeue(出隊)操作時抛丽，因為是將數(shù)組中的第一個元素刪除，當(dāng)刪除第一個元素后饰豺，數(shù)組中剩余的所有元素都需要向前移動一個位置亿鲜，來填充前面的空白，所以這個時候的時間復(fù)雜度為O(n)冤吨，每當(dāng)dequeue一次后蒿柳，時間復(fù)雜度都為O(n)，這種操作效率是很低的漩蟆。
-
Swift的實現(xiàn)（稍高效）
稍稍高效些的隊列的實現(xiàn)辦法有好幾種垒探，比如循環(huán)隊列等，我們介紹一個比循環(huán)隊列實現(xiàn)簡單些的怠李。
- 思路：不再是每出隊一次圾叼，就將數(shù)組中的元素向前移動，而是等到滿足一定條件后捺癞，才統(tǒng)一的向前移動夷蚊。
- 代碼
struct Queue<T> {
private var array = Array<T?>()
///用來標(biāo)記隊列的頭位置
private var headIndex = 0
//判空
var isEmpty: Bool {
return array.isEmpty
}
//隊列中元素個數(shù)
var count: Int {
return array.count
}
//查看隊首元素
var front: T? {
if isEmpty { return nil }
return array[headIndex]
}
//入隊
mutating func enqueque(_ element: T) {
array.append(element)
}
//出隊
mutating func dequeue() -> T? {
//存在隊首元素
guard !isEmpty, let firstElement = array[headIndex] else { return nil }
array[headIndex] = nil
//重新標(biāo)記隊首的位置
headIndex += 1
//達(dá)到條件，刪除前面的空位置翘簇，條件可以按照需要進(jìn)行更改
let percentage = Double(headIndex)/Double(array.count)
if array.count > 20 && percentage > 0.25 {
array.removeFirst(headIndex)
headIndex = 0
}
return firstElement
}
}
-
廣度優(yōu)先搜索
-
尋找大兵瑞恩撬码，從下面的人物關(guān)系圖中，最終找到瑞恩的最短路徑
找瑞恩.png 思路
-- 先找你直接認(rèn)識的朋友中版保，是否有瑞恩呜笑，有查找完成
-- 如果在你直接認(rèn)識的朋友中沒有夫否，則在朋友的朋友中查找，直到找到叫胁，或所有人都找過
-- 關(guān)鍵凰慈，只有你直接認(rèn)識的朋友中找完后，才能去從朋友的朋友中去查找驼鹅，這就需要通過隊列的先進(jìn)先出特性來實現(xiàn)
-- 記錄查找過的人微谓，防止循環(huán)查找
//通過字典(散列)來記錄整張關(guān)系圖
var relationGraph: [String: [String]] = {
var dic: [String: [String]] = ["Me": ["A", "C"]]
dic["A"] = ["B"]
dic["C"] = ["B", "D", "Ryan"]
dic["B"] = ["Ryan"]
dic["D"] = ["Ryan"]
return dic
}()
//創(chuàng)建一個存儲，朋友及朋友的朋友的隊列
var queue = Queue<String>()
//用來記錄已經(jīng)查詢過的人
var checked = [String]()
func find(_ name: String) {
findFromQueue(name)
}
//到朋友隊列中找Ryan
func findFromQueue(_ name: String) {
while queue.count > 0 {
guard let person = queue.dequeue() else {
return print("Can not find \(name)")
}
//如果查過則找下一個
if checked.contains(person) { continue }
//記錄已經(jīng)查詢過的
checked.append(person)
//找到
if person == name {
print("Find \(name)")
break
//未找到
}else {
//將朋友的朋友加入到隊列中
enQueueFriends(person)
}
}
}
//將朋友加入到隊列中
func enQueueFriends(_ name: String) {
guard let friends = relationGraph[name] else { return }
let _ = friends.map {
return queue.enqueque($0)
}
}
- 調(diào)用
//將自己的朋友加入到待查找隊列中
enQueueFriends("Me")
//從自己的朋友及朋友的朋友中尋找Ryan
find("Ryan")
