-
定义
仅可以在尾端(栈顶)进行插入和删除的线性表，称为栈。
-
特点
栈拥有栈底和栈顶，只许在栈顶就行插入和删除操作，栈内元素进出的原则为“LIFO-后进先出”。
插入，也可称作进栈（即push操作）;
删除，也称出栈（即pop操作）；
只可以查看栈顶元素（及peek操作）；
-
应用
1.浏览器浏览记录的前进与后退；
2.计算机内部的调用栈；
当调用方法 meetA() 后，计算机将为 meetA() 方法分配一块内存后，打印1，执行2后，在 meetA()内存的基础上，重新分配一块内存，打印3，后释放执行2分配的内存，接着打印4，执行5，在 meetA()内存的基础上，在重新分配一块内存（这时meetB调用而产生的内存，已经不再了），打印6后，释放执行5分配的内存，接着重新回到meetA执行完毕，释放分配的内存。这个过程就是调用栈。
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)，因为需要将数组内的元素迁前移或后移。
网友评论