什么是棧呢剩胁？
簡(jiǎn)單來說，棧是一種存儲(chǔ)數(shù)據(jù)的格式袱巨，分配內(nèi)存的一種方式阁谆。
類似于線性表(通過pNext指針的方式，指向下一個(gè)元素的地址)將數(shù)據(jù)串聯(lián)起來愉老。在這種內(nèi)存分配模式下场绿，只允許在一端（棧頂）進(jìn)行插入和刪除元素，因此嫉入，數(shù)據(jù)具備先進(jìn)后出的狀態(tài)焰盗。
如圖
我們可以把棧看做一個(gè)杯子咒林，在不斷向被子里放入比如橘子（??）吧熬拒，想象一下，當(dāng)我們把被子裝滿垫竞，我們想吃橘子的時(shí)候澎粟，是不是只能先拿最上面的，才能接著取下一個(gè)欢瞪，這就是棧的先進(jìn)后出活烙，也只能在杯子口放橘子和拿橘子。
簡(jiǎn)單的棧實(shí)現(xiàn)思路遣鼓。
我們可以把棧啸盏，看做一個(gè)簡(jiǎn)單的對(duì)象Stack（杯子），這個(gè)對(duì)象擁有2個(gè)指針骑祟，一個(gè)始終指向被子最上方的橘子（棧頂指針）回懦，一個(gè)永遠(yuǎn)指向杯底（棧底指針），并且有一些基本功能次企。比如：
- 初始化一個(gè)空棧
init - 判斷棧是否為空
empty - 插入一份數(shù)據(jù)
push - 刪除一份數(shù)據(jù)
pop - 遍歷所有數(shù)據(jù)
enumerateObjects
以下我們采用swift語言簡(jiǎn)單實(shí)現(xiàn)這些功能怯晕。首先我們打開Xcode新建命令行工程捅厂，語言選擇swift费坊，新建一個(gè)類，繼承自NSObject殖氏，命名為Stack,并且添加其棧頂和棧底指針蛉谜，和其基本的5個(gè)函數(shù)稚晚。
棧中的元素是以鏈表結(jié)構(gòu)相鏈接下一個(gè)數(shù)據(jù)，為了便于操作型诚，我們會(huì)在棧初始化的時(shí)候客燕，創(chuàng)建一個(gè)空的節(jié)點(diǎn)（頭節(jié)點(diǎn)），然后讓棧頂和棧底指針指向該節(jié)點(diǎn)狰贯，實(shí)現(xiàn)一個(gè)空棧的創(chuàng)建也搓。
在實(shí)現(xiàn)空棧創(chuàng)建之前赏廓，我們還需要定義棧中的元素對(duì)象，由于采用鏈表結(jié)構(gòu)傍妒，如圖tu.001.jpeg幔摸，棧中元素存在一個(gè)數(shù)據(jù)域（存放數(shù)據(jù)）和指針域（指向下一個(gè)對(duì)象的地址）相鏈接。
//棧元素對(duì)象
class Element: NSObject {
//數(shù)據(jù)域 存放數(shù)據(jù)
var data : NSObject?
//節(jié)點(diǎn)域 指向下一個(gè)元素的指針
var pNext : Element?
}
接下來實(shí)現(xiàn)空棧的創(chuàng)建颤练，重寫Stack類的init方法
override init() {
//創(chuàng)建頭節(jié)點(diǎn)既忆。便于操作棧
let elment = Element()
//將棧低指針指向該節(jié)點(diǎn)
bottom = elment
//由于是空棧，所以此時(shí)嗦玖，棧頂和棧低指針同時(shí)指向該節(jié)點(diǎn)
top = bottom
}
緊接著我們依次實(shí)現(xiàn)上面我們提到的基本功能
Stack class code
class Stack: NSObject {
var top : Element! //棧頂指針
var bottom : Element! //棧底指針患雇，永遠(yuǎn)指向一個(gè)不用的元素
override init() {
//創(chuàng)建頭節(jié)點(diǎn)。便于操作棧
let elment = Element()
//將棧低指針指向該節(jié)點(diǎn)
bottom = elment
//由于是空棧宇挫，所以此時(shí)苛吱，棧頂和棧低指針同時(shí)指向該節(jié)點(diǎn)
top = bottom
}
//棧是否是否為空
func empty() -> Bool {
//如果 棧頂指針和棧低指針同時(shí)指向同一個(gè)元素（即頭節(jié)點(diǎn)），那么這是一個(gè)空棧
if top.isEqual(bottom) {
return true
}
return false
}
//插入數(shù)據(jù)
func push(value:NSObject){
//首先創(chuàng)建要插入的節(jié)點(diǎn)元素
let element = Element()
element.data = value
//緊接著將元素加到棧頂器瘪，首先使得該元素的下一個(gè)pNext指向棧頂對(duì)象
element.pNext = top
//接著將最新的元素 設(shè)為棧頂元素
top = element
}
//刪除數(shù)據(jù),即只刪除棧的最上方的元素
//swift自動(dòng)釋放機(jī)制翠储，只需要將棧頂指針下移即可
func pop() -> NSObject? {
if !empty() {
let elemet = top
top = top.pNext
//返回刪除的元素
return elemet
}
return nil
}
//遍歷數(shù)據(jù)，這里只作簡(jiǎn)單的輸出
func enumerateObjects() {
//這里只做簡(jiǎn)單的遍歷輸出
//取一個(gè)臨時(shí)的指針娱局，找到棧頂指針彰亥，不斷下移實(shí)現(xiàn)輸出
var element = top
while !(element?.isEqual(bottom))! {
print("元素的值為\(element?.data!)")
element = element?.pNext
}
}
}
至此，我們簡(jiǎn)單的棧的功能就實(shí)現(xiàn)啦衰齐，你可以嘗試創(chuàng)建一個(gè)棧，插入和刪除元素試試哦继阻。
