堆棧就像一個(gè)數(shù)組贰拿，但功能有限。 你只能在堆棧的頂部添加(push方法熄云，或稱為進(jìn)棧膨更、入棧、壓棧)一個(gè)新的元素缴允，彈出(pop方法荚守，或稱為退棧，出棧)從頂部的元素并刪除，或者只查看(peek方法)頂部的元素矗漾，而不刪除锈候。
你為什么要這樣做？ 好吧敞贡，在許多算法中泵琳，您希望在某個(gè)時(shí)間點(diǎn)將對(duì)象添加到臨時(shí)列表，然后再次將其從此列表中刪除誊役。 通常获列，添加和刪除這些對(duì)象的順序很重要。
堆棧的順序是先入后出势木。 你最后一次添加的元素蛛倦，下一次彈出操作時(shí)就會(huì)被彈出來。（一個(gè)非常相似的數(shù)據(jù)結(jié)構(gòu)啦桌，隊(duì)列溯壶，是先入先出。）
例如甫男，讓我們?cè)诙褩Ｉ咸砑右粋€(gè)數(shù)字：
stack.push(10)
堆椙腋模現(xiàn)在是[10]。 添加下一個(gè)數(shù)字：
stack.push(3)
堆棸宀担現(xiàn)在是[10又跛，3]。 再添加一個(gè)數(shù)字：
stack.push(57)
堆椚糁危現(xiàn)在是[10慨蓝，3，57]端幼。 讓我們彈出堆棧頂端的數(shù)字：
stack.pop()
這次返回57礼烈，因?yàn)檫@是彈出的是最近添加的數(shù)字。 堆棧又變成了[10婆跑，3]此熬。
stack.pop()
這次返回3，依此類推滑进。 如果堆棧是空的犀忱，出堆棧方法返回nil或者在一些情況下，給它打印一個(gè)錯(cuò)誤消息（“堆棧下溢”）扶关。
堆棧很容易在Swift中創(chuàng)建阴汇。 它只是一個(gè)數(shù)組的包裝，只是讓你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將新元素放在數(shù)組的尾部吉执，而不是頭部。 在數(shù)組的頭部插入是費(fèi)時(shí)的O（n）操作地来，因?yàn)樗笏械臄?shù)組元素在內(nèi)存中移動(dòng)戳玫。 從尾部添加耗時(shí)是O（1）; 每次消耗的時(shí)間是一樣的，而不管元素的多少未斑。
堆棧的趣事：每次調(diào)用函數(shù)或方法時(shí)咕宿，CPU都會(huì)將返回地址放在堆棧上。 當(dāng)函數(shù)結(jié)束時(shí)蜡秽，CPU使用該返回地址府阀，跳回到調(diào)用者。 這就是為什么如果你調(diào)用太多的函數(shù) - 例如在一個(gè)遞歸函數(shù)芽突，永遠(yuǎn)不會(huì)結(jié)束 - 你會(huì)得到一個(gè)所謂的“堆棧溢出”（即著名的網(wǎng)站 stack overflow）试浙，因?yàn)镃PU堆棧已經(jīng)耗盡了空間。
作者: Matthijs Hollemans -- Swift算法俱樂部
英文鏈接:
https://github.com/raywenderlich/swift-algorithm-club/tree/master/Stack
