/

栈 Stack Data Structure

加入 Swift Algorithm Club /‘ælgə’rɪðəm/,回炉重新学习数据结构与算法。

自己创建的项目:GitHub - imzyf/data-structure-and-algorithm

实现一个 /stæk/,包含 push peek popGenerics 泛型。

stack

非常像一个数组,它包括少量的方法。

  • push 添加一个新元素到栈顶
  • pop 从栈顶移除一个元素
  • peek 查看栈顶的一个元素但是不 pop

A stack gives you a LIFO or last-in first-out order. 栈是后进先出,队列是先进先出。

public struct Stack<Element> {
fileprivate var array: [Element] = []
}

push

push 是在数组的尾部添加元素是以 O(1),如果是在数组最前添加是 O(n) 这是昂贵的。

public mutating func push(_ element: Element) {
array.append(element)
}

因为使用的 struct,修改属性值的方法要加 mutating

pop

想从一个空栈中弹出最后一个元素将返回 nil

public mutating func pop(_ element: Element) {
return array.popLast()
}

peek

pop 有点像,但是并没有移除栈顶的元素。

/// peek 改为更加语义化的 top 只读变量
public var top: T? {
return array.last
}

other

两个其他的常用属性,栈是否为空,栈中元素的个数。

public var isEmpty: Bool {
return array.isEmpty
}

public var count: Int {
return array.count
}

References

– EOF –