• 定義

僅可以在隊(duì)首進(jìn)行刪除，隊(duì)尾進(jìn)行插入的線性表，稱為隊(duì)列。

• 特點(diǎn)

先入隊(duì)列，則先刪除（First In First Out），類似Stack

• 應(yīng)用

鍵盤的輸入輸出

廣度優(yōu)先搜索等算法的實(shí)現(xiàn)

• Swift的實(shí)現(xiàn)（普通）

struct Queue<T> {//這里可以用鏈表代替private var array = Array<T>()//判空var isEmpty: Bool {return array.isEmpty}//隊(duì)列中元素個(gè)數(shù)var count: Int {return array.count}//查看隊(duì)首元素var front: T? {return array.first}//入隊(duì)mutating func enqueque(_ element: T) {array.append(element)}//出隊(duì)mutating func dequeue() -> T? {guard !isEmpty else { return nil }return array.removeFirst()} } 復(fù)制代碼

現(xiàn)在實(shí)現(xiàn)的這個(gè)隊(duì)列就可以工作了，但是還有些地方是不太完美的。

• 1.當(dāng)enqueue(入隊(duì))操作時(shí)，因?yàn)槭菍⑿碌脑丶拥綌?shù)組的尾部，所以入隊(duì)的時(shí)間復(fù)雜對(duì)為O(1)。 原因：在Swift中，在數(shù)組的后面，會(huì)預(yù)留出一些空的位置

var queue = Queue<String>() queue.enqueque("a") queue.enqueque("b") queue.enqueque("c") //實(shí)際在數(shù)組中情況為 ["a", "b", "c", **, **, **] //** 就是預(yù)留出來的內(nèi)存，以備將來插入新的元素 queue.enqueque("d") 后 // 實(shí)際情況為 ["a", "b", "c", "d", **, **] 復(fù)制代碼

Array的這種機(jī)制也會(huì)有問題，因?yàn)樵跀?shù)組的末端只會(huì)預(yù)留少量的位置，當(dāng)最后一個(gè)預(yù)留的位置也被插入新的元素后，就需要將整個(gè)數(shù)組中的元素一起拷貝，到一個(gè)新的擁有更多位置的數(shù)組中，這時(shí)的時(shí)間復(fù)雜度為O(n)，但是這種情況只是偶爾發(fā)生，所以平均的時(shí)間復(fù)雜對(duì)還是O(1)。

• 2.當(dāng)dequeue(出隊(duì))操作時(shí)，因?yàn)槭菍?shù)組中的第一個(gè)元素刪除，當(dāng)刪除第一個(gè)元素后，數(shù)組中剩余的所有元素都需要向前移動(dòng)一個(gè)位置，來填充前面的空白，所以這個(gè)時(shí)候的時(shí)間復(fù)雜度為O(n)，每當(dāng)dequeue一次后，時(shí)間復(fù)雜度都為O(n)，這種操作效率是很低的。

• Swift的實(shí)現(xiàn)（稍高效） 稍稍高效些的隊(duì)列的實(shí)現(xiàn)辦法有好幾種，比如循環(huán)隊(duì)列等，我們介紹一個(gè)比循環(huán)隊(duì)列實(shí)現(xiàn)簡(jiǎn)單些的。

• 思路：不再是每出隊(duì)一次，就將數(shù)組中的元素向前移動(dòng)，而是等到滿足一定條件后，才統(tǒng)一的向前移動(dòng)。

• 代碼

struct Queue<T> {private var array = Array<T?>()///用來標(biāo)記隊(duì)列的頭位置private var headIndex = 0//判空var isEmpty: Bool {return array.isEmpty}//隊(duì)列中元素個(gè)數(shù)var count: Int {return array.count}//查看隊(duì)首元素var front: T? {if isEmpty { return nil }return array[headIndex]}//入隊(duì)mutating func enqueque(_ element: T) {array.append(element)}//出隊(duì)mutating func dequeue() -> T? {//存在隊(duì)首元素guard !isEmpty, let firstElement = array[headIndex] else { return nil }array[headIndex] = nil//重新標(biāo)記隊(duì)首的位置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} } 復(fù)制代碼

• 廣度優(yōu)先搜索

• 尋找大兵瑞恩，從下面的人物關(guān)系圖中，最終找到瑞恩的最短路徑

• 思路 -- 先找你直接認(rèn)識(shí)的朋友中，是否有瑞恩，有查找完成 -- 如果在你直接認(rèn)識(shí)的朋友中沒有，則在朋友的朋友中查找，直到找到，或所有人都找過 -- 關(guān)鍵，只有你直接認(rèn)識(shí)的朋友中找完后，才能去從朋友的朋友中去查找，這就需要通過隊(duì)列的先進(jìn)先出特性來實(shí)現(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)建一個(gè)存儲(chǔ)，朋友及朋友的朋友的隊(duì)列var queue = Queue<String>()//用來記錄已經(jīng)查詢過的人var checked = [String]()func find(_ name: String) {findFromQueue(name)}//到朋友隊(duì)列中找Ryanfunc findFromQueue(_ name: String) {while queue.count > 0 {guard let person = queue.dequeue() else {return print("Can not find \(name)")}//如果查過則找下一個(gè)if checked.contains(person) { continue }//記錄已經(jīng)查詢過的checked.append(person)//找到if person == name {print("Find \(name)")break//未找到}else {//將朋友的朋友加入到隊(duì)列中enQueueFriends(person)}}}//將朋友加入到隊(duì)列中func enQueueFriends(_ name: String) {guard let friends = relationGraph[name] else { return }let _ = friends.map {return queue.enqueque($0)}} 復(fù)制代碼

• 調(diào)用

//將自己的朋友加入到待查找隊(duì)列中 enQueueFriends("Me") //從自己的朋友及朋友的朋友中尋找Ryan find("Ryan") 復(fù)制代碼

總結(jié)

以上是生活随笔為你收集整理的Queue(队列)-Swift实现与广度优先搜索应用的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。