Swift 语言没有内设有栈这种数据结构，这里我们利用数组来实现下栈。
栈的特点
应用
在开发应用中，涉及到的添加和删除或者撤销的操作，可以用到栈结构
iOS 中 navigation 对 view controller 的 push 和 pop 的操作也是用到栈的这种结构
局部变量的内存管理也是栈结构
在寻找离开迷宫的路径也是栈的这种结构，比如撤回上一次的决定
我们插入点 Swift 的基础知识
值类型和引用类型
Swift 中结构体和类都可以用来自定义类型，在 Objective-C 编程中，结构体和类的区别很大，该用结构体还是类，往往一眼就能做出决定。但是，在 Swift 中，结构体不再像之前那么单纯，它里面增添了很多面向对象的特性，从而使得结构体可以执行一些原本只有类才能执行的任务。官方的建议：
如果类型需要传值，就用结构体。这样可以保证赋值或者传参时，类型是复制的
如果类型不支持或者没有必要支持子类继承，就用结构体
如果类型所要实现的功能只是简单的存储数据，就考虑用结构体
如果需要保证数据独立，就用结构体，因为结构体属于值类型，而类属于引用类型
而栈主要用来存储数据，所以我们选择使用结构体
基本实现
/** Swift 实现 栈结构 *///注释1public struct Stack<Element>{ //声明一个泛型数组 private var storage: [Element] = [] public init () { } public init (_ element: [Element]) { storage = element } //注释2 public mutating func push(_ element: Element) { storage.append(element) } //注释3 @discardableResult public mutating func pop() -> Element? { storage.popLast() } public func peek() -> Element? { storage.last } public var isEmpty: Bool { peek() == nil }}
var stack = Stack<Int>()stack.push(1)stack.push(2)stack.push(3)stack.push(4)print(stack)//打印效果：Stack<Int>(elements: [1,2,3,4])
复制代码
1>Swift 中声明泛型的语法，在类型名后面紧跟一对尖括号(<>)，尖括号内部使用特定的符号作为类型占位符。占位符可以是任何字母，也可以是字符串，在 Swift 中一般使用一个大写的字母 T 作为类型占位符
2>结构体是值类型，值类型的方法是不能对自身(self)进行修改的，如果非要对自身(self)进行修改，就必须用关键字 mutating 进行标记
3>@discardableResult 是 Swift 中的一个特性，用于抑制函数或者方法返回值被调用而没有使用其结果时的警告
扩展
1.遵循 CustomStringConvertible 协议，让打印 Stack 的 log 简洁，美观。 将数组里面的元素按照堆栈的样式打印出来。 由于你是将元素添加到数组的尾部，所以首先要做的是反转数组。然后用 joined(separator:) 方法来拼接数组里面的元素，元素之间用 separator 隔开
extension Stack: CustomStringConvertible { public var description: String { //把 storage 数组转成字符串数组，然后反转，最后把元素用换行符拼接起来 """ ---top--- \(storage.map{"\($0)"}.reversed().joined(separator: "\n")) --------- """ }}
let array = ["a","b","c","d"]var stack = Stack(array)print(stack)stack.pop()/*打印效果：---top---dcba---------*/
复制代码
2.在创建 Stack 实例的时候，使用 var stringStack: Stack = Stack() 或者 var intStack = Stack() 语法可能显得太啰嗦，如果希望像数组一样使用 var doubleStack: Stack = [1.0, 2.0, 3.0] 字面量语法，就必须遵守 ExpressibleByArrayLiteral 协议，实现相应的方法：
extension Stack: ExpressibleByArrayLiteral{ public init(arrayLiteral elements: Element...){ storage = elements }}
var stack:Stack = [1.0,2.0,3.0,4.0]print(stack)stack.pop()
复制代码
所以完整的代码：
/** Swift 实现 栈结构 */public struct Stack<Element>{ private var storage: [Element] = [] public init () { } public init (_ element: [Element]) { storage = element } public mutating func push(_ element: Element) { storage.append(element) } @discardableResult public mutating func pop() -> Element? { storage.popLast() } public func peek() -> Element? { storage.last } public var isEmpty: Bool { peek() == nil }}
extension Stack: CustomStringConvertible { public var description: String { //把 storage 数组转成字符串数组，然后反转，最后把元素用换行符拼接起来 """ ---top--- \(storage.map{"\($0)"}.reversed().joined(separator: "\n")) --------- """ }}
extension Stack: ExpressibleByArrayLiteral{ public init(arrayLiteral elements: Element...){ storage = elements }}
复制代码
代码项目地址 Github
题目：
1.反转数组
[1,2,3,4,5] 反转后：[5,4,3,2,1]
代码实现：
let array: [Int] = [1, 2, 3, 4, 5]
// 数组实现 时间复杂度 O(n) 空间复杂度 O(1)func printInReverse(_ array:[Int]){ var currentArray = array if currentArray.count < 2 { print(currentArray.description) } var low = 0 var high = currentArray.count-1 while low < high { (currentArray[low],currentArray[high]) = (currentArray[high],currentArray[low]) low += 1 high -= 1 } print(currentArray.description)}
printInReverse(array)// 输出 [5,4,3,2,1]
复制代码
这个问题用数组就可以解决，但是如果要用栈的结构解决的话，代码如下：
let array: [Int] = [1, 2, 3, 4, 5]// 栈实现func printInReverse2(_ array:[Int]){ var stack = Stack(array) while stack.isEmpty == false { print(stack.pop()!) }}
printInReverse2(array)
复制代码
2.匹配花括号（）
// 1 h((e))llo(world)() // balanced parentheses
// 2 (hello world // unbalanced parentheses
代码实现：
func checkParentheses(_ testString: String) -> Bool{ //判断字符串的长度 if testString.count < 2 { return false } //拆分字符串成字符串数组 let array = testString.map({"\($0)"}) var stack = Stack<String>() for item in array { if item == "(" { stack.push(item) }else if(item == ")") { if let element = stack.peek() { if element == "(" { // 如果匹配，就移除栈顶元素 "(" stack.pop() } }else{ stack.push(item) } }else{ } } // 判断栈是否为空：就是看花括号是否一一匹配了 return stack.isEmpty == true}
let testString1 = "h((e))llo(world)()"print(checkParentheses(testString1)) // true
复制代码
Facebook 的一道面试题：
Given an absolute path for a file (Unix-style), simplify it.
For example:
path = "/home/", => "/home"
path = "/a/./b/../../c/", => "/c"
代码实现：
func simplifyPath(path: String) -> String { // 判断传入的字符 if path.count == 0 { return "" } if path.count == 1 && path == "." { return path } //利用 "/" 拆分原路径 string 成数组 let pathArray = path.split(separator: "/") print(pathArray) // 输出 ["a", ".", "b", "..", "..", "c"] 正式环境可以删掉 // 创建一个 String 类型的栈 var pathStack = Stack<String>() for char in pathArray { switch char { case ".": break case "..": pathStack.pop() default: pathStack.push(String(char)) } } // 判断 Stack 是否为空 if pathStack.isEmpty == true { return "/" }else{ let top = pathStack.peek() return "/" + (top ?? "") }}
let path_test = "/a/./b/../../c/"print(simplifyPath(path: path_test))// 输出: /c
复制代码
其实这道题用数组也是可以实现的，这里就不放代码了，思路都一样。
评论