Swift数据结构－堆栈Stack

声明：算法和数据结构的文章均是作者从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已经没有更多的空间来指定更多的返回位置。