Swift数据结构：堆栈（stack）

堆栈就像一个功能有限的数组，你只能将新元素添加（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堆栈空间会因为资源的消耗而不足。