Fork me on GitHub

【译】Swift算法俱乐部-栈

本文是对 Swift Algorithm Club 翻译的一篇文章。
Swift Algorithm Clubraywenderlich.com网站出品的用Swift实现算法和数据结构的开源项目,目前在GitHub上有18000+⭐️,我初略统计了一下,大概有一百左右个的算法和数据结构,基本上常见的都包含了,是iOSer学习算法和数据结构不错的资源。
🐙andyRon/swift-algorithm-club-cn是我对Swift Algorithm Club,边学习边翻译的项目。由于能力有限,如发现错误或翻译不妥,请指正,欢迎pull request。也欢迎有兴趣、有时间的小伙伴一起参与翻译和学习🤓。当然也欢迎加⭐️,🤩🤩🤩🤨🤪。
本文的翻译原文和代码可以查看🐙swift-algorithm-club-cn/Stack


这个话题已经有个辅导文章

栈类似于数组,但是限制了存取操作的灵活性。栈只允许使用者从栈顶 压入(push) 元素;从栈顶 弹出(pop) 元素;取得(peek) 栈顶元素,但不弹出。

这样的限制有什么意义呢?在很多算法的实现中,你可能需要将某些对象放到一个临时的列表中,之后再将其取出。通常加入和取出元素的顺序非常重要。

栈可以保证元素存入和取出的顺序是后进先出(last-in first-out, LIFO)的。栈中弹出的元素总是你最后放进去的那个。另外一个非常类似的数据结构是队列,它是一个先进先出(first-in, first-out, FIFO)的结构。

举例来说,我们先将一个数字压入栈中:

1
stack.push(10)

栈现在是 [10]。压入下一个数字:

1
stack.push(3)

栈现在是 [10, 3]。再压入一个数字:

1
stack.push(57)

栈现在是 [10, 3, 57]。现在把栈顶的数字弹出来:

1
stack.pop()

这行代码返回 57,因为它是我们最后压入的元素。现在栈又变成了 [10, 3]

1
stack.pop()

这行代码返回 3,以此类推。如果栈空了,弹栈操作将返回 nil,在有些实现中,会触发一个 stack underflow 错误消息。

栈在 Swift 中的实现非常容易。只需要包装一下自带的数组,将存取功能限制为 pop、push 和 查看栈的顶部元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public struct Stack<T> {
fileprivate var array = [T]()

public var isEmpty: Bool {
return array.isEmpty
}

public var count: Int {
return array.count
}

public mutating func push(_ element: T) {
array.append(element)
}

public mutating func pop() -> T? {
return array.popLast()
}

public var top: T? {
return array.last
}
}

注意到,压栈操作是将新元素压入数组的尾部,而不是头部。在数组的头部插入元素是一个很耗时的操作,它的时间复杂度为 O(n),因为需要将现有元素往后移位为新元素腾出空间。而在尾部插入元素的时间复杂度为 O(1);无论数组有多少元素,这个操作所消耗的时间都是一个常量。

关于栈的有趣知识:每次你调用函数或方法,CPU都会将函数返回地址压入到运行栈中。当这个函数执行结束的时候,CPU将返回地址从栈中取出,并据此返回到函数被调用的位置。所以,如果不断地调用太多的函数(例如死递归函数),就会得到一个所谓的“栈溢出(stack overflow)” 错误,因为CPU运行栈没有空间了。

作者:Matthijs Hollemans;译者:KSCO
校队:Andy Ron

坚持原创技术分享,您的支持将鼓励我继续创作!
  • 本文标题: 【译】Swift算法俱乐部-栈
  • 本文作者: AndyRon
  • 发布时间: 2018年09月16日 - 00:00
  • 最后更新: 2018年09月28日 - 10:24
  • 本文链接: http://andyron.com/2018/Swift算法俱乐部-栈.html
  • 版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 3.0 许可协议。转载请注明出处!