無論您是排隊(duì)購買自己喜歡的電影的門票，還是等待打印機(jī)打印出您的文件，隊(duì)列都無處不在豺鼻。隊(duì)列使用先進(jìn)先出(FIFO)順序耽梅，這意味著入隊(duì)的第一個(gè)元素將是第一個(gè)出列的元素除盏。這與Stack整好相反.
/**
* 該協(xié)議描述了常用的隊(duì)列操作
* enqueue：在隊(duì)列后面插入一個(gè)元素叉橱。 如果操作成功，則返回true者蠕。
* dequeue：刪除隊(duì)列前面的元素并將其返回窃祝。
* isEmpty：檢查隊(duì)列是否為空。
* peek：返回隊(duì)列前面的元素踱侣。
*/
public protocol Queue {
associatedtype Element
mutating func enqueue(_ element: Element) -> Bool
mutating func dequeue() -> Element?
var isEmpty: Bool { get }
var peek: Element? { get }
}
在以下部分中粪小，學(xué)習(xí)以四種不同的方式創(chuàng)建隊(duì)列：
- 使用數(shù)組
- 使用雙向鏈表
- 使用環(huán)形緩沖
- 使用兩個(gè)堆棧
Swift標(biāo)準(zhǔn)庫帶有核心集高度優(yōu)化的原始數(shù)據(jù)結(jié)構(gòu)，您可以使用它們來構(gòu)建更高級別的抽象抡句。 其中之一是Array探膊，一種存儲(chǔ)連續(xù)的有序元素列表的數(shù)據(jù)結(jié)構(gòu)。 在本節(jié)中待榔，您將使用數(shù)組來創(chuàng)建隊(duì)列逞壁。
1. 使用數(shù)組創(chuàng)建隊(duì)列
public struct QueueArray<T>: Queue {
private var array: [T] = []
public init() {}
}
接下來實(shí)現(xiàn)Queue協(xié)議
// 1 判斷隊(duì)列是否為空
public var isEmpty: Bool {
return array.isEmpty
}
// 2 返回隊(duì)列最前面一個(gè)元素
public var peek: T? {
return array.first
}
Enqueue
添加一個(gè)元素到隊(duì)列
public mutating func enqueue(_ element: T) -> Bool {
array.append(element)
return true
}
無論數(shù)組的大小如何，對元素進(jìn)行排隊(duì)都是O（1）操作锐锣。
在上面的示例中腌闯，注意一旦添加Mic，該數(shù)組有兩個(gè)空格刺下。
添加多個(gè)元素后，數(shù)組最終將滿稽荧。 如果要使用多于分配的空間橘茉，則必須調(diào)整陣列大小以增加空間。
調(diào)整大小是O（n）操作姨丈。 調(diào)整大小需要數(shù)組分配新內(nèi)存并將所有現(xiàn)有數(shù)據(jù)復(fù)制到新數(shù)組畅卓。 由于這種情況不常發(fā)生（由于每次都會(huì)增加一倍），復(fù)雜性仍然可以成為一個(gè)轉(zhuǎn)化為O（1）的復(fù)雜化蟋恬。
Dequeue
從隊(duì)列中刪除前面的元素
public mutating func dequeue() -> T? {
return isEmpty ? nil : array.removeFirst()
}
如果隊(duì)列為空翁潘，則dequeue只返回nil。 如果沒有歼争，它將從數(shù)組前面刪除元素并返回刪除的元素
如上圖所示從隊(duì)列前面刪除元素是O（n）操作拜马。 要出列，請從數(shù)組的開頭刪除該元素沐绒。 這始終是線性時(shí)間操作俩莽，因?yàn)樗髷?shù)組中的所有剩余元素在內(nèi)存中移位。
接下來就要驗(yàn)證一下使用數(shù)組來創(chuàng)建的隊(duì)列了, 為了方便調(diào)試打印數(shù)據(jù), 首先實(shí)現(xiàn)一下CustomStringConvertible協(xié)議
extension QueueArray: CustomStringConvertible {
public var description: String {
return array.description
}
}
添加一下代碼在playground中
var queue = QueueArray<String>()
queue.enqueue("Ray")
queue.enqueue("Brian")
queue.enqueue("Eric")
queue.dequeue()
queue
queue.peek
這段代碼將Ray乔遮，Brian和Eric放入隊(duì)列中扮超，然后刪除了Ray, 并查看了Brian，但沒有刪除它。
以下是基于隊(duì)列實(shí)現(xiàn)的算法和存儲(chǔ)復(fù)雜性的總結(jié)出刷。 除了dequeue（）需要線性時(shí)間之外璧疗，大多數(shù)操作都是恒定時(shí)間。 存儲(chǔ)空間也是線性的馁龟。
通過利用Swift數(shù)組實(shí)現(xiàn)隊(duì)列是容易的崩侠。 由于O（1）追加操作，入隊(duì)非称ò兀快啦膜。
但是它也存在一些缺點(diǎn)。 從隊(duì)列前面刪除元素可能效率低下淌喻，因?yàn)閯h除會(huì)導(dǎo)致所有元素向前移動(dòng)一個(gè)僧家。 這對非常大的隊(duì)列影響很大。 一旦對列變滿裸删，它就必須調(diào)整大小并且可能有未使用的空間八拱。 這可能會(huì)增加您的內(nèi)存占用。
是否有可能解決這些缺點(diǎn)涯塔？ 讓我們看一下基于鏈表的實(shí)現(xiàn)肌稻，并將其與QueueArray進(jìn)行比較。
2. 使用雙向鏈表創(chuàng)建隊(duì)列
首先實(shí)現(xiàn)一個(gè)雙向鏈表, 之前已經(jīng)實(shí)現(xiàn)了 單鏈表 , 雙向鏈表只是節(jié)點(diǎn)還包含了對前一個(gè)節(jié)點(diǎn)的引用, 具體實(shí)現(xiàn)如下
新建一個(gè)playground, 在source文件中新建DoublyLinkedList.swift 鍵入一下代碼
public class Node<T> {
public var value: T
public var next: Node<T>?
public var previous: Node<T>?
public init(value: T) {
self.value = value
}
}
extension Node: CustomStringConvertible {
public var description: String {
return String(describing: value)
}
}
public class DoublyLinkedList<T> {
private var head: Node<T>?
private var tail: Node<T>?
public init() { }
public var isEmpty: Bool {
return head == nil
}
public var first: Node<T>? {
return head
}
public func append(_ value: T) {
let newNode = Node(value: value)
guard let tailNode = tail else {
head = newNode
tail = newNode
return
}
newNode.previous = tailNode
tailNode.next = newNode
tail = newNode
}
public func remove(_ node: Node<T>) -> T {
let prev = node.previous
let next = node.next
if let prev = prev {
prev.next = next
} else {
head = next
}
next?.previous = prev
if next == nil {
tail = prev
}
node.previous = nil
node.next = nil
return node.value
}
}
extension DoublyLinkedList: CustomStringConvertible {
public var description: String {
var string = ""
var current = head
while let node = current {
string.append("\(node.value) -> ")
current = node.next
}
return string + "end"
}
}
public class LinkedListIterator<T>: IteratorProtocol {
private var current: Node<T>?
init(node: Node<T>?) {
current = node
}
public func next() -> Node<T>? {
defer { current = current?.next }
return current
}
}
extension DoublyLinkedList: Sequence {
public func makeIterator() -> LinkedListIterator<T> {
return LinkedListIterator(node: head)
}
}
下面定義一下基于雙向鏈表實(shí)現(xiàn)的隊(duì)列class
public class QueueLinkedList<T>: Queue {
private var list = DoublyLinkedList<T>()
public init() {}
}
QueueLinkedList 遵循Queue協(xié)議, 因此要實(shí)現(xiàn)協(xié)議內(nèi)的方法
Enqueue
添加一個(gè)元素到隊(duì)列
/// 添加到隊(duì)列
public func enqueue(_ element: T) -> Bool {
list.append(element)
return true
}
雙向鏈表將更新其尾節(jié)點(diǎn)對新節(jié)點(diǎn)的上一個(gè)和下一個(gè)的引用匕荸。 這是O（1）操作爹谭。
Dequeue
從隊(duì)列中移除元素
public func dequeue() -> T? {
guard !list.isEmpty, let element = list.first else {
return nil
}
return list.remove(element)
}
此代碼檢查列表是否為空并且隊(duì)列的第一個(gè)元素是否存在。 如果沒有榛搔，則返回nil诺凡。 否則践惑，它會(huì)刪除并返回隊(duì)列前面的元素尔觉。
從列表的前面刪除也是O（1）操作。 與數(shù)組實(shí)現(xiàn)相比，您不必逐個(gè)移動(dòng)元素配深。 相反烈掠，在上圖中，您只需更新鏈表的前兩個(gè)節(jié)點(diǎn)之間的下一個(gè)和前一個(gè)指針。
與數(shù)組的實(shí)現(xiàn)相同, 也可以實(shí)現(xiàn)檢查隊(duì)列狀態(tài)的協(xié)議
/// 查看隊(duì)列的第一個(gè)元素
public var peek: T? {
return list.first?.value
}
/// 判斷隊(duì)列是否為空
public var isEmpty: Bool {
return list.isEmpty
}
測試實(shí)現(xiàn)的隊(duì)列
var queue = QueueLinkedList<String>()
queue.enqueue("Ray")
queue.enqueue("Brian")
queue.enqueue("Eric")
queue.dequeue()
queue
queue.peek
性能總結(jié)
基于雙鏈表的隊(duì)列實(shí)現(xiàn)的算法和存儲(chǔ)復(fù)雜性。
QueueArray的一個(gè)主要問題是將項(xiàng)目出列需要線性時(shí)間。使用鏈表實(shí)現(xiàn)孽鸡，您將其減少為常量操作O（1）奥洼。您需要做的就是更新節(jié)點(diǎn)的上一個(gè)和下一個(gè)指針嚼沿。
QueueLinkedList的主要弱點(diǎn)在表中并不明顯忿檩。盡管有O（1）性能，但它的開銷很高肢藐。每個(gè)元素都必須有額外的存儲(chǔ)空間用于前向和后向引用。而且凑阶，每次創(chuàng)建新元素時(shí)蘸拔，都需要相對昂貴的動(dòng)態(tài)分配。相比之下，QueueArray可以更快地進(jìn)行批量分配。
你能消除分配開銷和主要O（1）隊(duì)列嗎诈闺？如果您不必?fù)?dān)心隊(duì)列長度超出固定大小仁烹，您可以使用不同的方法砰诵，如環(huán)形緩沖區(qū)总寒。例如，你可能有一個(gè)擁有五名玩家的壟斷游戲理肺。您可以使用基于環(huán)形緩沖區(qū)的隊(duì)列來跟蹤接下來的轉(zhuǎn)彎。接下來你將看一下環(huán)形緩沖區(qū)的實(shí)現(xiàn)媳禁。
3. 使用環(huán)形緩沖創(chuàng)建隊(duì)列
在此基礎(chǔ)上來實(shí)現(xiàn)隊(duì)列, 與之前數(shù)組實(shí)現(xiàn)隊(duì)列和鏈表一樣, 同樣需要繼承Queue協(xié)議實(shí)現(xiàn)方法
public struct QueueRingBuffer<T>: Queue {
private var ringBuffer: RingBuffer<T>
public init(count: Int) {
ringBuffer = RingBuffer<T>(count: count)
}
public var isEmpty: Bool {
return ringBuffer.isEmpty
}
public var peek: T? {
return ringBuffer.first
}
public mutating func enqueue(_ element: T) -> Bool {
return ringBuffer.write(element)
}
public mutating func dequeue() -> T? {
return isEmpty ? nil : ringBuffer.read()
}
}
基于環(huán)形緩沖區(qū)的隊(duì)列與鏈表實(shí)現(xiàn)具有相同的入隊(duì)和出隊(duì)時(shí)間復(fù)雜度。 唯一的區(qū)別是空間復(fù)雜性防嗡。 環(huán)形緩沖區(qū)具有固定大小，這意味著入隊(duì)可能會(huì)失敗蚁趁。
到目前為止番官，您已經(jīng)看到了三個(gè)實(shí)現(xiàn)，一個(gè)簡單的數(shù)組钢属，一個(gè)雙向鏈表和一個(gè)環(huán)形緩沖區(qū)徘熔。 雖然它們看起來非常有用，但接下來您將看到使用兩個(gè)堆棧實(shí)現(xiàn)的隊(duì)列淆党。 您將看到它的空間位置遠(yuǎn)遠(yuǎn)優(yōu)于鏈表酷师。 它也不需要像環(huán)形緩沖區(qū)那樣的固定大小。
4. 使用兩個(gè)堆棧創(chuàng)建隊(duì)列
使用兩個(gè)Stack來實(shí)現(xiàn)隊(duì)列的方式是, 每次入棧時(shí), 把入棧的元素放入RightStack, 每次出棧時(shí), 把RightStack 里的元素翻轉(zhuǎn)之后放入LeftStack, 然后從LeftStack的棧頂移除元素
棧隊(duì)列
public struct QueueStack<T> : Queue {
private var leftStack: [T] = []
private var rightStack: [T] = []
public init() {}
}
實(shí)現(xiàn)Queue里的協(xié)議
// 1 O(1)
public var isEmpty: Bool {
return leftStack.isEmpty && rightStack.isEmpty
}
//2 O(1)
public var peek: T? {
return !leftStack.isEmpty ? leftStack.last : rightStack.first
}
- 判斷隊(duì)列是否為空
- 查看棧頂?shù)脑? 如果leftStack不為空, 則leftStack棧頂?shù)脑匚挥陉?duì)列的前面, 否則, 需要將rightStack反轉(zhuǎn), rightStack的第一個(gè)元素將被至于leftStack的棧頂
Enqueue
public mutating func enqueue(_ element: T) -> Bool {
rightStack.append(element)
return true
}
這個(gè)和前面的使用數(shù)組實(shí)現(xiàn)隊(duì)列一樣, 簡單的把元素添加到數(shù)組中, O(1)操作
Dequeue
public mutating func dequeue() -> T? {
// 1
if leftStack.isEmpty {
//2
leftStack = rightStack.reversed()
//3
rightStack.removeAll()
}
//4
return leftStack.popLast()
}
- 因?yàn)閘eftStack存儲(chǔ)的數(shù)據(jù), 代表了隊(duì)列的數(shù)據(jù), 所以, 判斷下加leftStack 是否為空, 如果為空, 則讓rightStack 數(shù)據(jù)反轉(zhuǎn), 賦值給leftStack, 然后清空rightStack, 這是在leftStack及stack上, 移除棧頂?shù)臄?shù)據(jù); 如果不為空, 則直接移除棧頂?shù)臄?shù)據(jù)
注意, 這里的返回值是T?, 因?yàn)槿绻鹟eftStack和RightStack如果同時(shí)都沒有數(shù)據(jù)的話, 執(zhí)行了出棧操作, 返回值將會(huì)是nil, 整好利用了可選類型的數(shù)據(jù)特點(diǎn)
var queue = QueueStack<String>()
queue.enqueue("Ray") // true
queue.enqueue("Brian") //true
queue.enqueue("Eric") //true
queue.dequeue() //Ray
queue.peek // Brian
基于雙棧實(shí)現(xiàn)的隊(duì)列的存儲(chǔ)讀取性能, 實(shí)現(xiàn)了入隊(duì)和出隊(duì)都是O(1), 反轉(zhuǎn)數(shù)組是O(n)
與基于數(shù)組的實(shí)現(xiàn)相比宁否，通過利用兩個(gè)堆棧窒升，您可以將dequeue（_ :)轉(zhuǎn)換為分?jǐn)偟腛（1）操作缀遍。
此外慕匠，您的兩個(gè)堆棧實(shí)現(xiàn)是完全動(dòng)態(tài)的，并且沒有基于環(huán)形緩沖區(qū)的隊(duì)列實(shí)現(xiàn)具有的固定大小限制域醇。
最后台谊，它在空間局部性方面勝過鏈表蓉媳。 這是因?yàn)閿?shù)組元素在內(nèi)存塊中彼此相鄰。 因此锅铅，在第一次訪問時(shí)酪呻，大量元素將被加載到緩存中。
