-
定义
仅可以在队首进行删除，队尾进行插入的线性表，称为队列。
-
特点
先入队列，则先删除（First In First Out），类似Stack
-
应用
键盘的输入输出
广度优先搜索等算法的实现
-
Swift的实现（普通）
struct Queue<T> {
//这里可以用链表代替
private var array = Array<T>()
//判空
var isEmpty: Bool {
return array.isEmpty
}
//队列中元素个数
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()
}
}
现在实现的这个队列就可以工作了，但是还有些地方是不太完美的。
- 1.当enqueue(入队)操作时，因为是将新的元素加到数组的尾部，所以入队的时间复杂对为O(1)。
原因：在Swift中，在数组的后面，会预留出一些空的位置
var queue = Queue<String>()
queue.enqueque("a")
queue.enqueque("b")
queue.enqueque("c")
//实际在数组中情况为
["a", "b", "c", **, **, **]
//** 就是预留出来的内存，以备将来插入新的元素
queue.enqueque("d") 后
// 实际情况为
["a", "b", "c", "d", **, **]
Array的这种机制也会有问题，因为在数组的末端只会预留少量的位置，当最后一个预留的位置也被插入新的元素后，就需要将整个数组中的元素一起拷贝，到一个新的拥有更多位置的数组中，这时的时间复杂度为O(n)，但是这种情况只是偶尔发生，所以平均的时间复杂对还是O(1)。
-
2.当dequeue(出队)操作时，因为是将数组中的第一个元素删除，当删除第一个元素后，数组中剩余的所有元素都需要向前移动一个位置，来填充前面的空白，所以这个时候的时间复杂度为O(n)，每当dequeue一次后，时间复杂度都为O(n)，这种操作效率是很低的。
-
Swift的实现（稍高效）
稍稍高效些的队列的实现办法有好几种，比如循环队列等，我们介绍一个比循环队列实现简单些的。
- 思路：不再是每出队一次，就将数组中的元素向前移动，而是等到满足一定条件后，才统一的向前移动。
- 代码
struct Queue<T> {
private var array = Array<T?>()
///用来标记队列的头位置
private var headIndex = 0
//判空
var isEmpty: Bool {
return array.isEmpty
}
//队列中元素个数
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
//重新标记队首的位置
headIndex += 1
//达到条件，删除前面的空位置，条件可以按照需要进行更改
let percentage = Double(headIndex)/Double(array.count)
if array.count > 20 && percentage > 0.25 {
array.removeFirst(headIndex)
headIndex = 0
}
return firstElement
}
}
-
广度优先搜索
-
寻找大兵瑞恩，从下面的人物关系图中，最终找到瑞恩的最短路径
找瑞恩.png
-
思路
-- 先找你直接认识的朋友中，是否有瑞恩，有查找完成
-- 如果在你直接认识的朋友中没有，则在朋友的朋友中查找，直到找到，或所有人都找过
-- 关键，只有你直接认识的朋友中找完后，才能去从朋友的朋友中去查找，这就需要通过队列的先进先出特性来实现
-- 记录查找过的人，防止循环查找
//通过字典(散列)来记录整张关系图
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
}()
//创建一个存储，朋友及朋友的朋友的队列
var queue = Queue<String>()
//用来记录已经查询过的人
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 }
//记录已经查询过的
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)
}
}
- 调用
//将自己的朋友加入到待查找队列中
enQueueFriends("Me")
//从自己的朋友及朋友的朋友中寻找Ryan
find("Ryan")
网友评论