写点什么

Swift 算法 - 栈

用户头像
Byte_Panda
关注
发布于: 2021 年 01 月 13 日

Swift 语言没有内设有栈这种数据结构,这里我们利用数组来实现下栈。

栈的特点

  • 后进先出(LIFO: last-in first-out)的结构,最后进栈的元素最先被移出

  • 最主要的操作为 push 和 pop,push 为添加元素到栈的顶部,pop 为移除栈顶部的元素



应用

  • 在开发应用中,涉及到的添加和删除或者撤销的操作,可以用到栈结构

  • iOS 中 navigation 对 view controller 的 push 和 pop 的操作也是用到栈的这种结构

  • 局部变量的内存管理也是栈结构

  • 在寻找离开迷宫的路径也是栈的这种结构,比如撤回上一次的决定

我们插入点 Swift 的基础知识

值类型和引用类型

  • 值类型 在被赋值给另外一个实例或者作为参数传递给函数时,总是被复制的,你修改其中一个的值不会影响另外一个值

  • 引用类型 在被赋值给另外一个实例或者作为参数传递给函数时,不会产生副本,而是创建新的引用。你修改其中一个的值会影响另外一个值。

Swift 中结构体和类都可以用来自定义类型,在 Objective-C 编程中,结构体和类的区别很大,该用结构体还是类,往往一眼就能做出决定。但是,在 Swift 中,结构体不再像之前那么单纯,它里面增添了很多面向对象的特性,从而使得结构体可以执行一些原本只有类才能执行的任务。官方的建议:


  1. 如果类型需要传值,就用结构体。这样可以保证赋值或者传参时,类型是复制的

  2. 如果类型不支持或者没有必要支持子类继承,就用结构体

  3. 如果类型所要实现的功能只是简单的存储数据,就考虑用结构体

  4. 如果需要保证数据独立,就用结构体,因为结构体属于值类型,而类属于引用类型


而栈主要用来存储数据,所以我们选择使用结构体

基本实现

/** 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
复制代码


  1. 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
复制代码


其实这道题用数组也是可以实现的,这里就不放代码了,思路都一样。


发布于: 2021 年 01 月 13 日阅读数: 19
用户头像

Byte_Panda

关注

学而时习之 2017.11.30 加入

iOS开发者

评论

发布
暂无评论
Swift 算法-栈