数据结构和算法(三) - 栈

堆栈数据结构在概念上与物理的堆栈相同。将元素添加到堆栈时，将其放在堆栈顶部。从堆栈中删除元素时，始终会删除最顶层的元素。堆栈很有用，而且非常简单。构建堆栈的主要目标是强制您访问数据的方式。

堆栈只有两个基本操作：
push - 将一个元素添加到堆栈顶部
pop - 删除堆栈的顶部元素

这意味着您只能从数据结构的一侧添加或删除元素。 在计算机科学中，堆栈被称为LIFO（后进先出）数据结构。 最后被push的元素是第一个被pop的元素。

iOS使用导航堆栈将视图控制器推入和移出视图。
内存分配使用体系结构级别的堆栈。 还使用堆栈管理局部变量的内存。
搜索和征服算法，例如找出迷宫中的路径，使用堆栈来促进回溯。

定义栈数据结构

public struct Stack<Element> {
    
    private var storage: [Element] = []
 
    public mutating func push(_ element: Element) {
        storage.append(element)
    }
    
    @discardableResult
    public mutating func pop() -> Element? {
        // 这里的popLast返回的是一个可选值, 如果Stack为空, 则返回的是一个nil
        // popLast 和 removeLast 都是移除最后一个元素并返回该元素, 但是removeLast 返回的不是可选值, 如果Stack为空时, 调用removeLast, 则会造成crash
        return storage.popLast()        
    }
}

自定义打印

extension Stack: CustomStringConvertible {
    
    public var description: String {
        
        let topDivider = "----top----\n"
        let bottomDivider = "\n-----------"
        
        let stackElements = storage
            .map { "\($0)" }
            .reversed()
            .joined(separator: "\n")
        return topDivider + stackElements + bottomDivider
    }
    
}

playground 输入

 var stack = Stack<Int>()
    stack.push(1)
    stack.push(2)
    stack.push(3)
    stack.push(4)
    
    print(stack)
    
    if let poppedElement = stack.pop() {
        assert(4 == poppedElement)
        print("Popped: \(poppedElement)")
    }

输出

----top----
4
3
2
1
-----------
Popped: 4

Stack 是相对简单的数据结构, 既然有入栈和出栈的操作, 也因该添加一个查看栈顶数据的操作

// 查看栈顶的元素
    public func peek() -> Element? {
        return storage.last
    }
    
    public var isEmpty: Bool {
        return peek() == nil
    }

在链表的操作中, 让链表继承了swift的集合协议来更方便的操作链表, 但是对于Stack来说, 不适合使用swift集合协议, 对于Stack 来说, 主要是现实数据的访问, 我们只在栈顶对数据进行添加和删除, 而Collection 协议是可以在任意的位置进行元素的操作, 因此不适合Stack.

但是可以将数组转化为栈, 确保数组的访问顺序.

 public init(_ elements: [Element]) {
        storage = elements
    }

提供这样一个初始化方法, 把一个数组转化为栈

    let array = ["A", "B", "C", "D"]
    var stack = Stack(array)
    print(stack)
    stack.pop()

Stack(array) 因为swift 有自动推断, 会根据array 中的元素类型推断为String, 而不需要Stack<String> 来声明类型

也可以实现ExpressibleByArrayLiteral协议, 使用数组来初始化Stack

extension Stack: ExpressibleByArrayLiteral {
    public init(arrayLiteral elements: Element...) {
        storage = elements
    }
}

playground 输入

 var stack: Stack = [1.0, 2.0, 3.0, 4.0]
 print(stack)