使用Swift实现常见的数据结构。


1.动态数组

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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
class ArrayList<T: Equatable> {
// 元素数量(只读)
private(set) var count: Int = 0
// 使用nil作为占位
private var elements: [T?]
// 默认10个元素
private let DEFAULT_CAPACITY = 10
private let ELEMENT_NOT_FOUND = -1

// 构造器, 初始化容量为capaticy的数组
init(_ capaticy: Int) {
let capaticy = capaticy < DEFAULT_CAPACITY ? DEFAULT_CAPACITY : capaticy
elements = [T?](repeating: nil, count: capaticy)
}

// 是否为空
func isEmpty() -> Bool {
return count == 0
}

// 插入元素
func insert(_ item: T, _ index: Int) {
if index < 0 || index > count {
// 越界
fatalError("索引有误, 已经越界")
}
ensureCapacity()
for idx in (index...count).reversed() {
elements[idx + 1] = elements[idx]
}
count += 1
elements[index] = item
}

// 追加元素
func append(_ item: T) {
insert(item, count)
}

// 获取索引所在元素
func get(_ index: Int) -> T {
checkBounds(index)
return elements[index]!
}

// 设置元素
func set(_ item: T, _ index: Int) {
checkBounds(index)
elements[index] = item
}

// 移除元素
func remove(_ index: Int) -> T {
let ele = get(index)
for idx in index..<count {
elements[idx] = elements[idx + 1]
}
elements[count - 1] = nil
count -= 1
return ele
}

// 清空元素
func clear() {
for idx in 0..<count {
elements[idx] = nil
}
count = 0
}

// 是否包含某个元素
func contains(_ item: T) -> Bool {
// item 不可能为nil
return indexOf(item) != ELEMENT_NOT_FOUND
}

// 获取某个元素对应的索引
private func indexOf(_ item: T) -> Int {
// 这里的item不可能为nil
for idx in 0..<count {
if elements[idx]! == item {
return idx
}
}
return ELEMENT_NOT_FOUND
}

// 数组扩容
private func ensureCapacity() {
if count > elements.count >> 1 {
var elements = self.elements
// 扩容1.5倍
let newCapacity = elements.count + elements.count >> 1
self.elements = [T?](repeating: nil, count: newCapacity)
for idx in 0..<count {
self.elements[idx] = elements[idx]
}
}
}

// 索引越界检查
private func checkBounds(_ index: Int) {
if index < 0 || index >= count {
// 越界
fatalError("索引有误, 已经越界")
}
}
}

实现过程中几个需要注意的点:

  1. indexOf()函数中,元素使用==判等,需要遵守Equatable协议
  2. 数组的扩容中,使用位运算符可以避免产生浮点数
  3. 由于Swift中可选类型的存在,可以使用nil来占位。当然,在set()、append()等函数中,由于类型确定也省略了外界传参时对空值的判断

动态数组优化

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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
class OPArrayList<T: Equatable> {
// 元素数量(只读)
private(set) var count: Int = 0
// 使用nil作为占位
private var elements: [T?]
// 首位元素索引
private var frontIndex = 0
// 默认10个元素
private let DEFAULT_CAPACITY = 10
private let ELEMENT_NOT_FOUND = -1

// 构造器, 初始化容量为capaticy的数组
init(_ capaticy: Int) {
let capaticy = capaticy < DEFAULT_CAPACITY ? DEFAULT_CAPACITY : capaticy
elements = [T?](repeating: nil, count: capaticy)
}

// 是否为空
func isEmpty() -> Bool {
return count == 0
}

// 插入元素
func insert(_ item: T, _ index: Int) {
if index < 0 || index > count {
// 越界
fatalError("索引有误, 已经越界")
}
ensureCapacity()
for idx in (index..<count).reversed() {
elements[actualIndex(idx + 1)] = elements[actualIndex(idx)]
}
count += 1
elements[actualIndex(index)] = item
}

// 追加元素
func append(_ item: T) {
insert(item, count)
}

// 获取索引所在元素
func get(_ index: Int) -> T {
checkBounds(index)
return elements[actualIndex(index)]!
}

// 设置元素
func set(_ item: T, _ index: Int) {
checkBounds(index)
elements[actualIndex(index)] = item
}

// 移除元素
func remove(_ index: Int) -> T {
let ele = elements[actualIndex(index)]!
if index == 0 {
elements[frontIndex] = nil
frontIndex += 1
} else {
for idx in index..<count {
elements[actualIndex(idx)] = elements[actualIndex(idx + 1)]
}
elements[actualIndex(count - 1)] = nil
}
count -= 1
return ele
}

// 清空元素
func clear() {
for idx in 0..<count {
elements[actualIndex(idx)] = nil
}
count = 0
}

// 是否包含某个元素
func contains(_ item: T) -> Bool {
// item 不可能为nil
return indexOf(item) != ELEMENT_NOT_FOUND
}

// 获取某个元素对应的索引
private func indexOf(_ item: T) -> Int {
// 这里的item不可能为nil
for idx in 0..<count {
if elements[actualIndex(idx)]! == item {
return idx
}
}
return ELEMENT_NOT_FOUND
}

// 获取真实索引: (frontIndex + index) % elements.count
private func actualIndex(_ idx: Int) -> Int {
return (frontIndex + idx) % elements.count
}

// 数组扩容
private func ensureCapacity() {
if count == elements.count {
var elements = self.elements
// 扩容1.5倍
let newCapacity = elements.count + elements.count >> 1
self.elements = [T?](repeating: nil, count: newCapacity)
for idx in 0..<count {
let index = (frontIndex + idx) % elements.count
self.elements[idx] = elements[index]
}
frontIndex = 0
}
}

// 索引越界检查
private func checkBounds(_ index: Int) {
if index < 0 || index >= count {
// 越界
fatalError("索引有误, 已经越界")
}
}

// 数组内容打印
public func desc() {
var str = "["
for idx in 0..<elements.count {
var a = ", "
if idx == 0 {
a = ""
}
if elements[idx] != nil {
str += "\(a)\(elements[idx]!)"
} else {
str += "\(a)nil"
}
}
str += "], frontIndex = \(frontIndex), count = \(count)"
print(str)
}
}

2.单向链表

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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
class OneWayLinkedList<T: Equatable> {
// 元素没有找到
private let ELEMENT_NOT_FOUND = -1
fileprivate var first: Node<T>?
fileprivate var count: Int = 0

init(_ firstEle: T?) {
if firstEle == nil {
first = nil
} else {
first = Node(ele: firstEle!, next: nil)
count += 1
}
}

// 便利构造
convenience init() {
self.init(nil)
}

// 结点类
fileprivate class Node<T> {
var ele: T
var next: Node<T>?
init(ele: T, next: Node?) {
self.ele = ele
self.next = next
}
}

// 索引所在元素获取
func get(_ index: Int) -> T {
return node(index).ele
}

// 在某索引处插入元素
func insert(_ item: T, _ index: Int) {
if index < 0 || index > count {
// 越界
fatalError("索引有误, 已经越界")
}
if index == 0 {
let prev = first
let newNode = Node(ele: item, next: prev)
first = newNode
} else {
let prev = node(index - 1)
let newNode = Node(ele: item, next: prev.next)
prev.next = newNode
}
count += 1
}

// 追加元素
func append(_ item: T) {
insert(item, count)
}

// 移除某索引的元素
func remove(_ index: Int) {
checkBounds(index)
if index == 0 {
first = first?.next
} else {
let noe = node(index - 1)
noe.next = noe.next?.next
}
count -= 1
}

// 获取某元素所在索引
func indexOf(_ item: T) -> Int {
var node = first
var idx = 0
while node != nil {
if node!.ele == item {
return idx
}
node = node!.next
idx += 1
}
return ELEMENT_NOT_FOUND
}

// 清空所有元素
func clear() {
count = 0
self.first = nil
}

// 打印
func desc() {
var node = first
var str = ""
for idx in 0..<count {
if idx == 0 {
str += "first:\(node!.ele),"
}
if node!.next != nil {
str += " [\(node!.ele), \(node!.next!.ele)]"
} else {
str += " [\(node!.ele), nil]"
}
node = node!.next
if node != nil {
str += ","
}
}
print(str)
}

// 获取索引所在的结点
fileprivate func node(_ index: Int) -> Node<T> {
checkBounds(index)
var node = self.first
for _ in 0..<index {
node = node?.next
}
return node!
}

// 索引越界检查
fileprivate func checkBounds(_ index: Int) {
if index < 0 || index >= count {
// 越界
fatalError("索引有误, 已经越界")
}
}
}

3.单向循环链表

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
class OneWayCircularLinkedList<T: Equatable>: OneWayLinkedList<T> {
override func insert(_ item: T, _ index: Int) {
if index < 0 || index > count {
// 越界
fatalError("索引有误, 已经越界")
}
if index == 0 {
let prev = first
let newNode = Node(ele: item, next: prev)
if prev == nil {
// 只有一个元素
newNode.next = newNode
}
first = newNode
} else {
let prev = node(index - 1)
// 处理添加到最后一个位置
let fir = (index == count) ? first : prev.next
let newNode = Node(ele: item, next: fir)
prev.next = newNode
}
count += 1
}

override func remove(_ index: Int) {
checkBounds(index)
if index == 0 {
let last = node(count - 1)
// 对最后一个元素的处理
first = (count - 1 == index) ? nil : first?.next
last.next = first
} else {
let noe = node(index - 1)
noe.next = noe.next?.next
}
count -= 1
}

override func clear() {
let last = node(count - 1)
// 打破循环引用
last.next = nil
// 调用父类
super.clear()
}
}

4.双向链表

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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
class TwoWayLinkedList<T: Equatable> {
// 元素没有找到
private let ELEMENT_NOT_FOUND = -1
fileprivate(set) var first: Node<T>?
fileprivate(set) var last: Node<T>?
fileprivate(set) var count: Int = 0

init(_ ele: T?) {
if ele == nil {
first = nil
last = nil
} else {
first = Node(ele: ele!, prev: nil, next: nil)
last = first
count += 1
}
}

// 便利构造
convenience init() {
self.init(nil)
}

// 结点类
class Node<T> {
var ele: T
var prev: Node<T>?
var next: Node<T>?
init(ele: T, prev: Node?, next: Node?) {
self.ele = ele
self.prev = prev
self.next = next
}
}

// 索引所在元素获取
func get(_ index: Int) -> T {
checkBounds(index)
return node(index).ele
}

// 在某索引处插入元素
func insert(_ item: T, _ index: Int) {
if index < 0 || index > count {
// 越界
fatalError("索引有误, 已经越界")
}
if index == count {
let prev = last
let newNode = Node(ele: item, prev: prev, next: nil)
last = newNode
prev?.next = newNode
if index == 0 {
first = last
}
} else {
let next = node(index)
let prev = next.prev
let newNode = Node(ele: item, prev: prev, next: next)
next.prev = newNode
prev?.next = newNode
if newNode.prev == nil {
first = newNode
}
}
count += 1
}

// 追加元素
func append(_ item: T) {
insert(item, count)
}

// 移除某索引的元素
func remove(_ index: Int) -> T {
checkBounds(index)
let old = node(index)
let prev = old.prev
let next = old.next
if next == nil {
last = prev
} else {
next?.prev = prev
}

if prev == nil {
first = next
} else {
prev?.next = next
}
count -= 1
return old.ele
}

// 获取某元素所在索引
func indexOf(_ item: T) -> Int {
var node = first
var idx = 0
while node != nil {
if node!.ele == item {
return idx
}
node = node!.next
idx += 1
}
return ELEMENT_NOT_FOUND
}

// 清空所有元素
func clear() {
// 打破循环引用
var first = self.first
while first != nil {
first?.prev = nil
first = first?.next
}
self.first = nil
self.last = nil
count = 0
}

// 是否为空
func isEmpty() -> Bool {
return count == 0
}

// 打印
func desc() {
var node = first
var str = ""
for idx in 0..<count {
if idx == 0 {
str += "first:\(node!.ele),"
}
if node!.next != nil {
str += " [\(node!.ele), \(node!.next!.ele)]"
} else {
str += " [\(node!.ele), nil]"
}

if node != nil {
str += ","
}

if idx == count - 1 {
str += " last:\(node!.ele)"
}
node = node!.next

}
print(str)
}

// 获取索引所在的结点
fileprivate func node(_ index: Int) -> Node<T> {
checkBounds(index)
if index < count >> 1 {
// 在前半部分查找
var node = self.first
for _ in 0..<index {
node = node?.next
}
return node!
} else {
// 在后半部分查找
var node = self.last
for _ in (index + 1..<count).reversed() {
node = node?.prev
}
return node!
}
}

// 索引越界检查
fileprivate func checkBounds(_ index: Int) {
if index < 0 || index >= count {
// 越界
fatalError("索引有误, 已经越界")
}
}
}

5.双向循环链表

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
class TwoWayCircularLinkedList<T: Equatable>: TwoWayLinkedList<T> {
override func insert(_ item: T, _ index: Int) {
if index < 0 || index > count {
// 越界
fatalError("索引有误, 已经越界")
}
if index == count {
let prev = last
let newNode = Node(ele: item, prev: prev, next: first)
last = newNode
prev?.next = newNode
if index == 0 {
first = last
last?.next = newNode
}
first?.prev = newNode
} else {
let next = node(index)
let prev = next.prev
let newNode = Node(ele: item, prev: prev, next: next)
next.prev = newNode
prev?.next = newNode
if index == 0 {
// 首位插入元素
first = newNode
}
}
count += 1
}

override func remove(_ index: Int) -> T {
checkBounds(index)
let old: Node = node(index)
var prev = old.prev
var next = old.next
if count == 1 && index == 0 {
// 只有一个元素
prev = nil
next = nil
old.next = nil
old.prev = nil
}
if index == 0 {
first = next
}
if index == count - 1 {
last = prev
}
prev?.next = next
next?.prev = prev
count -= 1
return old.ele
}

override func clear() {
// 打破循环引用
var first = self.first
for idx in 0..<count {
first?.prev = nil
first = first?.next
if idx == count - 1 {
first?.next = nil
}
}
self.first = nil
self.last = nil
count = 0
}
}

6.栈

使用动态数组实现。

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
class Stack<T: Equatable> {
// 设置容量默认为10, 可自动扩容
private var list: ArrayList<T> = ArrayList(10)

// 元素数量
func size() -> Int {
return list.count
}

// 是否为空
func isEmpty() -> Bool {
return list.isEmpty()
}

// 入栈
func push(_ item: T) {
list.append(item)
}

// 出栈
func pop() -> T {
return list.remove(size() - 1)
}

// 获取栈顶元素
func top() -> T? {
return size() == 0 ? nil : list.get(size() - 1)
}

// 清空所有元素
func clear() {
list.clear()
}
}

7.队列

因为频繁地在开头末尾添加删除元素所以使用链表实现
又因为双向链表有头指针和尾指针而单向链表只有头指针所以使用双向链表实现(减少遍历)

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
class Queue<T: Equatable> {
private var list: TwoWayLinkedList<T> = TwoWayLinkedList()

// 元素数量
func size() -> Int {
return list.count
}

// 是否为空
func isEmpty() -> Bool {
return list.isEmpty()
}

// 入队
func enQueue(_ item: T) {
list.append(item)
}

// 出队
func deQueue() -> T {
return list.remove(0)
}

// 获取队头元素
func front() -> T? {
return list.first?.ele
}

// 清空所有元素
func clear() {
list.clear()
}

// 打印元素
func desc() {
list.desc()
}
}

使用栈实现队列

原理:

  1. 入队时, 把元素放入inStack中
  2. 出队时, 如果outStack为空, 则把inStack中的全部栈顶元素依次放到outStack中, 返回outStack的栈顶元素, 否则, 直接返回outStack的栈顶元素
    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
    class Queue_UseStack<T: Equatable> {
    // 维护两个栈
    private var inStack: Stack<T> = Stack()
    private var outStack: Stack<T> = Stack()

    // 元素数量
    func size() -> Int {
    return inStack.size() + outStack.size()
    }

    // 是否为空
    func isEmpty() -> Bool {
    return size() == 0
    }

    // 入队
    func enQueue(_ item: T) {
    inStack.push(item)
    }

    // 出队
    func deQueue() -> T {
    if outStack.isEmpty() {
    while inStack.isEmpty() == false {
    outStack.push(inStack.pop())
    }
    }
    return outStack.pop()
    }

    // 获取队头元素
    func front() -> T? {
    if outStack.isEmpty() {
    while inStack.isEmpty() == false {
    outStack.push(inStack.pop())
    }
    }
    return outStack.top()
    }

    // 清空所有元素
    func clear() {
    inStack.clear()
    outStack.clear()
    }
    }

8.循环队列

使用动态数组实现, 且各接口优化到O(1)时间复杂度
要点:

  1. 有一个指向队头元素的索引frontIndex, 必不可少
  2. 接口索引与真实索引的互换: 真实索引 = (frontIndex + index) % elements.count
  3. 入队
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
85
86
87
88
89
class CircleQueue<T: Equatable> {
// 元素数量
private var count: Int = 0
// 指向队头的索引
private var frontIndex: Int = 0
// 使用nil作为占位
private var elements: [T?]
// 默认10个元素
private let DEFAULT_CAPACITY = 10
private let ELEMENT_NOT_FOUND = -1

// 构造器, 初始化容量为capaticy的数组
init(_ capaticy: Int) {
let capaticy = capaticy < DEFAULT_CAPACITY ? DEFAULT_CAPACITY : capaticy
elements = [T?](repeating: nil, count: capaticy)
}

// 元素数量
func size() -> Int {
return count
}

// 是否为空
func isEmpty() -> Bool {
return count == 0
}

// 入队
func enQueue(_ item: T) {
ensureCapacity(count + 1)
elements[index(count)] = item
count += 1
}

// 出队
func deQueue() -> T {
let ele = elements[frontIndex]
if ele == nil {
fatalError("队列为空")
}
elements[frontIndex] = nil
// 不是frontIndex += 1, 要考虑frontIndex == elements.count但是elements有空闲位置的情况
// 这时应该是frontIndex = (frontIndex + 1) % elements.count, 也就是index(1)
frontIndex = index(1)
count -= 1
return ele!
}

// 获取队头元素
func front() -> T? {
return elements[frontIndex]
}

// 清空所有元素
func clear() {
for idx in 0..<elements.count {
elements[idx] = nil
}
frontIndex = 0
count = 0
}

// 数组扩容
private func ensureCapacity(_ capacity: Int) {
// 不需要扩容
if elements.count >= capacity {
return
}
var elements = self.elements
// 扩容1.5倍
let newCapacity = elements.count + elements.count >> 1
var newElements = [T?](repeating: nil, count: newCapacity)
for idx in 0..<count {
newElements[idx] = elements[index(idx)]
}
self.elements = newElements
frontIndex = 0
}

// 获取索引对应真实索引
private func index(_ index: Int) -> Int {
return (frontIndex + index) % elements.count
}

// 打印元素
func desc() {
print("frontIndex: \(frontIndex)" + " eles: \(elements)")
}
}

9.双端队列

两端都可以入队和出队

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
class DoubleEndedQueue<T: Equatable> {
private var list: TwoWayLinkedList<T> = TwoWayLinkedList()

// 元素数量
func size() -> Int {
return list.count
}

// 是否为空
func isEmpty() -> Bool {
return list.isEmpty()
}

// 从队头入队
func enQueueFront(_ item: T) {
list.insert(item, 0)
}

// 从队尾入队
func enQueueRear(_ item: T) {
list.append(item)
}

// 从队头出队
func deQueueFront() -> T {
return list.remove(0)
}

// 从队尾出队
func deQueueRear() -> T {
return list.remove(list.count - 1)
}

// 获取队头元素
func front() -> T? {
return list.first?.ele
}

// 获取队尾元素
func rear() -> T? {
return list.last?.ele
}

// 清空所有元素
func clear() {
list.clear()
}

// 打印元素
func desc() {
list.desc()
}
}

10.循环双端队列

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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
class CircleDoubleEndedQueue<T: Equatable> {
// 元素数量
private var count: Int = 0
// 指向队头的索引
private var frontIndex: Int = 0
// 使用nil作为占位
private var elements: [T?]
// 默认10个元素
private let DEFAULT_CAPACITY = 10
private let ELEMENT_NOT_FOUND = -1

// 构造器, 初始化容量为capaticy的数组
init(_ capaticy: Int) {
let capaticy = capaticy < DEFAULT_CAPACITY ? DEFAULT_CAPACITY : capaticy
elements = [T?](repeating: nil, count: capaticy)
}

// 元素数量
func size() -> Int {
return count
}

// 是否为空
func isEmpty() -> Bool {
return count == 0
}

// 从队头入队
func enQueueFront(_ item: T) {
ensureCapacity(count + 1)
frontIndex = index(-1)
elements[frontIndex] = item
count += 1
}

// 从队尾入队
func enQueueRear(_ item: T) {
ensureCapacity(count + 1)
elements[index(count)] = item
count += 1
}

// 从队头出队
func deQueueFront() -> T {
if count <= 0 {
fatalError("队列为空")
}
let ele = elements[frontIndex]
elements[frontIndex] = nil
frontIndex = index(1)
count -= 1
return ele!
}

// 从队尾出队
func deQueueRear() -> T {
if count <= 0 {
fatalError("队列为空")
}
let ele = elements[index(count - 1)]!
elements[index(count - 1)] = nil
count -= 1
return ele
}

// 获取队头元素
func front() -> T? {
return elements[frontIndex]
}

// 获取队尾元素
func rear() -> T? {
return elements[index(count - 1)]
}

// 清空所有元素
func clear() {
for idx in 0..<elements.count {
elements[idx] = nil
}
frontIndex = 0
count = 0
}

// 数组扩容
private func ensureCapacity(_ capacity: Int) {
// 不需要扩容
if elements.count >= capacity {
return
}
var elements = self.elements
// 扩容1.5倍
let newCapacity = elements.count + elements.count >> 1
var newElements = [T?](repeating: nil, count: newCapacity)
for idx in 0..<count {
newElements[idx] = elements[index(idx)]
}
self.elements = newElements
frontIndex = 0
}

// 获取索引对应真实索引
private func index(_ index: Int) -> Int {
var index = index
index += frontIndex
if index < 0 {
return index + elements.count
}
// return index % elements.count
return index - (index >= elements.count ? elements.count : 0)
}

// 打印元素
func desc() {
print("frontIndex: \(frontIndex)" + ",eles: \(elements)")
}
}

11. 二叉树

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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
class BinaryTree<T: Comparable> {
fileprivate var nodeCount = 0 // 结点数量
fileprivate var root: Node<T>? // 根节点

// 二叉树是否为空
func isEmpty() -> Bool {
return nodeCount == 0
}

// 清空
func clear() {
root = nil
nodeCount = 0
}

// 前序遍历(一般是根左右)
func preorderTraversal() {
print("---------以下是前序遍历的递归方式结果---------")
preorderTraversal(root)
print("---------以下是前序遍历的非递归方式结果---------")
if root == nil {
return
}
var results = [T]()
let stack = Stack<Node<T>>()
var p = root
while p != nil || stack.size() != 0 {
while p != nil {
// 先访问 根
results.append(p!.ele)
stack.push(p!)
// 再访问 左 (持续遍历左子树)
p = p?.left
}
p = stack.pop()
// 最后访问 右
p = p?.right
}
print(results)
}

fileprivate func preorderTraversal(_ node: Node<T>?) {
if node == nil {
return
}
print(node!.ele)
preorderTraversal(node!.left)
preorderTraversal(node!.right)
}

// 中序遍历(一般是左根右)
func inorderTraversal() {
print("---------以下是中序遍历的递归方式结果---------")
inorderTraversal(root)
print("---------以下是中序遍历的非递归方式结果---------")
if root == nil {
return
}
var results = [T]()
let stack = Stack<Node<T>>()
var p = root
while p != nil || stack.size() != 0 {
while p != nil {
// 持续访问左子树
stack.push(p!)
p = p?.left
}
// 弹出栈顶元素
p = stack.pop()
// 先访问左子树
results.append(p!.ele)
p = p?.right
}
print(results)
}

fileprivate func inorderTraversal(_ node: Node<T>?) {
if node == nil {
return
}
inorderTraversal(node!.left)
print(node!.ele)
inorderTraversal(node!.right)
}

// 后序遍历(一般是左右根)
func postorderTraversal() {
print("---------以下是后序遍历的递归方式结果---------")
postorderTraversal(root)
print("---------以下是后序遍历的非递归方式结果---------")
var results = [T]()
let stack = Stack<Node<T>>()
var p = root
var last: Node<T>? = nil
while p != nil || stack.size() != 0 {
while p != nil {
// 持续访问左子树
stack.push(p!)
p = p?.left
}
p = stack.top()
if p?.right == nil || p?.right == last {
// 没有右子树或者访问过右子树
results.append(p!.ele)
_ = stack.pop()
last = p
p = nil
} else {
p = p?.right
}
}
print(results)
}

fileprivate func postorderTraversal(_ node: Node<T>?) {
if node == nil {
return
}
postorderTraversal(node!.left)
postorderTraversal(node!.right)
print(node!.ele)
}

// 层序遍历--使用队列实现
func levelOrderTranversal() {
let queue = Queue<Node<T>>()
if root == nil {
return
}
var results = [T]()
queue.enQueue(root!)
while queue.size() != 0 {
let r = queue.deQueue()
results.append(r.ele)
if r.left != nil {
queue.enQueue(r.left!)
}
if r.right != nil {
queue.enQueue(r.right!)
}
}
print("---------以下是层序遍历的结果---------")
print(results)
}

// 是否是一颗完全二叉树
func isComplete() -> Bool {
if root == nil {
// 树为空
return false
}
var isAllLeaf = false
let queue = Queue<Node<T>>()
queue.enQueue(root!)
while queue.size() != 0 {
let r = queue.deQueue()
if isAllLeaf && !r.isLeaf() {
return false
}

if r.left != nil {
queue.enQueue(r.left!)
} else if r.left == nil && r.right != nil {
// 左子树为空而右子树不为空, 不是完全二叉树
return false
}

if r.right != nil {
queue.enQueue(r.right!)
} else {
// 左不为空右为空 或者 左右都为空, 要求之后的必须都是叶子结点
isAllLeaf = true
}
}
return true
}

// 查找前驱结点
fileprivate func precursor(_ node: Node<T>?) -> Node<T>? {
// 1. 空结点, 其前驱为空
if node == nil {
return nil
}

// 2. 前驱结点在左结点的右子树上, 比如找6的前驱
var p = node!.left
if p != nil {
while p!.right != nil {
p = p!.right
}
return p
}

// 3. 前驱结点在父节点\祖父结点上, 比如找9的前驱
p = node
while p!.parent != nil && p == p!.parent?.left {
p = p!.parent
}
return p!.parent
}

// 查找后继结点
fileprivate func successor(_ node: Node<T>?) -> Node<T>? {
// 1. 空结点, 其后继为空
if node == nil {
return nil
}

// 2. 后继结点在右结点的左子树上, 比如找7的后继
var p = node!.right
if p != nil {
while p!.left != nil {
p = p!.left
}
return p
}

// 3. 后继结点在父节点\祖父结点上, 比如找5的后继
p = node
while p!.parent != nil && p == p!.parent?.right {
p = p!.parent
}
return p!.parent
}

// 树的高度--迭代写法
func height() -> Int {
// 层序遍历法
let queue = Queue<Node<T>>()
if root == nil {
return 0
}
var level = 1
var height = 0
queue.enQueue(root!)
while queue.size() != 0 {
let r = queue.deQueue()
level -= 1
if r.left != nil {
queue.enQueue(r.left!)
}
if r.right != nil {
queue.enQueue(r.right!)
}
if level == 0 {
// 这一层遍历结束
level = queue.size()
height += 1
}
}
return height
//return height(root)
}

// 树的高度--递归写法
fileprivate func height(_ node: Node<T>?) -> Int {
if node == nil {
return 0
}
return 1 + max(height(node!.left), height(node!.right))
}

// 结点类
fileprivate class Node<T: Equatable>: Equatable {
var ele: T
var left: Node<T>?
var right: Node<T>?
var parent: Node<T>?
init(_ ele: T, _ parent: Node?) {
self.ele = ele
self.parent = parent
}

// 叶子结点, 左右结点均为空
func isLeaf() -> Bool {
return left == nil && right == nil
}

// 有两个结点
func hasTwoChildren() -> Bool {
return left != nil && right != nil
}

// 是左子结点
func isLeftChild() -> Bool {
// 比较指针是否一致
return parent != nil && parent?.left === self
}

// 是右子结点
func isRightChild() -> Bool {
// 比较指针是否一致
return parent != nil && parent?.right === self
}

// 对等比较
static func == (lhs: Node<T>, rhs: Node<T>) -> Bool {
return lhs.ele == rhs.ele
}
}
}

12.二叉搜索树

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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
class BinarySearchTree<T: Comparable>: BinaryTree<T> {
// 查找结点
fileprivate func findNode(_ ele: T) -> Node<T>? {
var p = root
while p != nil {
if ele == p!.ele {
// 元素相等, 直接替换
return p
} else if ele < p!.ele {
// 位于左子树
p = p!.left
} else {
// 位于右子树
p = p!.right
}
}
return p
}

// 添加结点
func addNode(_ ele: T) {
// 添加的是根节点
if root == nil {
root = Node(ele, nil)
nodeCount += 1
afterAdd(root!)
return
}
// 添加的不是根结点
else {
var p = root
var parent = root
while p != nil {
parent = p
if ele == p!.ele {
// 元素相等, 直接替换
p?.ele = ele
return
} else if ele < p!.ele {
// 位于左子树
p = p!.left
} else {
// 位于右子树
p = p!.right
}
}

// 得到parent结点
let newNode = Node(ele, parent)
if ele > parent!.ele {
parent?.right = newNode
} else {
parent?.left = newNode
}
// 总结点数量加1
nodeCount += 1

afterAdd(newNode)
}
}

// 移除结点
func remove(_ ele: T) {
var node: Node<T>? = findNode(ele)
if node == nil {
// 没有找到需要删除的结点
return
}

// 结点数量减1
nodeCount -= 1

// 度为2的结点
if node!.hasTwoChildren() {
// 找它的后继结点
let p = successor(node)
// 用后继结点内容替换待删除结点内容
node!.ele = p!.ele
// 需要删的结点就是node结点了
node = p
}

// node是叶子结点而且也是根结点
if node?.parent == nil {
root = nil
afterRemove(node!)
return
}

// 需要替换的结点
let replace = node?.left == nil ? node?.right : node?.left
if replace == nil {
// node没有左子树也没有右子树, 说明node是叶子结点
if node?.parent?.left == node {
// node是父结点的左结点
node?.parent?.left = nil
} else {
// node是父结点的右结点
node?.parent?.right = nil
}
afterRemove(node!)
} else {
if node?.parent == nil {
// 是根结点
root = replace
} else if node?.parent?.left == node {
// 是左结点
node?.parent?.left = replace
} else {
// 是右结点
node?.parent?.right = replace
}
afterRemove(node!)
}
}

fileprivate func afterAdd(_ node: Node<T>) {

}

fileprivate func afterRemove(_ node: Node<T>) {

}
}

13.AVLTree

1
2
3
4
5
6
7
8
9
class AVLTree<T: Comparable>: BinarySearchTree<T> {
fileprivate override func afterAdd(_ node: Node<T>) {
print("已经添加\(node)")
}

fileprivate override func afterRemove(_ node: Node<T>) {
print("已经移除\(node)")
}
}

还木有写完。。。。

14.红黑树

15.二叉堆

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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
protocol Heap  {
associatedtype T
var size: Int { get set }
// 是否为空
func isEmpty() -> Bool
// 清空
func clear()
// 添加元素
func add(_ ele: T)
// 获取堆顶元素
func get() -> T
// 删除堆顶元素
func remove() -> T
// 删除堆顶元素的同时插入一个新元素
func replace(_ ele: T) -> T?
}



class BinaryHeap<T: Comparable>: Heap {
// 使用nil作为占位
private var list: [T?]
// 元素数量
internal var size = 0
// 默认10个元素
private let DEFAULT_CAPACITY = 10

// 构造器
init(_ capaticy: Int) {
let capaticy = capaticy < DEFAULT_CAPACITY ? DEFAULT_CAPACITY : capaticy
list = [T?](repeating: nil, count: capaticy)
}

// 数组扩容
private func ensureCapacity(_ count: Int) {
if count > list.count {
var oldList = self.list
// 扩容1.5倍
let newCapacity = oldList.count + oldList.count >> 1
self.list = [T?](repeating: nil, count: newCapacity)
for idx in 0..<size {
self.list[idx] = oldList[idx]
}
}
}

// 是否为空
func isEmpty() -> Bool {
return size == 0
}

// 清空
func clear() {
for idx in 0..<size {
list[idx] = nil
}
size = 0
}

// 添加元素
func add(_ ele: T) {
ensureCapacity(size + 1)
list[size] = ele
size += 1
siftUp(size - 1)
}

// 获取堆顶元素
func get() -> T {
if self.isEmpty() {
fatalError("堆为空, 无法删除")
}
return list[0]!
}

// 删除堆顶元素
func remove() -> T {
if self.isEmpty() {
fatalError("堆为空, 无法删除")
}
size -= 1
let first = list[0]!
list[0] = list[size]
list[size] = nil
siftDown(0);
return first
}

// 删除堆顶元素的同时插入一个新元素
func replace(_ ele: T) -> T? {
if self.isEmpty() {
fatalError("堆为空, 无法删除")
}
var root: T?
if (size == 0) {
list[0] = ele
size += 1
} else {
root = list[0];
list[0] = ele;
siftDown(0);
}
return root;
}

// 建堆
func heapify(_ eles: [T]) {
size = eles.count
for idx in 0..<eles.count {
list[idx] = eles[idx]
}
// 自上而下的上滤O(nlogn)
/*
for idx in 0..<size {
siftUp(idx)
}
*/

// 自下而上的上滤O(n)
for idx in (0...size >> 1).reversed() {
siftDown(idx)
}
}

// index位置的元素下滤
private func siftDown(_ idx: Int) {
let ele = list[idx]!
var idx = idx
while idx < size >> 1 {
// 左结点
var childIdx = idx << 1 + 1
var child = list[childIdx]!
// 右结点索引
let rightIdx = childIdx + 1
// 如果右结点存在, 则取出左右结点中较大的一个
if rightIdx < size && list[rightIdx]! > child {
childIdx = rightIdx
child = list[childIdx]!
}
// 如果自己不小于较大子结点, 停止下滤
if ele >= child {
break
}
// 交换自己与较大子结点的位置
list[idx] = child
idx = childIdx
}
list[idx] = ele
}

// index位置的元素上滤
private func siftUp(_ idx: Int) {
var idx = idx
let ele = list[idx]!
while idx > 0 {
let parentIdx = (idx - 1) >> 1
let parent = list[parentIdx]!
if parent >= ele {
// 父结点不小于自己, 停止上滤
break
}
// 交换自己与父结点的位置
list[idx] = parent
idx = parentIdx
}
list[idx] = ele
}

func desc() {
print(list)
}
}

上滤
1、当插入一个新元素时,放在最末尾。
2、若有父节点,将插入节点和父节点比较,如果插入节点大于父节点,交换位置。
3、重复2,直至插入节点不小于父节点或者没有父节点,上滤结束。

下滤
1、删除首元素,将最后一个元素移到首节点。
2、若有孩子,则比较该节点和最大孩子的值,若小于最大孩子的值,与最大的孩子互换位置。
3、重复2,直至该节点的值大于最大孩子的值或者没有孩子,下滤结束,堆序性得以满足。

16.优先级队列

使用二叉堆实现。

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
class PriorityQueue<T: Comparable> {
private var heap: BinaryHeap = BinaryHeap<T>(10)

func size() -> Int {
return heap.size
}

func isEmpty() -> Bool {
return heap.isEmpty()
}

func clear() {
heap.clear()
}

func enQueue(_ ele: T) {
heap.add(ele)
}

func deQueue() -> T {
return heap.remove()
}

func front() -> T {
return heap.get()
}
}