开发基础随笔之栈Stack-用Swift实现栈

栈是一种特殊的线性表，只能在一端进行操作

• 往栈中添加元素的操作，一般叫做push，入栈
• 往栈中移除元素的操作，一般叫做pop，出栈（只能移除栈顶元素，也叫做：弹出栈顶元素）
• 后进先出的原则，Last In First Out，LIFO
  

栈的接口设计

用Swift定义一个协议Stackable，声明几个栈的常规操作，如果要实现一个栈，遵循Stackable协议，内部自己去实现，一般满足以下几个接口既可以。
关于关联类型associatedtype的使用，可以看这里关联类型 Associated Type
动态数组、链表都能用来实现栈

protocol Stackable {
    associatedtype Element //关联类型（可以理解泛型）
    mutating func push(_ element: Element) //入栈
    mutating func pop() -> Element //出栈
    func size() -> Int //元素的数量
    func top() -> Element //获取栈顶元素
    func isEmpty() -> Bool //是否为空
}

实现一个Stack类，遵循Stackable协议
这里因为编译器会自动处理，其实可以不用写明typealias Element = Int，只要实现协议方法的时候写明是Int就行，编译器会自动关联到需要的类型

class Stack: Stackable {
    //给关联类型设置真实类型
    typealias Element = Int
    
    var elements = [Int]()
    
    func size() -> Int { elements.count }
    
    func push(_ element: Int) { elements.append(element) }
    
    func pop() -> Int { elements.removeLast() }
    
    func top() -> Int { elements.last! }
    
    func isEmpty() -> Bool { elements.isEmpty }
}

var stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
stack.push(4)

let size = stack.size()
print(size) // 4

let top = stack.top()
print(top) // 4

while !stack.isEmpty() {
    print(stack.pop())
}
// 4 3 2 1