参考链接
栈（stack）是限制插入和删除只能在一个位置上进行的线性表，该位置在表的末端，叫做栈顶。
- 添加元素只能在尾节点后添加，删除元素只能删除尾节点，查看节点也只能查看尾节点。
- 添加、删除、查看依次为入栈（push）、出栈（pop）、栈顶节点（top）。
- 形象的说，栈是一个先进后出（LIFO）表，先进去的节点要等到后边进去的节点出来才能出来。
如图1，是一个栈的形象图，top指针指向的是栈顶节点，所以我们可以通过top访问到2节点，但是0和1节点由于先于2进入这个表，所以是不可见的。如果把0节点当做头节点，2节点当做尾节点，那么栈限制了访问权限，只可以访问尾节点。
img
如图2，当添加一个节点3的时候，只能在栈顶节点，也就是尾节点后添加，这样3节点变成了栈顶，2节点变成了不可见节点，访问的时候只能访问到3节点。入栈时限制了插入地址，只能在栈顶添加节点。
img
当我们执行出栈的命令时，图2的栈顶元素是3节点，删除的时候只能允许删除栈顶的元素，这样子3节点被删除，top指向删除后的栈顶2节点，如图3所示。
img
栈有两种实现结构，一种是顺序存储结构，也就是利用数组实现，一种是链式存储结构，可以用单链表实现。
代码如下：
/// 用数组实现的栈
public class YYStack<T> {
private var container = [T]()
public var count: Int { container.count }
public var isEmpty: Bool { container.isEmpty }
public func push(_ node: T) {
container.append(node)
}
public func pop() -> T? {
container.popLast()
}
public func top() -> T? {
container.last
}
public func bottom() -> T? {
container.first
}
public func cleanup() {
container.removeAll()
}
}
/// 用链表实现的栈
public class YYStack2<T> {
private var container = YYList<T>()
public var count: Int { container.length }
public var isEmpty: Bool { container.isEmpty }
public func push(_ node: T) {
container.append(node)
}
public func pop() -> T? {
container.popLast()
}
public func top() -> T? {
container.tail?.value
}
public func bottom() -> T? {
container.head?.value
}
public func cleanup() {
container.cleanup()
}
}
栈的应用
编译器调用函数就用了栈结构，当第一个函数还没执行完毕，调用第二个函数的时候，编译器就会把第一个函数压栈，第二个函数调用完毕的时候，就会取栈顶函数，也就是第一个函数继续执行。
