栈(Stack)类似数组,但是个相当内敛的闺秀。一个新元素,只可以在栈顶压(push)进来;要移除元素,也只能弹出(pop)栈顶的那个;访问元素也是一样,只可对顶部的那个元素惊鸿一瞥(peek)。

数据结构:Stack

数据结构:Stack - 敏捷大拇指 - 数据结构:Stack


为什么这样?在许多场合,你需要把东西放在一个临时容器里,稍后又需要一一取出,无论添加还是移除,你非常关心顺序。

栈提供了先进后出的机制保证了一种特别的顺序,类似的,队列( queue)提供了先进先出的机制。

比如,我们想给一个空栈里加个数字:

[Swift] 纯文本查看 复制代码
stack.push(10)


现在的栈是 [ 10 ]。再加一个:

[Swift] 纯文本查看 复制代码
stack.push(3)


现在成了 [ 10, 3 ]。再一个:

[Swift] 纯文本查看 复制代码
stack.push(57)


现在是 [ 10, 3, 57 ]。

数据结构:Stack 2

数据结构:Stack - 敏捷大拇指 - 数据结构:Stack 2


移除一个元素:

[Swift] 纯文本查看 复制代码
stack.pop()


这个方法返回被移除的元素57,只因它是最后被放进栈的。现在栈重新成了 [ 10, 3 ] 。我们继续:

[Swift] 纯文本查看 复制代码
stack.pop()


不出所料,返回了3。

如果栈已经空了,再pop人就会返回nil,也有的实现是直接给你个错误信息(“栈干了”)。

数据结构:Stack 0

数据结构:Stack - 敏捷大拇指 - 数据结构:Stack 0


用Swift实现栈太简单了,只需要简单地包装下Array,只支持上面说的push、pop和peek等方法就好:

[Swift] 纯文本查看 复制代码
public struct Stack<T> {
    fileprivate var array = [T]()
    
    public var isEmpty: Bool {
        return array.isEmpty
    }
    
    public var count: Int {
        return array.count
    }
    
    public mutating func push(_ element: T) {
        array.append(element)
    }
    
    public mutating func pop() -> T? {
        return array.popLast()
    }
    
    public func peek() -> T? {
        return array.last
    }
}


[Swift] 纯文本查看 复制代码
extension Stack: Sequence {
    public func makeIterator() -> AnyIterator<T> {
        var curr = self
        return AnyIterator {
            _ -> T? in
            return curr.pop()
        }
    }
}


注意到push方法是在array的最后追加元素而不是在最前插入。在最前插入有点低效,是个O(n)复杂度的操作,因为那需要内存中数组原来的元素都改变位置。在最后追加则只是常数级O(1)操作,不管数组原来有多少个元素,追加要用的时间几乎一样。

顺便一提的是函数调用栈:每次你调用一个函数或方法,CPU都会在一个栈上保存该函数的地址,函数执行完就可以根据这个地址准确地返回调用的地方。这也就是为什么一个函数如果多次调用自己——极端情况下是无限递归——我们的程序总是崩给我们看,只因为“栈爆了”,CPU用光了自己的空间。

数据结构:Stack 1

数据结构:Stack - 敏捷大拇指 - 数据结构:Stack 1


另外,猿媛们都该知道一个很好的网站:爆栈网(StackOverFlow),除了GitHub,那里是我们的另外一个乐园啊。




原作者: Matthijs Hollemans