這期的內(nèi)容有點(diǎn)劍走偏鋒毅该，我們來討論一下棧和隊(duì)列。Swift語言中沒有內(nèi)設(shè)的棧和隊(duì)列潦牛，很多擴(kuò)展庫中使用Generic Type來實(shí)現(xiàn)椏粽疲或是隊(duì)列。正規(guī)的做法使用鏈表來實(shí)現(xiàn)罢绽，這樣可以保證加入和刪除的時(shí)間復(fù)雜度是O(1)畏线。然而筆者覺得最實(shí)用的實(shí)現(xiàn)方法是使用數(shù)組，因?yàn)?Swift 沒有現(xiàn)成的鏈表良价，而數(shù)組又有很多的 API 可以直接使用寝殴，非常方便。本期主要內(nèi)容有：
- 棧和隊(duì)列的基本Swift實(shí)現(xiàn)明垢，以及在iOS開發(fā)中應(yīng)用的實(shí)例
- Facebook棧相關(guān)面試題一道
- 棧和隊(duì)列的互相實(shí)現(xiàn)及其思想
實(shí)現(xiàn)
對(duì)于棧來說蚣常，我們需要了解以下幾點(diǎn)：
- 棧是后進(jìn)先出的結(jié)構(gòu)。你可以理解成有好幾個(gè)盤子要壘成一疊痊银，哪個(gè)盤子最后疊上去抵蚊，下次使用的時(shí)候它就最先被抽出去。
- 在iOS開發(fā)中溯革，如果你要在你的App中添加撤銷操作（比如刪除圖片贞绳，恢復(fù)刪除圖片），那么棧是首選數(shù)據(jù)結(jié)構(gòu)
- 無論在面試還是寫App中致稀，只關(guān)注棧的這幾個(gè)基本操作：push, pop, isEmpty, peek, size冈闭。
protocol Stack {
/// 持有的元素類型
associatedtype Element
/// 是否為空
var isEmpty: Bool { get }
/// 棧的大小
var size: Int { get }
/// 棧頂元素
var peek: Element? { get }
/// 進(jìn)棧
mutating func push(_ newElement: Element)
/// 出棧
mutating func pop() -> Element?
}
struct IntegerStack: Stack {
typealias Element = Int
var isEmpty: Bool { return stack.isEmpty }
var size: Int { return stack.count }
var peek: Element? { return stack.last }
private var stack = [Element]()
func push(_ newElement: Element) {
stack.append(newElement)
}
func pop() -> Element? {
return stack.popLast()
}
}
對(duì)于隊(duì)列來說，我們需要了解以下幾點(diǎn)：
- 隊(duì)列是先進(jìn)先出的結(jié)構(gòu)抖单。這個(gè)正好就像現(xiàn)實(shí)生活中排隊(duì)買票萎攒，誰先來排隊(duì)遇八，誰先買到票。
- iOS開發(fā)中多線程的GCD和NSOperationQueue就是基于隊(duì)列實(shí)現(xiàn)的耍休。
- 關(guān)于隊(duì)列我們只關(guān)注這幾個(gè)操作：enqueue, dequeue, isEmpty, peek, size刃永。
protocol Queue {
/// 持有的元素類型
associatedtype Element
/// 是否為空
var isEmpty: Bool { get }
/// 棧的大小
var size: Int { get }
/// 棧頂元素
var peek: Element? { get }
/// 入隊(duì)
mutating func enqueue(_ newElement: Element)
/// 出隊(duì)
mutating func dequeue() -> Element?
}
struct IntegerQueue: Queue {
typealias Element = Int
var isEmpty: Bool { return left.isEmpty && right.isEmpty }
var size: Int { return left.count + right.count }
var peek: Element? { return left.isEmpty ? right.first : left.last }
private var left = [Element]()
private var right = [Element]()
mutating func enqueue(_ newElement: Element) {
right.append(newElement)
}
mutating func dequeue() -> Element? {
if left.isEmpty {
left = right.reversed()
right.removeAll()
}
return left.popLast()
}
}
實(shí)戰(zhàn)
下面是Facebook一道真實(shí)的面試題。
Given an absolute path for a file (Unix-style), simplify it.
For example,
path = "/home/", => "/home"
path = "/a/./b/../../c/", => "/c"
這道題目一看羊精，這不就是我們平常在terminal里面敲的cd啊pwd之類的嗎斯够，好熟悉啊。
根據(jù)常識(shí)园匹，我們知道以下規(guī)則：
- . 代表當(dāng)前路徑雳刺。比如 /a/. 實(shí)際上就是 /a，無論輸入多少個(gè) . 都返回當(dāng)前目錄
- ..代表上一級(jí)目錄裸违。比如 /a/b/.. 實(shí)際上就是 /a，也就是說先進(jìn)入a目錄本昏，再進(jìn)入其下的b目錄供汛，再返回b目錄的上一層，也就是a目錄涌穆。
然后針對(duì)以上信息怔昨，我們可以得出以下思路：
- 首先輸入是個(gè) String，代表路徑宿稀。輸出要求也是 String, 同樣代表路徑趁舀。
- 我們可以把 input 根據(jù) “/” 符號(hào)去拆分，比如 "/a/b/./../d/" 就拆成了一個(gè)String數(shù)組["a", "b", ".", "..", "d"]
- 創(chuàng)立一個(gè)棧然后遍歷拆分后的 String 數(shù)組祝沸，對(duì)于一般 String 矮烹，直接加入到棧中，對(duì)于 ".." 那我們就對(duì)棧做pop操作罩锐，其他情況不錯(cuò)處理
思路有了奉狈，代碼也就有了
func simplifyPath(path: String) -> String {
// 用數(shù)組來實(shí)現(xiàn)棧的功能
var pathStack = [String]()
// 拆分原路徑
let paths = path.components(separatedBy: "/")
for path in paths {
// 對(duì)于 "." 我們直接跳過
guard path != "." else {
continue
}
// 對(duì)于 ".." 我們使用pop操作
if path == ".." {
if (pathStack.count > 0) {
pathStack.removeLast()
}
// 對(duì)于太注意空數(shù)組的特殊情況
} else if path != "" {
pathStack.append(path)
}
}
// 將棧中的內(nèi)容轉(zhuǎn)化為優(yōu)化后的新路徑
let res = stack.reduce("") { total, dir in "\(total)/\(dir)" }
// 注意空路徑的結(jié)果是 "/"
return res.isEmpty ? "/" : res
}
上面代碼除了完成了基本思路，還考慮了大量的特殊情況涩惑、異常情況仁期。這也是硅谷面試考察的一個(gè)方面：面試者思路的嚴(yán)謹(jǐn)和代碼的風(fēng)格規(guī)范。
隊(duì)列會(huì)在以后講樹遍歷和圖的廣度優(yōu)先遍歷時(shí)大放異彩竭恬，所以本期隊(duì)列先按下不表跛蛋。
轉(zhuǎn)化
處理?xiàng)：完?duì)列問題，最經(jīng)典的一個(gè)思路就是使用兩個(gè)棧/隊(duì)列來解決問題痊硕。也就是說在原棧/隊(duì)列的基礎(chǔ)上赊级，我們用一個(gè)協(xié)助棧/隊(duì)列來幫助我們簡(jiǎn)化算法，這是一種空間換時(shí)間的思路寿桨。比如
用棧來實(shí)現(xiàn)隊(duì)列
struct MyQueue {
var stackA: Stack
var stackB: Stack
var isEmpty: Bool {
return stackA.isEmpty && stackB.isEmpty;
}
var peek: Any? {
get {
shift();
return stackB.peek;
}
}
var size: Int {
get {
return stackA.size + stackB.size
}
}
init() {
stackA = Stack()
stackB = Stack()
}
func enqueue(object: Any) {
stackA.push(object);
}
func dequeue() -> Any? {
shift()
return stackB.pop();
}
fileprivate func shift() {
if stackB.isEmpty {
while !stackA.isEmpty {
stackB.push(stackA.pop()!);
}
}
}
}
用隊(duì)列實(shí)現(xiàn)棧
struct MyStack {
var queueA: Queue
var queueB: Queue
init() {
queueA = Queue()
queueB = Queue()
}
var isEmpty: Bool {
return queueA.isEmpty && queueB.isEmpty
}
var peek: Any? {
get {
shift()
let peekObj = queueA.peek
queueB.enqueue(queueA.dequeue()!)
swap()
return peekObj
}
}
var size: Int {
return queueA.size
}
func push(object: Any) {
queueA.enqueue(object)
}
func pop() -> Any? {
shift()
let popObject = queueA.dequeue()
swap()
return popObject
}
private func shift() {
while queueA.size != 1 {
queueB.enqueue(queueA.dequeue()!)
}
}
private func swap() {
(queueA, queueB) = (queueB, queueA)
}
}
上面兩種實(shí)現(xiàn)方法都是使用兩個(gè)相同的數(shù)據(jù)結(jié)構(gòu)此衅，然后將元素由其中一個(gè)轉(zhuǎn)向另一個(gè)强戴，從而形成一種完全不同的數(shù)據(jù)。
總結(jié)
Swift中棧和隊(duì)列是比較特殊的數(shù)據(jù)結(jié)構(gòu)挡鞍，個(gè)人認(rèn)為最實(shí)用的實(shí)現(xiàn)方法是利用數(shù)組骑歹。雖然它們本身比較抽象，卻是很多復(fù)雜數(shù)據(jù)結(jié)構(gòu)和iOS開發(fā)中的功能模塊的基礎(chǔ)墨微。這也是一個(gè)工程師進(jìn)階之路理應(yīng)熟練掌握的兩種數(shù)據(jù)結(jié)構(gòu)道媚。
