适配器模式（Adapter）

将一个类的接口，转换成客户期望的另一个接口。适配器让原本接口不兼容的类可以合作无间。

栗子

欧洲的插座大多是三脚的，而美国的插头大多是两脚的，那么如何让两脚插头插进三脚插座里呢？这就需要一个转换头，作为一个中介，二脚插头先插入转换头，然后转换头再插入三脚插座。

还记得笔记1里的鸭子吧？

模版方法模式（Template）

在一个方法中定义一个算法的骨架，而将一些步骤延迟到子类。模版方法使得子类可以在不改变算法结构的情况下，重新定义算法中的某些步骤。

好莱坞原则：别调用（打电话给）我们，我们会调用（打电话给）你。
（由高层组件决定低层组件的行为，而不是反过来）

栗子

现在你有两种冲泡饮料，分别是咖啡和茶。

咖啡的冲泡过程：

1. 把水煮沸
2. 用沸水冲泡咖啡
3. 把咖啡倒进杯子
4. 加糖和牛奶

茶的冲泡过程：

1. 把水煮沸
2. 用沸水浸泡茶叶
3. 把茶倒进杯子
4. 加柠檬

单例模式（Singleton）

确保一个类只有一个实例，并提供一个全局访问点。

应用场景：线程池、注册表、任务管理器、日志对象、充当打印机、显卡等设备的驱动程序等的对象。

命令模式（Command）

将“请求”封装成对象，以便使用不同的请求，队列或日志来参数化其他对象。命令模式也支持可撤销的操作。

栗子

现在有个万能遥控器，它有五个插槽和五对开关按钮。每个插槽可以插一张存储卡，存储卡里面存的是可以控制的某个电器代码，对应的开关按钮可以控制某个电器开关。（听起来这个遥控器有点奇怪是不是？你把它想像成小霸王游戏机就可以了）

你的任务就是给遥控器上的这些开关按钮编程，让它们可以使用存储卡存的电器命令进而控制电器。

工厂模式（Factory）

定义了一个创建对象的接口，但由子类决定要实例化的类是哪一个。工厂方法让类把实例化推迟到子类。

new

按照之前的原则，使用接口，并 new 一个具体实现：

1

Duck duck = new MallardDuck();

但如果出现一堆相关的具体类时，可能会写出这样的代码：

1
2
3
4
5
6
7
8
9

Duck duck;

if (picnic) { // 在野外，是绿头鸭
	duck = new MallardDuck();
} else if (hunting) { // 在打猎，是诱导鸭
	duck = new DecoyDuck();
} else if (inBathTub) { // 在浴缸，是橡皮鸭
	duck = new RubberDuck();
}

一旦有变化或扩展，就要重新打开这段代码进行检查和修改。通常这样修改过的代码将造成部分系统更难维护和更新，而且也更容易犯错。

装饰者模式（Decorate）

动态地将责任附加到对象上。若要扩展功能，装饰者提供了比继承更有弹性的替代方案。

设计原则四：类应该对扩展开放，对修改关闭。

如果使用过 Python，应该听过装饰器，虽然概念有点不同，但都是通过动态添加的方式给对象扩展功能。

快速排序

与归并排序一样，快速排序也使用了分治思想，下面是对一个典型的子数组 A[low … high] 进行快速排序的三步分支过程：

1. 分解：数组 A[low … high] 被划分为两个子数组 A[low … mid - 1] 和 A[mid + 1 … high]，使得 A[low … mid - 1] 中的每一个元素都小于等于 A[mid]，而 A[mid] 也小于等于 A[mid + 1 … high] 中的每个元素。
2. 解决：通过递归调用快速排序，对子数组 A[low … mid - 1] 和 A[mid + 1 … high] 进行排序。
3. 合并：因为子数组都是原址排序的，所以不需要合并操作：数组 A[low … high] 已经有序。

数据结构

栈（stack）

判断空栈：

1
2

stack_empty(S)
	return S.top == 0

压栈：

1
2
3

push(S, x)
	S.top++
	S[S.top] = x

弹栈：

1
2
3
4
5
6

pop(S)
	if stack_empty(S)
		error "underflow"
	else
		S.top--
		return S[S.top + 1]