更多数据结构
链表
单向链表节点：
class ListNode {
var val: Int
var next: ListNode?
init(_ val: Int) {
self.val = val
self.next = nil
}
}
双向的话就多加一个prev。
解决链表问题是常用的技巧：
- dummy head: 创建一个辅助的链表头结点，然后返回的时候为return dummy.next. 这个技巧为了省去我们判断头结点是否为nil，减少程序错误。
- fast and slow pointer：快慢指针，慢指针每次移动一步，快指针每次移动两步。用快慢指针可以轻松获取链表中间节点，和判断链表是否有环。
栈和队列
栈Stack，后进先出（LIFO）。Swift没有现成的Stack，但是可以用Array来轻松实现。
在《iOS面试之道》里面，所有不同数据类型的Stack的创建是遵循一个Stack Protocal，然后用Associated Types
来设定不同的数据类型。这非常Swifty。这里也可以用Swift自带的Generic来做：
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来实现。
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：
- 如果StackB是空的，则把StackA中的所有元素dequeue出来然后enqueue进StackB中，这个时候，之前最先进去StackA的元素就到了StackB的顶部，然后就只需要dequeue出StackB里的一个元素返回。
- 如果StackB中不是空，就直接dequeue然后返回。
用两个Queue实现Stack要稍微难想一点点，要点是两个Queue要shift他们的功能。
更多：
如何实现一个线程安全的Stack：
实现线程安全在iOS中有多种方法，主要分为运用锁（lock）相关的技术和运用线程先关的技术。在阅读苹果关于多线程编程的文档后，可以得知，苹果官方推荐工程师用线程相关的技术，特别是GCD，来做线程安全。原因是因为：iOS系统分为应用层（application level）和内核层（kernel level）。锁的处理是在内核层，当程序每一次创建锁和解开锁的时候，它都要从应用层转到内核层进行操作，这个过程的消耗是巨大的，更不用说在用锁实现线程安全的时候会有大量的建锁和解锁的程序。而苹果的GCD则不同，它基本上是只运行在应用层的，只有真正有需要的时候，才会进去内核层。
再来说说CGD做线层安全，我所熟知的两个方法：
- 用串行队列（Serial dispatch queue）的方法
- 用并行队列（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和ObjC混编。
ListNode.h
#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
#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
#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
#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:
故胤道长和唐巧两位大神的书《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
