Swift数据结构篇之 Stack

栈(英语:stack)又称为栈或堆叠,是计算机科学中一种特殊的串列形式的抽象数据类型,其特殊之处在于只能允许在链表或数组的一端(称为堆栈顶端指针,英语:top)进行加入数据(英语:push)和输出数据(英语:pop)的运算。另外栈也可以用一维数组或链表的形式来完成。堆栈的另外一个相对的操作方式称为队列。

由于堆栈数据结构只允许在一端进行操作,因而按照后进先出(LIFO, Last In First Out)的原理运作。

堆栈数据结构使用两种基本操作:推入(压栈,push)和弹出(弹栈,pop):

  • 推入:将数据放入堆栈的顶端(数组形式或串列形式),堆栈顶端top指针加一
  • 弹出:将顶端数据数据输出(回传),堆栈顶端数据减一。

栈的基本特点:

  • 先入后出,后入先出。
  • 除头尾节点之外,每个元素有一个前驱,一个后继。



堆栈的简单示意图


以上引用自维基百科

在 Swift 中实现 Stack

Swift Standard Library 中,几乎所有的数据结构都是用 struct 来实现的,为什么使用 struct, 可以参考 Why Choose Struct Over Class?。在这里也使用 struct 来实现。

由于栈中的元素可以是任意的,所以这里使用到了泛型。基本结构为:

1
2
3
public struct Stack<T> {
...
}

元素如何存储在栈中

压入栈中的元素如何存储呢?Stack 是我们自定义的一个结构体,需要一个 backing storage 来存储入栈的元素。这里我们使用 Swift 中的 Array来实现。

1
2
3
public struct Stack<T> {
private var elements: [T] = []
}

由于内部储存不需要向外界暴露,所以使用了 private, 其内部存储的元素类型与入栈元素类型保持一致。

压栈、出栈

Stack 添加两个实例方法来达到压栈、出栈的目的。压栈就是简单的向内部的数组追加元素,出栈则是去除内部数组的最后一个元素

1
2
3
4
5
6
7
8
9
10
11
12
public struct Stack<T> {
private var elements: [T] = []
// 压栈
public mutating func push(_ element: T) {
elements.append(element)
}

// 出栈
public mutating func pop() -> T? {
return elements.popLast()
}
}

取回栈顶元素

根据栈的特性,栈顶元素就是最后一个入栈的元素,也就是内部数组的最后一个元素:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public struct Stack<T> {
private var elements: [T] = []

public mutating func push(_ element: T) {
elements.append(element)
}

public mutating func pop() -> T? {
return elements.popLast()
}
// 取回栈顶元素
public func peek() -> T? {
return elements.last
}

栈中元素个数,栈是否为空

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public struct Stack<T> {
private var elements: [T] = []

public mutating func push(_ element: T) {
elements.append(element)
}

public mutating func pop() -> T? {
return elements.popLast()
}

public func peek() -> T? {
return elements.last
}
// 栈是否为空
public var isEmpty: Bool {
return elements.isEmpty
}
// 栈中元素个数
public var count: Int {
return elements.count
}

初始化 Stack

提供一个最基本的构造器

1
public init() {}

其实在 swift 中,编译器默认为 结构体 添加了一个包含包含所有成员的初始化构造器,所有这个我们提供的这个这也可以不写。

如果说我现在有一个序列(Sequence),我想将其中的所有元素按顺序都放到栈中,怎么做呢,像下面这样?

1
2
3
4
5
let aSequence = [1, 2, 3, 4]
var stack = Stack<Int>()
for item in aSequence {
stack.push(item)
}

这样看着很是不舒服,不够简洁。所以可以为Stack添加一个构造器,使其可以接收一个 Sequence 来完成初始化。

1
2
3
public init<S: Sequence>(_ s: S) where S.Iterator.Element == T {
self.elements = Array(s)
}

这里要保证 Sequence 的迭代器的元素类型要和 Stack 中的元素类型要保持一致。

更方便的初始化

如果更加方便的来初始化我们的 Stack 呢?在使用 swift standard library提供的 集合(set) 的时候,可以像下面这样初始化:

1
let set: Set = [1, 2, 3]

等号后面是个 Array, 如何将给定的数组转为了集合呢?通过查看 Set 的定义的发现,其遵从了一个名为 ExpressibleByArrayLiteral 的协议,意思是可用数组字面量表示,需要实现一个初始化方法:

1
public init(arrayLiteral elements: Self.ArrayLiteralElement...)

那是不是我们的 Stack 遵从了该协议后就能使用数组字面量来表示了呢? 答案是肯定的。

1
2
3
4
5
6
extension Stack: ExpressibleByArrayLiteral {

public init(arrayLiteral elements: T...) {
self.init(elements)
}
}

需要将 elements 的类型由 Self.ArrayLiteralElement改为Stack中所用到的类型 T,在调用public init<S: Sequence>(_ s: S) 构造器来完成初始化。

1
let stack: Stack = [1, 2, 3, 4] // 需显示指明 stack 的类型,如不指定则优先推断为 Array

debug

在 OC 中所有的类(除 NSProxy 外)都是 NSObject 的子类, 都遵从了 NSObjectProtocol 协议,所以可以实现一个description 和一个 debugDescription 属性,这两个属性非常有用。但我们的 Stack 并不是继承自 NSObject, 而是一个 struct, 如何实现这两个属性呢?比直接在 Stack 结构体中 直接声明这两个属性更加优雅的方式是:extension 我们的 Stack并遵从CustomStringConvertible, CustomDebugStringConvertible 这两个协议。

1
2
3
4
5
6
7
8
9
extension Stack: CustomStringConvertible, CustomDebugStringConvertible {
public var description: String {
return elements.description
}

public var debugDescription: String {
return elements.debugDescription
}
}

遍历

如何遍历我们的 Stack 实例呢?内部的 Array 对外不可见, 无法直接对其进行遍历。在 swift 标准库这提供了一个 Sequence协议,实现了该协议的实例就具有了可以被遍历的能力。

Sequence 协议非常简单,只需要实现一个方法就可以了。

1
public func makeIterator() -> Self.Iterator

该方法需要返回一个遵从 IteratorProtocol 协议的实例即可。

来看一下 IteratorProtocol 有哪些需要实现的方法或属性。遵从该协议只需要实现一个 next 方法,如下:

1
public mutating func next() -> Self.Element?

下面就来看下如何操作。

  1. 定义一个遵从IteratorProtocol协议的结构体ArrayIterator, 并实现 next方法:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    public struct ArrayIterator<T> : IteratorProtocol {

    init(elements: [T]){
    self.currentElement = elements
    }

    mutating public func next() -> T? {
    if self.currentElement.isEmpty { return nil }
    return self.currentElement.popLast()
    }
    }

    由于我们的堆栈实现使用一个数组作为其内部存储,因此我们将一个名为currentElement的实例变量定义为[T],其中T是在采用ArrayIterator时定义的,因此它将保存传递给初始值设定项的数组。
    然后我们实现next方法,该方法负责返回序列中的下一个元素。 如果我们已经到达数组的末尾,则返回nil。 这将向swift运行时发出信号,表示在for ... in循环中迭代它时没有更多元素可用。

  2. 扩展 Stack 使其遵从 Sequence 协议,并实现 makeIterator:

    1
    2
    3
    4
    5
    extension Stack: Sequence {
    public func makeIterator() -> ArrayIterator<T> {
    return ArrayIterator<T>(elements: self.elements)
    }
    }

代码优化

在上面的遍历中, 我们创建了一个遵从IteratorProtocol协议的结构体ArrayIterator, 来达到遍历的目的。在 swift 标准库中,已经完成了相应的工作,可以省去大量的样板代码。下面介绍三种新类型, 这些类型允许我们优化我们的 Stack,因此它也支持lazy evaluation:

  • AnyIterator - An abstract IteratorProtocol base type. Use as a sequence type associated IteratorProtocol type.
  • AnySequence - Creates a sequence that has the same elements as base. When used below the call to .lazy, it will return a LazySequence type
  • IndexingIterator - An iterator for an arbitrary collection. This is also the default iterator for any collection that doesn’t declare its own.

所以遵从 Sequence 协议的 extension 就可以更新为:

1
2
3
4
5
extension Stack: Sequence {
public func makeIterator() -> AnyIterator<T> {
return AnyIterator(IndexingIterator(_elements: self.elements))
}
}

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
public struct Stack<T> {
private var elements: [T] = []
public init() {}

public init<S: Sequence>(_ s: S) where S.Iterator.Element == T {
self.elements = Array(s)
}

public mutating func pop() -> T? {
return elements.popLast()
}

public mutating func push(_ element: T) {
elements.append(element)
}

public func peek() -> T? {
return elements.last
}

public var isEmpty: Bool {
return elements.isEmpty
}

public var count: Int {
return elements.count
}
}

extension Stack: CustomStringConvertible, CustomDebugStringConvertible {
public var description: String {
return elements.description
}

public var debugDescription: String {
return elements.debugDescription
}

}

extension Stack: ExpressibleByArrayLiteral {

public init(arrayLiteral elements: T...) {
self.init(elements)
}
}

extension Stack: Sequence {
public func makeIterator() -> AnyIterator<T> {
return AnyIterator(IndexingIterator(_elements: self.elements.lazy))
}
}