《iOS面试之道》阅读笔记（2）

栈和队列

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

在iOS面试之道里面，所有不同数据类型的Stack的创建是遵循一个Stack Protocol，然后用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：
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做线层安全，我所知道的有两个方法：

用串行队列（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。

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 = NULL;
        NSString *name = [NSString stringWithFormat:@"com.ThreadSafeStack.dispatchQueue.%@", [[NSUUID UUID] UUIDString]];
        _isolationQueue = dispatch_queue_create([name cStringUsingEncoding:NSASCIIStringEncoding], DISPATCH_QUEUE_SERIAL);
    }
    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;
        }
    });
    return res;
}

#pragma mark - public methods

- (id)peek {
    __block id res;
    dispatch_sync(self.isolationQueue, ^{
        res = self.head.value;
    });
    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;
        }
    });
    return res;
}

- (void)push:(id)object {
    dispatch_async(self.isolationQueue, ^{
        self.head = [[ListNode alloc] initWithValue:object andNext:self.head];
    });
}

#pragma mark - override methods

- (NSString *)description {
    NSMutableString *des = [NSMutableString stringWithFormat:@"%@: ", [super description]];
    dispatch_sync(self.isolationQueue, ^{
        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

《iOS面试之道》阅读笔记（2）

更多数据结构

链表

栈和队列

Juncheng Han