教程一原文：Core Graphics Tutorial Part 1: Getting Started

Behind the scenes in Core Graphics

Each UIView has a graphics context, and all drawing for the view renders into this context before being transferred to the device’s hardware.

iOS updates the context by calling draw(_:) whenever the view needs to be updated. This happens when:

• The view is new to the screen.
• Other views on top of it are moved.
• The view’s hidden property is changed.
• Your app explicitly calls the setNeedsDisplay() or setNeedsDisplayInRect() methods on the view.

Note: Any drawing done in draw(_:) goes into the view’ graphics context. be aware that if you start drawing outside of draw(_:), as you’ll do in the final part of this tutorial you’ll have to create your own graphics context.

you haven’t used Core Graphics yet in this tutorial because UIKit has wrappers around many of the Core Graphics functions. A UIBezierPath, for example, is a wrapper for a CGMutablePath, which is the lower-level Core Graphics API.

Note: Never call draw(_:) directly. If your view is not being updated, then call setNeedsDisplay() on the view.

setNeedsDisplay() does not itself call draw(_:), but it flags the view as ‘dirty’, triggering a redraw using draw(_:) on the next screen update cycle. Even if you call setNeedsDisplay() five times in the same method you’ll only ever actually call draw(_:) once.

Drawing Into the Context

Core Graphics uses a “painter’s model”. When you draw into a context, it’s almost like making a painting. You lay down a path and fill it, and then lay down another path on top and fill it. You can’t change the pixels that have been laid down, but you can “paint” over them.

This image from Apple’s documentation describes how this works. Just as it is when you’re painting on a canvas, the order in which you draw is critical.

Note: Remember that a path simply consists of points. Here’s an easy way to grasp the concept: when creating the path imagine that you have a pen in hand. Put two dots on a page, then place the pen at the starting point, and then draw a line to the next point by drawing a line.

That’s essentially what you do with the above code by using move(to:) and addLine(to:).

Points and Pixels

iPad 2：1 point = 1 pixel；

iPhone 6：2x retina screen，1 point = 2 * 2 pixels；

iPhone 6 Plus：3x retina screen，1 point = 3 * 3 pixels。

iOS anti-aliases the half-filled pixels with a color half way between the two colors, and the line looks fuzzy.

If you have oddly sized straight lines, you’ll need to position them at plus or minus 0.5 points to prevent anti-aliasing. If you look at the diagrams above, you’ll see that a half point on the iPad 2 will move the line up half a pixel, on the iPhone 6, up one whole pixel, and on the iPhone 6 Plus, up one and a half pixels.

教程二原文：Core Graphics Tutorial Part 2: Gradients and Contexts

Core Graphics

This image from Apple describes the relevant frameworks conceptually:

原文：Grand Central Dispatch Tutorial for Swift 3: Part 2/2

欢迎来到 GCD 系列教程的第二篇，也是最后一篇。

在该系列的第一篇（原文链接）中，你学习了关于并发、线程以及怎么使用 GCD。你为读出图片实现了一个单例，并且利用 dispatch barriers 与 synchronous dispatch queues 决了读者-写者问题以达到线程安全。同时，你使用 dispatch queues 来延迟提示信息的显示来提高 app 的用户体验，以及当初始化 ViewController 时异步分流 CPU 密集工作。

在这一篇的 GCD 教程中，同样会使到上篇中的 GooglyPuff app。你将深入研究高级的 GCD 概念，包括 dispatch groups、取消 dispatch blocks、异步测试技术以及 dispatch sources。

是时候探索更多的GCD了！

开始

你可选择继续使用上一篇教程的工程项目。或者，你可以下载准备好的项目。

运行 app，点击 + 并选择 Le Internet 来添加网络照片。你应该注意到了图片还没在下载完成而 Download Complete 提示框已经提前显示出来。

这就是你需要解决的第一个问题。

Dispatch Groups

打开 PhotoManager.swift 并查看 downloadPhotosWithCompletion(_:)：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

func downloadPhotosWithCompletion(
  _ completion: BatchPhotoDownloadingCompletionClosure?) {
  var storedError: NSError?
  for address in [overlyAttachedGirlfriendURLString,
                  successKidURLString,
                  lotsOfFacesURLString] {
                    let url = URL(string: address)
                    let photo = DownloadPhoto(url: url!) {
                      _, error in
                      if error != nil {
                        storedError = error
                      }
                    }
                    PhotoManager.sharedManager.addPhoto(photo)
    }
    
    completion?(storedError)
}

提示框是通过该方法传入的参数 completion 闭包调用的。它是在图片下载的 for 循环后直接调用的。你误以为下载图片会在该闭包调用之前完成。

图片下载是通过调用 DownloadPhoto(url) 完成的。该调用的结果会立即返回，但实际上下载过程是异步的。所以当 completion 调用时，并不能保证所有的图片已经下载完成。

What you want is for downloadPhotosWithCompletion(_:) to call its completion closure after all the photo download tasks are complete. How can you monitor these concurrent asynchronous events to achieve this? With the current methodology, you don’t know when the tasks are complete and they can finish in any order.

好消息！Dispatch groups的设计就是用来解决该问题的。你可以使用 dispatch group 把多个任务组合在一起并等待它们完成，或者当它们一旦完成后收到通知。这些任务可以是异步或，甚至可以是不同队列的任务。

DispatchGroup 管理调度组。你第一个要关注的是 wait 方法。 在该 group 所有的调度任务完成之前它会阻塞当前线程。（原谅：This blocks your current thread until all the group’s enqueued tasks have been completed.）

在 PhotoManager.swfit 中使用下面的代码覆盖 downloadPhotosWithCompletion(_:) 中的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

DispatchQueue.global(qos: .userInitiated).async { // 1
  var storedError: NSError?
  let downloadGroup = DispatchGroup() // 2
  for address in [overlyAttachedGirlfriendURLString, 
                  successKidURLString,
                  lotsOfFacesURLString] {
    let url = URL(string: address)
    downloadGroup.enter() // 3
    let photo = DownloadPhoto(url: url!) {
      _, error in
      if error != nil {
        storedError = error
      }   
      downloadGroup.leave() // 4
    }   
    PhotoManager.sharedManager.addPhoto(photo)
  }   
      
  downloadGroup.wait() // 5
  DispatchQueue.main.async { // 6
    completion?(storedError)
  }   
}

这里，一步一步的讲解上面的代码具体做了什么：

1. 由于你使用了同步的 wait 方法会阻塞当前线程，所以你使用 async 把整个方法放入后台队列中进行，以确保该方法不会阻塞主线程。
2. 这里你创建了一个新的 dispatch group。
3. 你调用 enter() 来手动通知 goup 该任务已经开始了。你必须使用 leave() 的调用次数来平衡 enter()的调用次数，否则你的 app 将会崩溃。
4. 在这里，你通知 group 该任务已经完成。
5. 你调用 wait() 来阻塞当前线程，等待所有任务完成。这种永远的等待是好的因为 photos 创建的任务总是会完成。你可以使用 wait(timeout:) 来指定一个超时并且当超时后将不再等待。
6. 这里，你保证所有的图片下载任务完成或者超时。然后在主线程回调上执行你的 completion 闭包。

Bulid 并运行你的 app。通过 Le Internet 选项下载图片并检查所有图片下载完成前提示框是否弹出。

笔记：TODO

Dispatch group 对于所有类型的队列来说是个很好选择。你应该警惕的是在主线程中，如果你同步的等待所有任务完成，由于你不希望占用主线程。然而，异步模型是非常好的方法用来更新 UI，尤其是在几个需要长时间运行的任务完成后更新 UI，例如网络调用。

当前的解决方法是不错的，不过在通常情况下应该尽可能的避免阻塞当前线程。下一任务是当任务完成后使用异步通知的方式来重写它。

Dispatch Groups，Take 2（第二种使用方式）

异步调度到另一个队列然后使用 wait 阻塞当前队列的做法是不够优雅的。幸好，这是有一个更好的方法。当 group 的所有任务完成时，可以使用 DispatchGroup 的 notify 来代替。

仍然在 PhotoManager.swift 中，使用下面的代码替换 downloadPhotosWithCompletion(_:) 中的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

// 1
var storedError: NSError?
let downloadGroup = DispatchGroup()
for address in [overlyAttachedGirlfriendURLString,
                successKidURLString,
                lotsOfFacesURLString] {
  let url = URL(string: address)
  downloadGroup.enter()
  let photo = DownloadPhoto(url: url!) {
    _, error in
    if error != nil {
      storedError = error
    }   
    downloadGroup.leave()
  }   
  PhotoManager.sharedManager.addPhoto(photo)
}   
    
downloadGroup.notify(queue: DispatchQueue.main) { // 2
  completion?(storedError)
}

解释下这里做了些什么：

1. 在这新实现方法中，你不再需要使用 async 来包含这些代码，因为它并不会阻塞主线程。
2. notify(queue:work:) 处理异步完成闭包。当 group 中的所有任务执行完成后它将被调用。你指定了 completion 任务将在主线程上运行。

这是一个非常清晰方式来处理这个特定的任务，并且它不会阻塞任何线程。

Build 并运行 app。检验一下当所有网络图片下载完成后提示框才弹出：

Concurrency Looping （并发循环）

所有这些新的工具任你使用，你应该很使用线程来做任何事，是吗？

看一下 PhotoManager 中的 downloadPhotosWithCompletion(_:)。你应该注意到了，这里使用了 for 循环来迭代下载三张图片。你的任务是在 for 循环中尝试使用并发来加速下载。

这正好是 DispatchQueue.concurrent(iterations:execute:) 的工作。（未完待续…）

原文：Controlling Animation Timing

有个协议叫做 CAMediaTiming ，而 CABasicAnimation 与 CAKeyframeAnimation 的基类 CAAnimation 实现了这个协议。它包含了所有与 timing 相关的属性，比如：duration，beginTime 与 repeatCount 就是来自于它。总而言之，这个协议包含有 8 个属性，这些属性相互搭配使用可以精准的控制 timing。苹果官方文档中这些属性的使用往往只有几句话来说明，所以看完所有这些相关的内容肯定要比这篇文章快。不过，使用视觉化的方法来解释 timing 更加清晰易懂。

红黑树是一种可以自动平衡的二叉查找树。它在二叉查找树的基础上为每个节点添加了额外的属性：红色或黑色的颜色。在进行插入、删除操作后，它会进行自动平衡操作。从而确保该树的树根到叶子的所有路径长度相差保持在2位以下。

条件

红黑树需要满足以下条件：

1. 所有节点为黑或白色；
2. 根节点为黑；
3. 所有叶子（Nil）为黑色；
4. 如果一个节点为红色，那么它的子节点都为黑色；
5. 对所有的节点而言，该节点到它的叶子的所有简单路径所包含的黑色节点是相同的。

操作

旋转操作

旋转操作如下：

1
2
3
4
5
6

     |                        |
    [y]    Right-Rotate      [x]
   /   \   ~~~~~~~~~~~>     /   \
 [x]    c  <~~~~~~~~~~~~   a    [y]
 / \        Left-Rotate          / \
a   b                           b   c

1.右旋转 Right-Rotate(T, y)

1
2
3
4
5
6
7
8
9
10
11
12
13

x = y.left
y.left = x.right
if x.right != nil
	x.right.p = y
x.p = y.p
if y.p == nil
	T.root = x
else y == y.p.left
	y.p.left = x
else
	y.p.right = x
x.right = y
y.p = x

2.左旋转 Left-Rotate(T, x)

1
2
3
4
5
6
7
8
9
10
11
12
13

y = x.right
x.right = y.left
if y.left != nil
	y.left.p = x
y.p = x.p
if x.p == nil
	T.root = y
else if x.p.left == x
	x.p.left = y
else
	x.p.right = y
y.left = x
x.p = y

原文：Grand Central Dispatch Tutorial for Swift 3:Part1/2

GCD 是管理并发操作的底层 API。使用 GCD 把计算昂贵的任务放到后台执行，来改善你的 app 反应灵敏度。它是一个容易使用加锁与多线程的并发模型。

在 Swift 3 中，对 GCD 进行了大幅度的修改，从基于 C API 到 “Swifter”API，包含了新的 Class 与新的数据结构。

在这两篇 GCD 教程中，你将学习 GCD 的来龙去脉。这第一篇教程将介绍 GCD 能做什么以及展示几个基础的 GCD 函数。在第二篇教程中，你将学习一些 GCD 高级函数。

你将在 GooglyPuff 这个已经提供的应用上进行开发。GooglyPuff 是一个没有性能改善，“非线程安全”的app，它使用了 CoreImage 人脸识别API在脸上覆盖一双 Googly Eyes。你可以选择图片库或者从网络下载的图片，来使用这种效果。

在这篇教程中，你的任务是使用 GCD 改善这个 app 并确保你可安全的从不同的线程调用代码。

开始

下载 starter project 并解压。使用 Xcode 打开并运行这个项目，看看它都有些什么功能。

首页初始时为空界面。点击+然后点击Le Internet从网络上下载预备好图片。点击第一张图片，你将会看到 Googly Eyes 添加到脸上。

在这个篇教程中，这里有4个主要的类你将会用到：

• PhotoCollectionViewController： 初始的 view controller。它显示选择好的图片的缩略图；
• PhotoDetailViewController：显示从PhotoCollectionViewController中选择的图片以及添加 googly eyes 到图片上。
• Photo：这是一个协议，描述了图片的属性。它提供图片，缩略图以及它们相关的状态。有两个类实现了这个协议：DownloadPhoto 实例化一张图片从URL实例，AssetPhoto 实例化一张图片从PHAsset实例。
• PhotoManager：这是一个管理所有Photo对象。

这个 app 还有几个问题。一个总题是你应该注意到的当运行 app 时下载完成的提示过早的显示。你将在该系列教程的第二篇解决此问题。

在这第一篇教程中，你要的事情是改善 googly-fying 处理性能以及让 PhotoManager 变得线程安全。

GCD的概念

要懂得 GCD，你需要理解几个与 concurrency（并发）与 threading（线程）相关的概念。

Concurrency（并发）

iOS中的 process（进程）或应用是由1或多个线程组成。这些线程是由操作系统调度程序独立管理的。所有线程都能并发执行，但这是由系统来决定是否并发执行以及怎样执行。

单核（Single-core）设备可以通过时间分片（time-slicing）来达到并发。它们将运行在一个线程上，执行上下文切换，然后运行其他另一个线程。

而多核（Multi-core）设备则是另一种情况，通过并行（parallelism）在同一时间执行多线程。

GCD 是以线程为基础的。底层的实现是它管理一个共享线程池（shared therad pool）。使用 GCD 你添加代码块或者 work items 到 dispatch queues，并由GCD来决定它们在哪个线程上执行。

比如你构建你的代码，你将会发现有的代码块它们应该同时运行，而有的不应该。这就允许你利用 GCD 的并发执行。

注意，GCD 决定多少并行是必需的是基于系统及闲置系统资源。务必注意的是并行需要并发，但并发不能保证并行。（原文： It’s important to note that parallelism requires concurrency, but concurrency does not guarantee parallelism.）

总之，并发是关于结构，而并行是关于执行。（原文：Basically, concurrency is about structure while parallelism is about execution.）

译者注：stackoverflow上有关于并发与并行的区别的提问：Concurrency vs Parallelism - What is the difference?

Queues（队列）

GCD 提供 DispatchQueue（调度队列）来管理你所提交的任务，并按先进先出的顺序来执行，保证第一个被提交的任务第一个开始。

Dispatch Queue 是线程安全的，这意味着你可以从多个线程同时访问它们。当你理解了怎么用 dispatch queue 为你的部分代码提供线程安全时，GCD 的好处是比较明显的。关键是挑选出合适的 dispatch queue 以及正确的使用调度函数（dispatching function）来提交你的代码（work）到这个队列。

Queues 可以为 serial（串行）或 concurrent（并发）。Serial队列确保任何时刻只有一个任务在运行。GCD控制着执行时间。你不知道当前任务结束与下一任务开始之间的时间为多少：

Concurrent 队列允许多个任务在同一时间运行。这些任务将按照添加时的顺序开始。这些任务可能以任何顺序结束并且你即不知道下一个任务什么时候开始，也不知道什么时候有多少个任务在执行。

下面是任务执行的例子：

注意 Task 1、Task 2 与 Task 3 三者先后较快的开始执行。另一方面，Task 0 结束时Task1才开始，同样我们也注意到 Task 3 比 Task 2 慢执行，但 Task 3 先结束。

什么时候开始一个任务这完全取决于 GCD。如果一个任务的运行时间覆盖到了其他任务，它将由GCD决定否应该运行在不同的核上，如果有空闲的核话，或者执行一个 context switch（上下文切换）来运行不同的任务。

GCD提供了三个主要的队列类型：

1. Main queue（主队列）： 运行在主线程上，它是 serial queue（串行队列）。

2. Global queues（全局队列）： 整个系统共享的并发队列。它有4种不同优先级的队列：high、default、low 以及 background。background 权限的队列是 I/O 节流（throttled）。

3. Custom queues（自定义队列）：你可以创建串行或并行队列。实际上，归根到底它最后还是由一个全局队列来处理。（These actually trickle down into being handled by one of the global queues.）

   当设置一个全局并发队列，你不能直接指定它的优先级。但你可以指定一个 Quality of Service(Qos) 的类属性。它将表明任务的重要性并给GCD决定这个任务的优先级提供参考。

Qos 类别有：

• User-interactive：这个表示任务必需立刻完成，从而提供一个比较好的用户体验。使用它来更新 UI，事件处理以及低延迟且较小的工作量。在这个类里，所有的工作在你的 app 执行期间应该比较小。这些应该运行在主线程上。

• User-initiated：这个表示从 UI 初始化的任务并可以异步执行。它应该被用于用户等待的结果需要立刻返回，或需要持续交互的任务。它将被映射到高优先级的全局队列。

• Utility：这个表示长时间运行的任务，典型的会有用户可视进度指示器。使用它来计算，I/O，网络，连续的数据提供以及类似的任务。这个类被设计为高能耗。它将被映射到低优先级的全局队列。

• Background：这个表示用户并不会直接查觉到的任务。使用它来 prefetching（预获取），维护以及其他不需要用户交互与时间不敏感的任务。它将被映射到 background 优先级的全局队列。

Synchronous（同步） vs. Asynchronous（异步）

使用 GCD，你可以 dispatch（调度）一个同步或异步任务。

一个同步函数控制着调用者在任务完成后返回。

一个异步函数立即返回，任务会按顺序开始，但不会等待任务完成。 因此，一个异步函数不会堵塞当前线程继续执行下一函数。

Managing Tasks

关于 tasks（任务）你现在已经知道比较多了。出于这篇教程的目的你应该考虑用 closure 为 task。Closures 是 self-contained（自包含），代码回调 blocks，它可以被存储或做为参数传递。

使用 DispatchWorkItem 来封装 Tasks 提交到 DispatchQueue 中。你可以配置 DispatchWorkItem 的行为，例如 QoS 类或者产生一个新的独立线程。

处理后台任务

知道了这么多 GCD 知识后，是时候用来改善你的 app 了。

回到 app 并通过你的 Photo Library 或者使用 Le Internet选项来下载几张图片。点击图片。注意一下 Photot DetailVC 要多久才能显示出来。当在较慢的设备上展示较大的图片时，延迟是非常显示的。

重载 View Controller 的 viewDidLoad() 方法容易导致在View展示之前有较长的等待。如果一些任务在加载时是非必要的，那么可以将这些任务放在后台执行。

这听上去好像是DispatchQueue的 async 的工作！

打开 PhotoDetailViewController.swift。修改 viewDidload() 并替换这两行代码：

1
2

let overlayImage = faceOverlayImageFromImage(image)
fadeInNewImage(overlayImage)

使用下面的代码：

1
2
3
4
5
6

DispatchQueue.global(qos: .userInitiated).async { // 1
  let overlayImage = self.faceOverlayImageFromImage(self.image)
  DispatchQueue.main.async { // 2
    self.fadeInNewImage(overlayImage) // 3
  }
}

我们一步一步来解释这些代码做了什么：

1. 你将work移动到后台全局并在异步闭包中运行 work。这让 viewDidLoad() 在主线程上提前完成并使用加载感觉更简短。此时，人脸识别处理已经开始并将在晚一点的时候完成。
2. 这个时候，人脸识别处理已经完成并生成新的图片。由于你想用这张新图片来更新你的 UIImageView，你添加一个新的闭包到主线程队列。记住——你访问 UIKit 的类的时候，必须始终在主线程上。
3. 最后，你调用fadeInNewImage(_:)更新UI，该方法执行渐入效果添加新的googly eyes图片。

Build 并运行 app。通过 Le Internet 选项下载一些图片。选择一张图片，你会注意到 view controller 加载的速度明显并快并且在稍候添加一些 googly eyes 上去。

This lends a nice before and after effect to the app as the googly eyes are added. 甚至，如果你尝试去加载一张更大的图片，app 不会挂起 view controller 同样会加载完成。

通常，当你需要执行一个在后台中的 network-based （基于网络）或CPU intensive 的任务且并不会阻塞当前线程时，你将会想到使用 async。

这里有一份怎样使用、什么时候使用 async 的几种队列的快速指南：

• MainQueue：当在并发队列上的一个任务完成时，通常会选择这个队列去更新UI。为此，你将编写一个 closure 嵌入到其他队列中。定位到主线程队列并调用 async 确保这个新的任务将在当前方法完成后的某个时间执行。
• GlobalQueue：这个通常使用在非 UI 工作的后台中。
• Custom Serial Queue：非常好的选择，当你想执行一连串的后台工作或追踪它时。由于同一时间只能执行一个任务，所以它消除了争抢资源的问题。注意，如果你想从一个方法中获取数据，你必须使用内联的 closure 来获取或者考虑使用 sync。

Delaying Task Execution（延迟任务执行）

DispatchQueue 允许你延迟任务的执行。Care should be taken not to use this to solve race conditions or other timing bugs through hacks like introducing delays. 当你希望任务在指定时间运行时使用它。

先思考一下你的 app 的用户体验。当用户第一次打开app时，他们有可能会困惑这个 app 是干什么用的，不是吗？

如果在没有图片的情况下，给予用户一些提示会是一个不错的主意。你同样应该考虑到用户的视线是怎样导航首页的。如果提示过早，他们可能没注意到。1秒钟的时间延迟提示信息应该可以足够的引起用户的注意以及引导他们。

打开PhotoCollectionViewController.swift并在showOrHidNavPromp()中实现以下代码：

1
2
3
4
5
6
7
8
9

let delayInSeconds = 1.0 // 1
DispatchQueue.main.asyncAfter(deadline: .now() + delayInSeconds) { // 2
  let count = PhotoManager.sharedManager.photos.count
  if count > 0 {
    self.navigationItem.prompt = nil
  } else {
    self.navigationItem.prompt = "Add photos with faces to Googlyify them!"
  }
}

解释一下上面的代码：

1. 你指定了一个需要延迟多少时间的变量。
2. 你然后等待指定的时间，然后异步运行更新图片数量和提示信息的 block。

showOrHidNavPrompt() 在 viewDidLoad()中执行并用任意时刻UICollectionView重新加载。

Build 并运行 app。在提示信息显示之前应该有较小的延迟：

那什么情况下使用 asyncAfter 呢？通常情况下，在主队列中使用是比较好的选择。如果在全局后台队列或自定义串行队列中使用的放，你要多加小心。你最好还是坚持在主队列中使用。

为什么不使用 Timer 呢？如果你有重复的任务并容易按照预定时间执行，那么你应该考虑使用它。这里有两点原因支撑使用 asyncAfter。

第一是可读性。使用 Timer 你需要定义一个方法然后创建一个带selector或 invocation 的 timer。而 DispatchQueue 与 asyncAfter 你只要简单的添加一个closure。

Timer 是 scheduled 在 runloop 上，所以你必需确保它是 scheduled 在runloop上的，你想要开启的（在正确 runloop modes 的情况下）。就这一点而言，使用asyncAfter就非常简单了。

Managing Singletions（管理单例）

单例。爱并恨着，它们在iOS中很普遍，就像猫的图片在web上一样。:]

单例的一个常见的问题是它们通常不是线程安全的。鉴于使用它们，这种担心也是合理的：单例通常是被多个控制器在同一时间访问单一实例。你的 PhotoManager 类就是一个单例，所以你需要考虑这一问题。

线程安全的代码在多线程或并发任务调用时是安全的，不会出现数据腐化（data corruption）或者导致app崩溃的问题。如果代码不是线程安全的，那么它在同一时间只能在一个上下文中运行。

这里有两种线程安全情况需要考虑，单实例初始化过程中以及实例对象读写过程中。

初始化的情况实现起来比较简单，因为有 Swift 管理初始化全局变量。当全局变量第一次访问后，它们将被实例化，并且保证它们是以 atomic 的方式被初始化。也就是说，代码执行初始化是经过临界区（critical section）处理的并且保证在其他任意线程访问全局变量之前完成。

一个临界区（critical section）是不会并发执行的一段代码，也就是说，两个线程不能在同一时间执行的代码。这是比较常见的，因为一段代码维护一个共享资源，比如一个变量，如果使用并发进程访问的话这个变量将腐化（corrupt）掉。

打开PhotoManager.swift，来看看单例是怎样被初始化的：

1

private let _sharedManager = PhotoManager()

这个私有的全局变量 _sharedManager 被使用到了 PhototManager 懒加载初始化里。正如下所示，它只有在第一次访问时执行：

1
2
3

class var sharedManager: PhototManager {
  return _sharedManager
}

这个公开的sharedManager变量返回了私有的 _sharedManager 变量。Swift 会确保这一操作是线程安全的。

当访问单例中共享内部数据代码时，你仍然需要处理线程安全问题。你可以通过使用例如 synchronizing 数据访问的方法来处理它。你将在下一章节中看到一种解决方案。

Handling the Readers-Writers Problem（处理读者-写者问题）

在Swift中，使用 let 关键字定义的任意变量都会被识别为常量并且是只读与线程安全的。然而使用 var 关键字定义的变量，为可变的并且非线程安全的，除非是被设计过的数据类型。当Swift集合类型如 Array、Dictionary 被定义为可变时，它们是非线程安全的。

虽然多个线程同时读一个可变数组时没有问题，但当有一个线程在修改这个线程时而其他线程在读时是非线程安全的。在当前的状态中，你的单例并不会阻挡这种状况的发生。

来看下这个问题，看一下 PhotoManager.swift 中的 addPhoto()，它被复制到下面：

1
2
3
4
5
6

func addPhoto(_ photo: Photo) {
  _photos.append(photo)
  DispatchQueue.main.async {
    self.postContentAddedNotification()
  }
}

这是一个write方法，它修改了可变数组对象。

现在看一下photos属性，如下：

1
2
3
4

fileprivate var _photos: [Photo] = []
var photos: [Photo] {
  return _photos
}

这个属性的 getter 方法被称为 read 方法，读这个可变数据。调用者获取这个数组的复本并且没有合适的保护原来的数组。当一个线程调用写方法 addPhoto() 同时其他线程在调用 photos 属性的 getter 方法时，这里并没有提供任务保护措施。

Note: 在上面的代码中，为什么说调用者获取是这个数组的复本呢？在 Swift 中，参数与函数的返回类型是传递引用类型或值类型。

传递的复本对象是值类型话，修改复本是不会影响原始对象的。在Swift中，默认情况下class实例是引用类型，结构体是值类型。Swift 内置的数据类型，比如 Array 与 Dictionary 是采用结构体实现的。

当反复的传递集合类型时，它们看起来会产生大量的复本。不需要担心关于内存使用的问题。Swift 的集合类型是经过性能优化过的，只有在必要的情况下才会复制，例如当经过值传递的数组在通过后第一次被修改。(for instance when an array passed by value is modified for the first time after being passed.)

这就是经典的软件开发读者-写者问题。GCD提供了一个优雅的解决方案，就是使用 dispatch barriers 创建一个read/write lock。Dispatch barriers 是一个函数组，当运行在并发队列上时，它相当于serial-style的瓶颈。

当你将 DispatchWorkItem 提交到一个 dispatch queue 时，你可以设置 flags 来指示它应该是指定排列的特定时间上的唯一任务。这意味着已经所有提到队列的任务必须在 dispatch barrier 执行DispatchWorkItem之前完成。

当 DispatchWorkItem 到达时，barrier 会执行它并确保该任务运行期间不会执行队列中的其他任务。一旦执行完毕，该队列将恢复到默认实现状态。

下图描述了 barrier 任务对其他多个异步任务的影响：

注意这个队列的常规操作就像一个正常的并发队列。但是，当 barrier 执行期间它就像一个串行队列。也就是说，barrier 只执行唯一的任务。等 barrier 完成后，该队列将恢复为一个正常的并发队列。

当在全局后台队列中使用 barrier 时要小心，因为这些队列是资源共享的。在串行队列中使用 barrier 是多余的，因为它已经是串队执行。在自定义并发中使用 bairrer是很好的选择，它可以处理临界代码原子性的线程安全。

你将使用一个自定义并发队列来处理你的 barrier 函数与分隔读与写函数。该并发队列允许你进行并发读操作。

打开 PhototManager.swift 并在 _photots 上添加一个私有属性：

1
2
3
4

fileprivate let concurrentPhotoQueue =
  DispatchQueue(
    label: "com.raywenderlich.GooglyPuff.photoQueue", // 1
    attributes: .concurrent) // 2

这里将 concurrentPhotoQueue 初始化为并发队列。

1. 你设置了 label 描述名称，在 debug 时它非常在用。一般情况下，你会使用颠倒的 DNS 来命名；
2. 你指定它为并发队列。

下一步，使用以下代码覆盖 addPhoto(_:) 方法：

1
2
3
4
5
6
7
8

func addPhoto(_ photo: Photo) {
  concurrentPhotoQueue.async(flags: .barrier) { // 1
    self._photos.append(photo) // 2
    DispatchQueue.main.async { // 3
      self.postContentAddedNotification()
    }
  }
}

以下是这个函数的解释：

1. 你 dispatch 这个异步写操作为 barrier。当它执行时，它将成为你的队列中的唯一 item；
2. 你将 photo 对象添加到数组；
3. 最后你发送了 photo 被添加的通知。这个通知应该在主线程队列中发送，因为它将会做 UI 更新操作。所以你异步的 dispatch 这个任务到主线程队列来触发这个通知。

这是写方法的实现细节，不过你同样需要实现 photos 的读方法。

为了确保写操作的线程安全，你需要在 concurrentPhotoQueue 上执行读写作。你需要在函数调用时返回数据，而使用异步 dispatch 并不会正常返回。在这种情况下，使用 sync 是个不错的选择。

使用 sync 来追踪你的 dispatch barriers 任务，或者当你使用 closure 进行数据处理之前需要行者之前的任务操作完成。

使用时要尽可能的小心。想像一下，如果你已经运行在当前队列，你又使用 sync 到当前队列。这时将造成 deadlock（死锁）的情况。

两个（或两个以上）items ——通常情况下为线程——如果它们都在等待其他线程完成或执行其他的动作将会产生死锁。第一个不能完成是因为它在等待第二个的运行结束。而第二个不能完成是因为它在等待第一个的结束。

你的情况是，sync 调用将等待直到到 closure 完成，但 closure 不能结束（它甚至都不会开始！）直到当前正在执行的 closure 结束，它结束不了！这使用必须意识到哪些队列应该调用——同样的，哪些队列你可以调入。（原文：This should force you to be conscious of which queue you’re calling from — as well as which queue you’re passing in.）

以下简短的总结了什么情况下使用 sync：

• Main Queue：非常小心！与上面同样的原因；这种情况会隐患的产生死锁；
• Global Queue：这是好的选择，使用 sync 搭配 dispatch barriers时或当行等待一个任务完成后再更进一步的处理数据；
• Custom Serial Queue：这种情况时要非常小心！如果你运行在一个队列中并且你调用 sync 到同一队列中时，你明显的创建了一个死锁。

仍然，在 PhotoManager.swift 中修改 photos 属性的 getter：

1
2
3
4
5
6
7

ar photos: [Photo] {
  var photosCopy: [Photo]!
  concurrentPhotoQueue.sync { // 1
    photosCopy = self._photos // 2
  }
  return photosCopy
}

解释上面的代码：

1. 使用同步 Dispatch 到 concurrentPhotoQueue执行读操作；
2. 保存 photo 数据的副本到 photosCopy 并作为返回值返回。

Build 并运行 app。使用 Le Internet下载图片。它应该跟之前一样，但这次你使用一些有趣线程来实现它。

恭喜！现在你的 PhotoManager 是线程安全的了。不管理你怎样去读或写操作图片，你可以自信的确保不会出现任何意外，安全的方式完成。

接下来做什么？

在这篇教程中，你学习了怎样让你的代码线程安全与在 CPU 执行比较密集任务的情况下，如果维护主线程的响应灵敏。

你可以下载完整的代码 completed project，它包含了所有的代码改善。在第二部分教程中你将继续改善这个项目。

如果你计划改善你自己的 app，你应该使用 Instruments 中的 Time Profile 模块进行测试。使用这些工具是本教程的范畴之外，你可以查看 How to Use Instruments 它很好的介绍了 Instruments。

确保你 profile 的是真实设备，由于在模拟器上测试与你的用户所体验的结果有非常大的区别。

你可能想查看 this excellent talk by Rob Pike 的 Concurrency vs Parallelism。

我们的 iOS Concurrency with GCD and Operations 视频教程系列同样覆盖了多数相关的主题。

在下一篇教程中，你将更加深入的研究一些更酷的 GCD’s API。

组成

分类：

• UIScrollView (DZNEmptyDataSet)
• UIView (DZNConstraintBasedLayoutExtensions)

协议：

• DZNEmptyDataSetSource
• DZNEmptyDataSetDelegate

类：

• DZNEmptyDataSetView
• DZNWeakObjectContainer

UIScrollView (DZNEmptyDataSet)

使用运行时添加的属性：

• emptyDataSetSource
• emptyDataSetDelegate
• isEmptyDataSetVisible

使用runtime Swizzling为reloadData添加方法：

• dzn_reloadEmptyDataSet

  即当tableView或collectionView 调用reloadData方法时会执行dzn_reloadEmptyDataSet。这是整个框架的核心方法。

dzn_reloadEmptyDataSet方法

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

- (void)dzn_reloadEmptyDataSet
{
  	//1.是否能显示 empty dataset view
    if (![self dzn_canDisplay]) {
        return;
    }
    
  	//2.一、询问emptyDataSetDelegate是否应该显示  二、itemsCount是否为0：tableView根据tableView:numberOfRowsInSection方法，collectionView根据 collectionView: numberOfItemsInSection:方法
    if (([self dzn_shouldDisplay] && [self dzn_itemsCount] == 0) || [self dzn_shouldBeForcedToDisplay])
    {
      	//3.创建empty dataset view(空数据View)
        // Notifies that the empty dataset view will appear
      	//3.1通知emptyDataSetDelegate代理，dataset view即将显示
        [self dzn_willAppear];
      
        //3.2 创建
        DZNEmptyDataSetView *view = self.emptyDataSetView;
        
        if (!view.superview) {
          	//3.3添加到ScrollView
            // Send the view all the way to the back, in case a header and/or footer is present, as well as for sectionHeaders or any other content
            if (([self isKindOfClass:[UITableView class]] || [self isKindOfClass:[UICollectionView class]]) && self.subviews.count > 1) {
                [self insertSubview:view atIndex:0];
            }
            else {
                [self addSubview:view];
            }
        }
        
      	//3.4 清理，重置约束以
        // Removing view resetting the view and its constraints it very important to guarantee a good state
        [view prepareForReuse];
        
      //3.5 添加你提供的自定义View
        UIView *customView = [self dzn_customView];
        
        // If a non-nil custom view is available, let's configure it instead
        if (customView) {
            view.customView = customView;
        }
        else {
            // Get the data from the data source
           //3.6 根据emptyDataSetSource提供的数据，配置空数据View的子View
          //具体代码太长，为避免干扰省略
        
          //3.7 通知emptyDataSetDelegate 空数据View已显示
        // Notifies that the empty dataset view did appear
        [self dzn_didAppear];
    }
    else if (self.isEmptyDataSetVisible) {
      	//4.空数据View清除操作
        [self dzn_invalidate];
    }
}

原文：Insertion sort

插入排序

目标：排序一个数组从底到高（或从高到底）。

给你一个数字数组并需要把它们排成正确的顺序。插入排序算法的工作步骤：

• 把所有的数字放到堆中。这个堆是无序的；
• 从堆中取出一个数字。取哪个数字都无所谓，但最简单的做法是从堆顶取；
• 把这个数字插入到新的数组中；
• 从无序堆中取出下一个数字并同样的插入到数组中。它在第一个被选出来的数字的前面或者后面，这样这两个数字排好序了；
• 再次，从无序堆中取出数字插入到新数组相应的有序位置；
• 不断重复直到无序堆中没有任何数字。堆为空时结束，并数组也排好序了。

这就是为什么被称为“插入”排序的原因，因为你从堆中取出一个数字然后把它插入到数组中相应的有序位置。

例子

比如说，这是一个需要排序的[8, 3, 5, 4, 6]。这是我们的无序堆。

取出第一个数字，8,并插入到新数组。这个数组中什么都没有，所以这步很简单。现在这个有序数组为[8]，堆为[3, 5, 4, 6]。

从堆中取出下一个数字，3，并且插入到有序数组中。它应该放在8前面，所以有序数组现为[3, 8]，堆为[5, 4, 6]。

从堆中取出下一个数字，5，并且插入到有序数组中。它应该放在3 与8之间。有序数组为[3, 5, 8]，堆为[4, 6]。

重复这个过程直到堆为空。

In-place（就地） 排序

上面的解释使它看起来好像你需要两个数组：一个是无序堆，另一个用来装排好序的数字。

不过你可以In-place（就地）排序，不需要额外的数组。你只要记录哪部分是已经排好序的数组和哪部分是未排序的堆。

开始时，这个数组是[8, 3, 5, 4, 6]。这|竖线显示在排好序部分的末端，在无序堆的首端：

1

[| 8, 3, 5, 4, 6]

上面显示了排序部分为空，而无序堆从8开始。

处理第一个数字后，变为：

1

[8 | 3, 5, 4, 6]

排序部分是[8]，无序堆为[ 3, 5, 4, 6 ]。|竖线向右挪了一位。

下面展示了在排序过程中数组内容的变化：

1
2
3
4
5
6

[| 8, 3, 5, 4, 6 ]
[ 8 | 3, 5, 4, 6 ]
[ 3, 8 | 5, 4, 6 ]
[ 3, 5, 8 | 4, 6 ]
[ 3, 4, 5, 8 | 6 ]
[ 3, 4, 5, 6, 8 |]

每一步，|都向后移动一步。正如你所看到的，数组起始到|之简的部分都排好序的。无序堆减一，而排序部分增一。直到无序堆为空，不再有无序数字可移动。

怎样插入

每一步，你取出无序堆最前面的数字，然后插入到排序数组部分中。你必须把这个数字放到排序部分的合适位置。这一步怎么做呢？

比如说，我们已经完成了前面几步，然后数组就像这样：

1

[ 3, 5, 8 | 4, 6 ]

下一个要排序的数字是4。我们需要把它插入到排序部分[ 3, 5, 8 ]数组的某位置。

这里有一个方法可以实现它：查看前一个元素，8。

1
2

[ 3, 5, 8, 4 | 6 ]
        ^

是否大于4？大于，所以4应该在8的前面。交换它们的位置得到：

1
2
3

[ 3, 5, 4, 8 | 6 ]
        <-->
        交换后

还没完。前面的新元素，5，又大于4。同样的，交换它们：

1
2
3

[ 3, 4, 5, 8 | 6 ]
     <-->
    交换后

再次，查看前面的元素。3大于4？不大于，这意味着4已经完成操作。开始部分的数组又变为有序了。

这是内循环插入排序算法的描述，你会在下一章看到。它采用数字交换的方法，把数字从截头部插入到有序部分。

代码

这里采用Swift实现插入排序：

1
2
3
4
5
6
7
8
9
10
11

func insertionSort(_ array: [Int]) -> [Int] {
  var a = array	//1
  for x in 1..<a.count {	//2
    var y = x							
    while y > 0 && a[y] < a[y-1] {	//3
      swap(&a[y-1], &a[y])
      y -= 1
    }
  }
  return a
}

使用Playground测试上面的代码，例如：

1
2

let list = [10, -1, 3, 9, 2, 27, 8, 5, 1, 3, 0, 26 ]
insertionSort(list)

这里解释下，上面的代码怎么运行：

1. 复制array。这一步是必须的，因为我们不能直接修改参数变量array。就像Swift自带的sort()，insertionSort()函数将返回原始数组复制后的排序数组。
2. 这里有两个循环在这个函数中。外循环依次查询数组中的所有元素；用来从堆中取出最上面的数字。x变量用来标识排好序部分的结尾与堆起始位置（即|的位置）。记住，任何时刻，数组的起始 — 从0到x — 总是排好序的。剩余的，从x到最后一个元素，是无序堆。
3. 内循环从x下标的元素开始。这是堆最顶端的数字，它可能小于前面所有元素。内循环一步步向后通过排序数组；每次查找前一个元素是否大于它，如果大于则交换位置。当内循环完成后，数组起始部分们又变成有序了，并且有序部分增加一个元素。

注意： 外循环从下标1开始而不是0。移动第一个元素从堆到排序部分，没有发生实质的变化，所以我们跳过了它。

去掉交换

上面的版本工作的很好，不过可以删除swap()来提升一些速度。

你已经知道，我们通过交换数字来移动下一个元素到排序位置：

1
2
3
4
5
6
7

[ 3, 5, 8, 4 | 6 ]
        <-->
        交换
        
[ 3, 5, 4, 8 | 6 ]
     <-->
     交换

替代的做法是，我们只要向右挪动这些元素一个位置，然后复制一个新数字到目标位置即可：

1
2
3
4
5
6
7
8
9
10
11

[ 3, 5, 8, 4 | 6 ]   记住 4
           *
[ 3, 5, 8, 8 | 6 ]   把 8 向右挪动
        --->
        
[ 3, 5, 5, 8 | 6 ]   把 5 向右挪动
     --->
     
[ 3, 4, 5, 8 | 6 ]   复制 4 到这个位置
     *

在代码中，就像这样：

1
2
3
4
5
6
7
8
9
10
11
12
13

func insertionSort(_ array: [Int]) -> [Int] {
  var a = array
  for x in 1..<a.count {
    var y = x
    let temp = a[y]
    while y > 0 && temp < a[y - 1] {
      a[y] = a[y - 1]                // 1
      y -= 1
    }
    a[y] = temp                      // 2
  }
  return a
}

//1行的代码是挪动前一个元素一个位置。在内循环的最后，y是新元素插入到有序数组部分的目标位置，//2行表示复制这个数字到目标位置。

增加泛型

如果可以用来排序其他类型，那就更好了。我们可以给数组的数据类型添加泛型并使用用户提供（user-supplied）函数（或闭包）去执行小于号比较，这只需要改变函数中两个地方。

函数的参数签名变为：

1

func insertionSort<T>(_ array: [T], _ isOrderedBefore: (T, T) -> Bool) -> [T] {

数组为类型[T],T表示通用的占位类型。现在insertionSort()函数可以接受任何类型的数组了，无论它包含数字，字符串，或者其他对象。

新参数isOrderedBefore: (T, T) -> Bool是一个函数，这个函数比较两个T对象，当第一个对象在第二个对象前面时返回true，相反时，返回false。这跟Swift内置函数sort()的做法一样。

其他只要改变的地方在内循环中，现在改为：

1

while y > 0 && isOrderedBefore(temp, a[y-1]) {}

我们调用isOrderedBefore()函数来替换temp < a[y-1]。这样是完全相同的，除了我们现在可以比较任何类型的对象，不仅仅只是数字。

在playground中做如下测试：

1
2
3

let numbers = [ 10, -1, 3, 9, 2, 27, 8, 5, 1, 3, 0, 26 ]
insertionSort(numbers, <)
insertionSort(numbers, >)

<与>决定排序顺序，相当于底-高，高-底。

当然，你也可以使用其他对象进行排序，比如字符串：

1
2

let strings = [ "b", "a", "d", "c", "e" ]
insertionSort(strings, <)

或者，较复杂的对象：

1
2

let objects = [ obj1, obj2, obj3, ... ]
insertionSort(objects) { $0.priority < $1.priority }

闭包告诉insertionSort()函数，使用对象的priority属性来排序。

插入排序是稳定排序。稳定排序是指当元素中有相同的元素，当排序完成后相同元素将保持原有的顺序。这不是很重要，对于简单值来说，比如：数字和字符串，不过对于较复杂的对象来说非常重要。在上面的例子中，如果两个对象有相同的priority，不管他们的属性的值是多少，他们都不会交换位置。

性能

如果是已经排好序的数组那么插入排序非常的快。这听起来显而易见，不过这对于所有的搜索算法来说不太正确。在实际情况中，大部分数据已经排好序了，所以在这种情况下，插入排序工作的不错。

插入排序的最坏和平均的时间复杂度为O(n^2)。因为函数中有两个嵌套循环。其他排序算法，比如快速排序与合并排序的时间复杂度为O(n log n)，它们输入数据很快。

在排好序的小数组使用插入排序是非常快的。有些标准库中，当数组分配粒度为10或更小时，使用插入排序代替快速排序。

我做过一个快速测试，来比较我们的insertionSort()与Swift内置的sort()。使用大小大约为100的数组，它们的时间花费差距非常小。然而，如果你输入一个比较大的数组，O(n^2)比O(n log n)开始有非常大的性能差距，并且插入排序不能工作。

参考阅读

Insertion sort on Wikipedia

Written for Swift Algorithm Club by Matthijs Hollemans

原文：What are algorithms and data structures?

算法与数据结构是什么？

算法就是计算机做事的食谱。如果你会下厨，则懂算法！

这里有一个煎饼的食谱：

1. 将面粉、发酵粉、盐与糖倒入大碗盆中和匀；

2. 倒入牛奶、鸡蛋与黄油；

3. 搅拌和匀；

4. 加热煎饼锅至中等热；

5. 用勺将面糊放至锅中，每个饼使用大概1/4杯的量；

6. 将饼两面煎至微黄。

食谱由这些一条条连续的步骤组成。算法也是如此，除了包含一些计算机执行指令，而烹调没有。

原料 — 面粉、牛奶、鸡蛋、黄油 — 是算法要使用的数据。数据进入算法是一种形式（不成熟，分开的原料），出去是另一种形式（美味的煎饼！）。

所以，什么是数据结构呢？数据结构是用来装算法用到的数据的容器。在煎饼食谱中，数据结构是装面粉的袋子、搅拌用的大碗盆、把饼煎黄的煎饼锅以及最后用来装煎完了的饼的盘子。

原文：https://www.bodybuilding.com/exercises/detail/view/name/seated-triceps-press

类型：力量

锻炼主要肌肉：肱三头肌

器械：哑铃

级别：入门

坐姿肱三头肌推举图

指南

1.坐在有背部支撑的训练椅上并双手抓起哑铃举过头顶、手臂伸直。Tip:此动作最好让朋友帮忙，尤其哑铃比较重时。你的双手应该握住哑铃片，这时你的手掌应该朝前，这将是起始位置。

2.保持你的上臂与头部靠近并与地板成直角（手肘朝内），控制哑铃在头部后向下直至前臂碰到二头肌，同时吸气。Tip：上臂应该保持直线并只移动前臂。

3.使用肱三头肌的力量举起哑铃到起始位置，同时呼气。

4.重复训练推荐的重复次数。

主要肌肉

原文：https://github.com/raywenderlich/swift-algorithm-club/tree/master/Stack

堆栈

堆栈就像数组，不过功能有限。你只能通过Push添加一个新元素到堆栈的顶部，使用Pop从栈顶删除元素，可以不用Pop一个元素来查看栈顶的元素。

你为什么要这样做呢？是这样的，在很多算法中你想在某一时间段添加一些对象到一个临时数组，然后晚些时候又把这些对象从数组中拉出来。通常顺序是处决于你添加与删除对象情况。

一个堆栈给你一个后进先出或LIFO的顺序。最后Push进来的元素，第一个被Pop出来。（一个非常相似的数组结构，队列，先进先出 或者 FIFO）。

举个例子，让我们Push一个数字到堆栈：

1

stack.push(10)

这个堆栈现在是[10]。Push下一个数字：

1

stack.push(3)

这个堆栈现在是[10, 3]。再Push一个数字：

1

stack.push(57)

这个堆栈现在是[10, 3, 57]。让我们从栈顶Pop出一个数字：

1

stack.pop()

返回值为57。因为它是最近Push到栈中的。堆栈又变为[10, 3]。

1

stack.pop()

这时返回值为3，诸此类推。如果这个堆栈为空，将返回nil或者是给定实现的错误信息（’stack underflow’）。

用Swift实现一个堆栈很简单。底层用一个数组封装，可以让你Push、Pop、查看栈顶元素：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

publich struct Stack<T> {
  fileprivate var array = [T]()
  
  public var isEmpty: Bool {
    return array.isEmpty
  }
  
  public var count: Int {
    return array.count
  }
  
  public mutating func push(_ element: T) {
    array.append(element)
  }
  
  public mutating func pop() -> T? {
    return array.popList()
  }
  
  public var top: T? {
    return array.last
  }
}

注意Push是将一个元素添加到数组尾部，而不是首部。插入到数组首部开销非常大的，为O(n)操作，因为这样操作必须挪动数组中所有已存在元素的内存地址。而添加到数组尾部是O(1)操作；这样做，不管理数组大小，所花时间都是同样的。

一个关于堆栈的有趣事实：你每次调用函数或方法时，CPU会把返回地址放置在堆栈上。当函数结束时，CPU会使用这个返回跳回到调用者。这就是为什么你调用太多函数方法时（举个例子在递归函数中它永远不结束）你会得到一叫“stack overflow” 就是CPU运行空间不足。

写自 Swift Algorithm Club 的 Matthijs Hollemans