Swift数据结构篇之 Queue

发表于 | 分类于 |

队列，又称为伫列（queue），是先进先出（FIFO, First-In-First-Out）的线性表。在具体应用中通常用链表或者数组来实现。队列只允许在后端（称为rear）进行插入操作，在前端（称为front）进行删除操作。

队列的操作方式和堆栈类似，唯一的区别在于队列只允许新数据在后端进行添加。

在 Swift 中实现 Queue

与 swift 数据结构之 Stack 相同, 也是采用 struct 来实现。

元素如何存储在栈中

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

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

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

入队、出队

为 Queue 添加两个实例方法来达到入队、出队的目的。入队就是简单的向内部的数组追加元素，出队则是去除内部数组的第一个元素

1
2
3
4
5
6
7
8
9
10
11
12
13
public struct Queue<T> {
    ...
    
    // 入队
    public mutating func enqueue(_ element: T) {
        return elements.append(element)
    }
    // 出队
    public mutating func dequeue() -> T? {
        guard !elements.isEmpty else { return nil }
        return elements.removeFirst()
    }
}

取回队头元素

根据队列的特性，队头元素就是第一个入队的元素，也就是内部数组的第一个元素：

1
2
3
4
5
6
7
public struct Queue<T> {
    ...
    // 取回队头元素
    public func peek() -> T? {
        return elements.first
    }
}

队列元素个数、队列是否为空

1
2
3
4
5
6
7
8
9
10
11
12
public struct Queue<T> {
    
    ...
    
    public var count: Int {
        return elements.count
    }
    
    public var isEmpty: Bool {
        return elements.isEmpty
    }
}

清空队列

1
2
3
4
5
6
public struct Queue<T> {
    ...
    public mutating func clear() {
        elements.removeAll()
    }
}

初始化 Queue

1
2
3
4
5
6
7
8
9
public struct Queue<T> {
    ...
    // 创建一个空的队列
    public init() {} 
    // 从已有序列创建队列
    public init<S: Sequence>(_ s: S) where S.Iterator.Element == T {
        self.elements.append(contentsOf: s)
    }
}

使用数组字面量初始化

1
2
3
4
5
extension Queue: ExpressibleByArrayLiteral {
    public init(arrayLiteral elements: T...) {
        self.init(elements)
    }
}

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

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

实现 description 和debuDescription

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

遍历

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

通过 subscript 获取队列中的元素

要实现通过 subscript 获取队列中的元素，则需要遵从 Collection协议：

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
extension Queue: Collection {
    
    public func check(index: Int) {
        if index < 0 || index > count {
            fatalError("Index out of range")
        }
    }
    
    public var startIndex: Int {
        return 0
    }
    
    public var endIndex: Int {
        return count - 1
    }
    
    public func index(after i: Int) -> Int {
        return elements.index(after: i)
    }
    
    public subscript(index: Int) -> T {
        get {
            check(index: index)
            return elements[index]
        }
        set {
            check(index: index)
            elements[index] = newValue
        }
    }
}

完整代码

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
import Foundation

public struct Queue<T> {
    private var elements: [T] = []
    
    public init() {}
    
    public init<S: Sequence>(_ s: S) where S.Iterator.Element == T {
        self.elements.append(contentsOf: s)
    }
    
    public mutating func dequeue() -> T? {
        guard !elements.isEmpty else { return nil }
        return elements.removeFirst()
    }
    
    public mutating func enqueue(_ element: T) {
        return elements.append(element)
    }
    
    public func peek() -> T? {
        return elements.first
    }
    
    public mutating func clear() {
        elements.removeAll()
    }
    
    public var count: Int {
        return elements.count
    }
    
    public var isEmpty: Bool {
        return elements.isEmpty
    }
}

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

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

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

extension Queue: Collection {
    public func check(index: Int) {
        if index < 0 || index > count {
            fatalError("Index out of range")
        }
    }

    public var startIndex: Int {
        return 0
    }

    public var endIndex: Int {
        return count - 1
    }

    public func index(after i: Int) -> Int {
        return elements.index(after: i)
    }

    public subscript(index: Int) -> T {
        check(index: index)
        return elements[index]
    }
}