声明：算法和数据结构的文章均是作者从github上翻译过来，为方便大家阅读。如果英语阅读能力强的朋友，可以直接到swift算法俱乐部查看所有原文，以便快速学习。作者同时也在学习中，欢迎交流
堆栈就像是带有约束的数组，你只可以从最顶端添加新的元素，从最顶端开始移除元素，或者查看最顶端的元素。
为什么要这么设定呢？实际上，很多算法都会出现类似情况，在某一时刻你只想添加某些元素到一个临时列表里，然后过一会儿又将它们移除出去。这时候，你添加或者移除元素的顺序会影响整个算法。
堆栈可以提供后进先出的顺序（LIFO）。它每一次移除的元素，都是你最后放进去的元素。这里有一个非常类似的数据结构，队列Queue，属于先进先出的顺序（FIFO）。
比如，我们将一个数字放进堆栈里。
stack.push(10)
现在堆栈的内容为 [ 10 ]。 我们再放进下一个数字：
stack.push(3)
现在堆栈的内容变为 [ 10, 3 ]。我们继续放入新的数字：
stack.push(57)
现在堆栈的内容变为［10，3，57］。这回，我们将堆栈里最顶部的数字移除：
stack.pop()
这里我们得到的返回值为57，因为它是我们最后放进去的数字。现在堆栈的内容变为［10，3］。
stack.pop()
这一次我们得到的返回值为3，我们可以继续移除堆栈的数据。如果堆栈变为空，移除方程返回结果为nil，在一些执行语句里面会返回错误信息（“堆栈下溢”）。
在swift中，堆栈很容易创建。简单的说它就是对一个数组进行包装，让你能够从数组最顶部添加，移除，查看数据。
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会使用刚才的返回位置跳回到刚刚调用方程的地方。这就是为什么当你同时调用太多方程时，比如说在无限循环的递归方程里，你会得到结果为堆栈溢出的错误反馈，因为这时候CPU已经没有更多的空间来指定更多的返回位置。
网友评论