Swift算法俱乐部中文版 -- 堆栈

堆栈就像一个数组，但功能有限。 你只能在堆栈的顶部添加(push方法，或称为进栈、入栈、压栈)一个新的元素，弹出(pop方法，或称为退栈，出栈)从顶部的元素并删除，或者只查看(peek方法)顶部的元素，而不删除。

你为什么要这样做？ 好吧，在许多算法中，您希望在某个时间点将对象添加到临时列表，然后再次将其从此列表中删除。 通常，添加和删除这些对象的顺序很重要。

堆栈的顺序是先入后出。 你最后一次添加的元素，下一次弹出操作时就会被弹出来。（一个非常相似的数据结构，队列，是先入先出。）

例如，让我们在堆栈上添加一个数字：

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中创建。 它只是一个数组的包装，只是让你push，pop和peek：

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 func peek() -> T? {
        return array.last
    }
}

注意，push将新元素放在数组的尾部，而不是头部。 在数组的头部插入是费时的O（n）操作，因为它要求所有的数组元素在内存中移动。 从尾部添加耗时是O（1）; 每次消耗的时间是一样的，而不管元素的多少。

堆栈的趣事：每次调用函数或方法时，CPU都会将返回地址放在堆栈上。 当函数结束时，CPU使用该返回地址，跳回到调用者。 这就是为什么如果你调用太多的函数 - 例如在一个递归函数，永远不会结束 - 你会得到一个所谓的“堆栈溢出”（即著名的网站 stack overflow），因为CPU堆栈已经耗尽了空间。

作者: Matthijs Hollemans -- Swift算法俱乐部

英文链接:
https://github.com/raywenderlich/swift-algorithm-club/tree/master/Stack