堆栈就像一个功能有限的数组，你只能将新元素添加（push）到堆栈顶部，从堆栈顶部删除（pop）元素，也可以只查看而不删除（peak）顶部元素。
为什么需要这样的数据结构呢？在很多算法中，在某些时刻需要临时将对象添加到临时列表中，然后在以后再次将它们从此列表中删除，通常，添加和删除这些对象的顺序很重要，比如像函数的参数传递。
堆栈作为LIFO（后进先出），最后压栈的数可以通过pop（）弹出，堆栈跟队列（queue）是非常相似，队列是FIFO（先进先出），下章再做介绍。
堆栈的演示：首先让我们添加（push）一个值
stack.push(1)
这个堆栈现在是[ 1 ],接着在添加下一个数
stack.push(3)
现在这个堆栈是[ 1 , 3 ],接着在添加一个数
stack.push(5)
现在这个堆栈是[ 1 , 3 , 5]，接着从这个堆栈中删除一个数
stack.pop()
返回值是5，因为堆栈只能删除顶部数据现在堆栈是[ 1 , 3 ]
对堆栈再进行三次删除pop()，返回值将会是nil，因为堆栈里面已经没有任何数值了，根据你的具体堆栈实现也可以让堆栈为空的状态下使用pop，进行报错处理。
让我们来一起实现堆栈吧，在swift中很容易创建堆栈，它只是一个数组的包装器：
public struct Stack<T> { //泛型，Int,Float,Double...
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 peak: T? {
return array.last
}
}
是不是挺简单的，swift中的关键词flieprivate、mutating是swift结构中的用法，需要修改结构类的属性就必须用mutating显性指出，这涉及到了结构中值复制的操作，想要进一步了解建议去查swift的语法文档。
注意的一点是，堆栈的插入都是从最后插入，如果从堆栈最前面插入将会使得堆栈内部元素进行整体后移，这样的后移时间复制度将会是O(n),直接插入将会是O(1)。
关于堆栈的有趣事实：每次调用函数或方法时，CPU都会将返回地址放在堆栈上。当函数结束时，CPU使用该返回地址跳回调用者。这就是为什么如果你调用太多函数 - 例如在一个永远不会结束的递归函数中 - 将会“堆栈溢出”，因为CPU堆栈空间会因为资源的消耗而不足。
网友评论