-
定義
僅可以在尾端(棧頂)進行插入和刪除的線性表串稀，稱為棧粥庄。
-
特點
棧擁有棧底和棧頂岖瑰，只許在棧頂就行插入和刪除操作叛买，棧內元素進出的原則為“LIFO-后進先出”。
插入蹋订，也可稱作進棧（即push操作）;
刪除率挣，也稱出棧（即pop操作）；
只可以查看棧頂元素（及peek操作）露戒；
-
應用
1.瀏覽器瀏覽記錄的前進與后退椒功；
2.計算機內部的調用棧捶箱；
當調用方法 meetA() 后，計算機將為 meetA() 方法分配一塊內存后动漾，打印1丁屎，執(zhí)行2后，在 meetA()內存的基礎上谦炬，重新分配一塊內存悦屏，打印3，后釋放執(zhí)行2分配的內存键思，接著打印4，執(zhí)行5甫贯，在 meetA()內存的基礎上吼鳞，在重新分配一塊內存（這時meetB調用而產生的內存，已經不再了）叫搁，打印6后赔桌，釋放執(zhí)行5分配的內存，接著重新回到meetA執(zhí)行完畢渴逻，釋放分配的內存疾党。這個過程就是調用棧。
func meetA(_ name: String) {
//1
print("hello, \(name)!")
//2
meetB(name)
//4
print("time to say bye..")
//5
bye()
}
func meetB(_ name: String) {
//3
print("how are you \(name)?")
}
func bye() {
//6
print("Bye Bye!")
}
3.遞歸調用棧惨奕；
遞歸調用棧雪位，類似2中方法調用棧，只不過是方法自己調用自己梨撞。下面舉一個“斐波那契數列”實現的例子（具體請去百度）
func getCount(_ count: Int) -> Int {
//基線條件或遞歸退出條件
if count == 1 {
return 1
}else if count == 0 {
return 0
//分解問題雹洗，直到符合基線條件（縮小范圍）
}else {
return getCount(count - 1) + getCount(count - 2)
}
}
//10個月后共55對兔子
let count = getCount(10)
-
Swift代碼實現
struct Stack<T> {
fileprivate var array: [T] = []
//入棧
mutating func push(_ element: T) {
array.append(element)
}
//出棧
mutating func pop() -> T? {
return array.popLast()
}
//查看棧頂元素
func peek() -> T? {
return array.last
}
//判斷是否為空棧
var isEmpty: Bool {
return array.isEmpty
}
//棧內元素個數
var count: Int {
return array.count
}
}
注意：
通過數組實現棧，當入棧時一定是在數組的末尾插入新的元素卧波，出棧的時候也是一樣的时肿，因為這樣進出棧的操作的時間復雜度為O(1)。如果在數組的頭進行進出棧操作港粱，時間復雜度為O(n)螃成，因為需要將數組內的元素遷前移或后移。
