聲明：算法和數(shù)據(jù)結(jié)構(gòu)的文章均是作者從github上翻譯過來敷搪，為方便大家閱讀雨膨。如果英語(yǔ)閱讀能力強(qiáng)的朋友，可以直接到swift算法俱樂部查看所有原文丢氢，以便快速學(xué)習(xí)傅联。作者同時(shí)也在學(xué)習(xí)中，歡迎交流
堆棧就像是帶有約束的數(shù)組疚察，你只可以從最頂端添加新的元素蒸走，從最頂端開始移除元素，或者查看最頂端的元素稍浆。
為什么要這么設(shè)定呢载碌？實(shí)際上，很多算法都會(huì)出現(xiàn)類似情況衅枫，在某一時(shí)刻你只想添加某些元素到一個(gè)臨時(shí)列表里嫁艇，然后過一會(huì)兒又將它們移除出去。這時(shí)候弦撩，你添加或者移除元素的順序會(huì)影響整個(gè)算法步咪。
堆棧可以提供后進(jìn)先出的順序（LIFO）益楼。它每一次移除的元素猾漫，都是你最后放進(jìn)去的元素。這里有一個(gè)非常類似的數(shù)據(jù)結(jié)構(gòu)感凤，隊(duì)列Queue悯周，屬于先進(jìn)先出的順序（FIFO）。
比如陪竿，我們將一個(gè)數(shù)字放進(jìn)堆棧里禽翼。
stack.push(10)
現(xiàn)在堆棧的內(nèi)容為 [ 10 ]。 我們?cè)俜胚M(jìn)下一個(gè)數(shù)字：
stack.push(3)
現(xiàn)在堆棧的內(nèi)容變?yōu)?[ 10, 3 ]族跛。我們繼續(xù)放入新的數(shù)字：
stack.push(57)
現(xiàn)在堆棧的內(nèi)容變?yōu)椋?0闰挡，3，57］礁哄。這回长酗，我們將堆棧里最頂部的數(shù)字移除：
stack.pop()
這里我們得到的返回值為57，因?yàn)樗俏覀冏詈蠓胚M(jìn)去的數(shù)字⊥┤蓿現(xiàn)在堆棧的內(nèi)容變?yōu)椋?0夺脾，3］。
stack.pop()
這一次我們得到的返回值為3茉继，我們可以繼續(xù)移除堆棧的數(shù)據(jù)劳翰。如果堆棧變?yōu)榭眨瞥匠谭祷亟Y(jié)果為nil馒疹，在一些執(zhí)行語(yǔ)句里面會(huì)返回錯(cuò)誤信息（“堆棧下溢”）佳簸。
在swift中，堆棧很容易創(chuàng)建。簡(jiǎn)單的說它就是對(duì)一個(gè)數(shù)組進(jìn)行包裝生均，讓你能夠從數(shù)組最頂部添加听想，移除，查看數(shù)據(jù)马胧。
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
}
}
需要注意這里的添加功能是將數(shù)據(jù)添加到數(shù)組的最末端汉买，而不是最前端。如果想要在最前端插入數(shù)據(jù)佩脊，是屬于O(n)運(yùn)算蛙粘，相當(dāng)不劃算，因?yàn)樗枰覀儼阉袛?shù)據(jù)都移除出來威彰。但是在最末端添加數(shù)據(jù)就屬于O(1)運(yùn)算出牧，運(yùn)算時(shí)間恒定且與數(shù)組大小無(wú)關(guān)。
關(guān)于堆棧有趣的地方：每一次你調(diào)用一個(gè)方法或者方程歇盼，CPU都會(huì)為你在堆棧上指定一個(gè)返回位置舔痕。當(dāng)方程運(yùn)行結(jié)束的時(shí)候，CPU會(huì)使用剛才的返回位置跳回到剛剛調(diào)用方程的地方豹缀。這就是為什么當(dāng)你同時(shí)調(diào)用太多方程時(shí)伯复，比如說在無(wú)限循環(huán)的遞歸方程里，你會(huì)得到結(jié)果為堆棧溢出的錯(cuò)誤反饋邢笙，因?yàn)檫@時(shí)候CPU已經(jīng)沒有更多的空間來指定更多的返回位置啸如。
