更多数据结构

链表

单向链表节点:

1
2
3
4
5
6
7
8
9
class ListNode {
var val: Int
var next: ListNode?

init(_ val: Int) {
self.val = val
self.next = nil
}
}

双向的话就多加一个prev。

解决链表问题是常用的技巧:

  1. dummy head: 创建一个辅助的链表头结点,然后返回的时候为return dummy.next. 这个技巧为了省去我们判断头结点是否为nil,减少程序错误。
  2. fast and slow pointer:快慢指针,慢指针每次移动一步,快指针每次移动两步。用快慢指针可以轻松获取链表中间节点,和判断链表是否有环。

栈和队列

栈Stack,后进先出(LIFO)。Swift没有现成的Stack,但是可以用Array来轻松实现。

在iOS面试之道里面,所有不同数据类型的Stack的创建是遵循一个Stack Protocol,然后用Associated Types
来设定不同的数据类型。这非常Swifty。这里也可以用Swift自带的Generic来做:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
struct Stack<Element> {
var store = [Element]()

var size: Int {
return store.count
}

var peek: Element? {
return store.last
}

mutating func push(_ item: Element) {
store.append(item)
}
mutating func pop() {
store.removeLast()
}
}

var intStack = Stack<Int>()
intStack.push(1)

队列Queue,先进先出(FIFO)。同样也可以用Array来实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
struct Queue<Element> {
var store = [Element]()

var size: Int {
return store.count
}

var isEmpty: Bool {
return store.count == 0
}

mutating func enqueue(_ e: Element) {
store.append(e)
}

mutating func dequeue() -> Element? {
return store.first
}
}

var queue = Queue<Int>()

简单解释用两个Stack实现一个Queue。假设我们有StackA和StackB,StackA用来存Enqueue进来的元素,StackB用来处理Dequeue的元素。

  • Enqueue:直接把新的元素放进StackA
  • Dequeue:
    1. 如果StackB是空的,则把StackA中的所有元素dequeue出来然后enqueue进StackB中,这个时候,之前最先进去StackA的元素就到了StackB的顶部,然后就只需要dequeue出StackB里的一个元素返回。
    2. 如果StackB中不是空,就直接dequeue然后返回。

用两个Queue实现Stack要稍微难想一点点,要点事两个Queue要shift他们的功能。

更多:

如何实现一个线程安全的Stack。实现线程安全在iOS中有多种方法,主要分为运用锁(lock)相关的技术和运用线程先关的技术。在阅读苹果关于多线程编程的文档后,可以得知,苹果官方推荐工程师用线程相关的技术,特别是GCD,来做线程安全。原因是因为:iOS系统分为应用层(application level)和内核层(kernel level)。锁的处理是在内核层,当程序每一次创建锁和开锁的时候,它都要从应用层转到内核层进行操作,这个过程的消耗是巨大的,更不用说在用锁实现线程安全的时候会有大量的建锁和开锁的程序。而苹果的GCD则不同,它基本上是只运行在应用层的,只有真正有需要的时候,才会进去内核层。

再来说说CGD做线层安全,我所知道的有两个方法:

  1. 用串行队列(Serial dispatch queue)的方法
  2. 用并行队列(Concurrent dispatch queue)+ 栅栏(Barrier)的方法

我以前一直认为第二种方法更高效,毕竟是并发嘛。但是在和一个苹果工程师交谈后和阅读苹果文档后,我发现了问题所在。在用第二种方法的时候,程序会创建Barrier和删除Barrier,情形类似于锁,这个过程会消耗很多性能。如果这个线程安全的Stack有大量的数据操作的话,自然就慢了。

看了这么多,其实苹果官方文档中有这个一句话:

Serial dispatch queue offer a more efficient alternative to locks and other synchronization primitives.

意思就是串行最棒棒。所以我为什么之前要讲这么多。

给个例子吧,这个是我以前写的Thread Safe Stack,虽然是用ObjC,但是可以看看。这里我是用LinkList来实现Stack。所有的程序都是ObjC,不过更优秀的做法是用C或C++来写LinkList。

ListNode.h

1
2
3
4
5
6
7
8
9
10
#import <Foundation/Foundation.h>

@interface ListNode : NSObject <NSSecureCoding>

@property (nonatomic, strong, nullable) id value;
@property (nonatomic, strong, nullable) ListNode *next;

- (nullable instancetype)initWithValue:(nullable id)value andNext:(nullable ListNode *)next;

@end

ListNode.m

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
#import "ListNode.h"

@implementation ListNode

- (instancetype)init
{
self = [super init];
if (self) {
self.next = NULL;
self.value = NULL;
}
return self;
}

- (instancetype)initWithValue:(id)value andNext:(ListNode *)next {
self = [super init];
if (self) {
self.next = next;
self.value = value;
}
return self;
}

#pragma mark - NSCoding

#define kValueKey @"valueKey"
#define kNextKey @"nextKey"

- (void)encodeWithCoder:(nonnull NSCoder *)aCoder {
[aCoder encodeObject:_value forKey:kValueKey];
[aCoder encodeObject:_next forKey:kNextKey];
}

- (nullable instancetype)initWithCoder:(nonnull NSCoder *)aDecoder {
id value = [aDecoder decodeObjectForKey:kValueKey];
id next = [aDecoder decodeObjectOfClass:[ListNode class] forKey:kNextKey];

self = [super init];

if (self) {
self.value = value;
self.next = next;
}
return self;
}

+ (BOOL)supportsSecureCoding {
return YES;
}

@end

ThreadSafeStack.h

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
#import <Foundation/Foundation.h>

@protocol ThreadSafeStackProtocol

- (void)test;

@end

@interface ThreadSafeStack<__covariant ObjectType> : NSObject <NSSecureCoding, NSMutableCopying, NSCopying>

// MARK: initializer
- (instancetype)init;

// MARK: public motheds
- (void)push:(ObjectType)object;
- (ObjectType)pop;
- (ObjectType)peek;


@property (nonatomic, weak) id<ThreadSafeStackProtocol> delegate;
@property (nonatomic, strong) NSArray<id<ThreadSafeStackProtocol>> * array;

@property (readonly) NSUInteger count;

@end

ThreadSafeStack.m

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
#import "ThreadSafeStack.h"
#import "ListNode.h"

@interface ThreadSafeStack()

@property (nonatomic, strong) ListNode *head;
@property (nonatomic, strong) dispatch_queue_t isolationQueue;

@end

@implementation ThreadSafeStack

- (instancetype)init {
self = [super init];
if (self) {
// head = (ListNodeC *)malloc(sizeof(ListNodeC));
_head = NULL;
NSString *name = [NSString stringWithFormat:@"com.ThreadSafeStack.dispatchQueue.%@", [[NSUUID UUID] UUIDString]];
_isolationQueue = dispatch_queue_create([name cStringUsingEncoding:NSASCIIStringEncoding], DISPATCH_QUEUE_CONCURRENT);
}
return self;
}

#pragma mark - setter and getter

- (NSUInteger)count {
__block NSInteger res = 0;
dispatch_sync(self.isolationQueue, ^{
ListNode *temp = self.head;
while (temp != NULL) {
res += 1;
temp = temp.next;
}

#if DEBUG
NSLog(@"count %ld", (long)res);
#endif
});
return res;
}

#pragma mark - public methods

- (id)peek {
__block id res;
dispatch_sync(self.isolationQueue, ^{
res = self.head.value;

#if DEBUG
NSLog(@"peek %@", res);
#endif
});
return res;
}

- (id)pop {
__block id res = NULL;
dispatch_sync(self.isolationQueue, ^{
if (self.head == NULL) {
} else {
res = self.head.value;
self.head = self.head.next;
}

});

#if DEBUG
NSLog(@"pop %@", res == NULL ? @"Null" : res);
#endif
return res;
}

- (void)push:(id)object {
dispatch_async(self.isolationQueue, ^{
self.head = [[ListNode alloc] initWithValue:object andNext:self.head];
#if DEBUG
NSLog(@"push %@", object);
#endif
});
}

#pragma mark - override methods

- (NSString *)description {
NSMutableString *des = [NSMutableString stringWithFormat:@"%@: ", [super description]];
dispatch_sync(self.isolationQueue, ^{
// struct ListNodeC * temp = head;
ListNode *temp = self.head;
while (temp != NULL) {
[des appendString:[NSString stringWithFormat:@"%@ ", [temp.value description]]];
temp = temp.next;
}
});
return [des copy];
}

#pragma mark - NSCopy and NSMutableCopy

- (id<NSCopying, NSSecureCoding>)copyWithZone:(NSZone *)zone {

ThreadSafeStack *copy = [[[self class] allocWithZone:zone] init];

copy.head = self.head;

return copy;
}

- (id)mutableCopyWithZone:(NSZone *)zone {
return [self copyWithZone:zone];
}

#pragma mark - NSCoding

#define kHeadKey @"headKey"

- (void)encodeWithCoder:(nonnull NSCoder *)aCoder {
[aCoder encodeObject:_head forKey:kHeadKey];
}

- (nullable instancetype)initWithCoder:(nonnull NSCoder *)aDecoder {
id head = [aDecoder decodeObjectOfClass:[ListNode class] forKey:kHeadKey];

self = [super init];
if (self) {
_head = head;
NSString *name = [NSString stringWithFormat:@"com.ThreadSafeStack.dispatchQueue.%@", [[NSUUID UUID] UUIDString]];
_isolationQueue = dispatch_queue_create([name cStringUsingEncoding:NSASCIIStringEncoding], DISPATCH_QUEUE_SERIAL);
}
return self;
}

+ (BOOL)supportsSecureCoding{
return YES;
}

Reference:

https://xiaozhuanlan.com/ios-interview 《iOS 面试之道》

Concurrency programming / GCD
https://developer.apple.com/documentation/dispatch
https://developer.apple.com/library/content/documentation/General/Conceptual/ConcurrencyProgrammingGuide/Introduction/Introduction.html\#//apple\_ref/doc/uid/TP40008091-CH1-SW1

Threading
https://developer.apple.com/library/content/documentation/Cocoa/Conceptual/Multithreading/Introduction/Introduction.html\#//apple\_ref/doc/uid/10000057i-CH1-SW1