参考链接

• 基本数据结构：栈（stack）

栈（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()
    }
}

栈的应用

编译器调用函数就用了栈结构，当第一个函数还没执行完毕，调用第二个函数的时候，编译器就会把第一个函数压栈，第二个函数调用完毕的时候，就会取栈顶函数，也就是第一个函数继续执行。