队列和双端队列的比较

队列(queue)是一种是相对于栈的一种数据结构，它是先进先出(First In First Out)。
它只可以在尾部添加元素。

双端队列(deque double ended queue（双端队列）)是一种相对于队列的一种数据结构。它可以在尾部和头部插入、移除和获取。

三者成员函数的比较

通过他们各自的成员函数我们能一目了然的看出区别

栈的成员函数

• stack<Type> s : 定义一个stack的变量
• s.push(x) : 入栈，如例
• s.pop() : 出栈，如例 . 注意，出栈操作只是删除栈顶元素，并不返回该元素。
• s.top() : 访问栈顶，如例
• s.empty() : 判断栈空，如例，当栈空时，返回true。
• s.size() : 访问栈中的元素个数，如例

队列的成员函数

• queue<Type> M : 定义一个queue的变量
• M.empty() : 查看是否为空范例 是的话返回1，不是返回0;
• M.push() : 从已有元素后面增加元素
• M.size() : 输出现有元素的个数
• M.front() : 显示第一个元素
• M.back() : 显示最后一个元素
• M.pop() : 清除第一个元素

双端队列的成员函数

• deque<Type> c : 定义一个deque的变量
• c.pop_back() : 删除最后一个数据。
• c.pop_front() : 删除头部数据。
• c.push_back(elem) : 在尾部加入一个数据。
• c.push_front(elem) : 在头部插入一个数据。
• c.clear() : 移除容器中所有数据。
• c.front() : 传回地一个数据。
• c.back() : 传回最后一个数据，不检查这个数据是否存在。
• c.size() : 返回容器中实际数据的个数。
• c.empty() : 判断容器是否为空。

有了二叉树的基础, 我们继续学习二叉搜索树.

二叉搜索树的定义

二叉查找树(Binary Search Tree, 简称”BST”), 又名”二叉搜索树”或”二叉排序树”:
它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。

. . .

二叉树的二叉链式存储方案的代码表示：

typedef struct BinTreeNode
{
	BinTreeNode( char Data ) : data_( Data ), left_( nullptr ), right_( nullptr ) {}
	char data_;
	struct BinTreeNode *left_, *right_;
}btn, *btnp;

二叉树的遍历

. . .

接着上一篇， 上一篇主要说了各种排序算法， 但对几个常用的数据结构还未提及，所以这一篇主要讲二叉树, 二叉树已经包括很多链表的知识了。所有代码都是测试过的, 可以直接撸.

二叉树

这里不举太多数字方面的东西， 我们直接看图， 直观感性的认识满二叉树和完全二叉树：

有一点性质需要牢记：具有n个结点的完全二叉树的最大高度为log2n+1

二叉树的二叉链式存储

二叉树的二叉链式存储方案的代码表示：

typedef struct BinaryTreeNode
{
	void *data;
	BinaryTreeNode *LeftNode;
	BinaryTreeNode *RightNode;
}BTN, *BTNP;

. . .

面向对象的四大特征

• 封装：
  封装是把过程和数据包围起来，对数据的访问只能通过已定义的界面，面向对象计算始于这个基本概念，即现实世界可以被描绘成一系列完全自治，封装的对象，这些对象通过一个受保护的接口访问其他对象

• 继承：
  继承是一种联结类的层次模型，并且允许和鼓励类的重用，它提供了一种明确表达共性的方法，对象的一个新类可以从现在的类中派生，这个过程成为继承，新类继承了原始类的特性，新类成为原始类的派生类，而原始类称为新类的基类，派生类可以从他的基类那里继承方法和实例变量，并且类可以修改或增加新的方法使之更加适合特殊的需求

• 抽象：
  抽象就是忽略一个主题中与当前目标无关的那些方面，以便充分的注意与当前目标有关的方面，抽象包括两个方面，一个是过程抽象，二是数据抽象

• 多态性：
  多态性是指允许不同类的对象对同一消息作出响应，多态性包括参数化多态性和包含多态性，多态性语言具有灵活，抽象，行为共享，代码共享的优势，很好的解决了应用程序函数同名的问题

面向对象的五大原则

记忆口诀 : 替开依(“凯隐”, 一个英雄联盟英雄名字)接单

• 单一职责原则（Single-Resposibility Principle）
  其核心思想为：一个类，最好只做一件事，只有一个引起它的变化。单一职责原则可以看做是低耦合、高内聚在面向对象原则上的引申，将职责定义为引起变化的原因，以提高内聚性来减少引起变化的原因。职责过多，可能引起它变化的原因就越多，这将导致职责依赖，相互之间就产生影响，从而大大损伤其内聚性和耦合度。通常意义下的单一职责，就是指只有一种单一功能，不要为类实现过多的功能点，以保证实体只有一个引起它变化的原因。
  专注，是一个人优良的品质；同样的，单一也是一个类的优良设计。交杂不清的职责将使得代码看起来特别别扭牵一发而动全身，有失美感和必然导致丑陋的系统错误风险。

• 开放封闭原则（Open-Closed principle）
  其核心思想是：软件实体应该是可扩展的，而不可修改的。也就是，对扩展开放，对修改封闭的。开放封闭原则主要体现在两个方面1、对扩展开放，意味着有新的需求或变化时，可以对现有代码进行扩展，以适应新的情况。2、对修改封闭，意味着类一旦设计完成，就可以独立完成其工作，而不要对其进行任何尝试的修改。
  实现开开放封闭原则的核心思想就是对抽象编程，而不对具体编程，因为抽象相对稳定。让类依赖于固定的抽象，所以修改就是封闭的；而通过面向对象的继承和多态机制，又可以实现对抽象类的继承，通过覆写其方法来改变固有行为，实现新的拓展方法，所以就是开放的。
  “需求总是变化”没有不变的软件，所以就需要用封闭开放原则来封闭变化满足需求，同时还能保持软件内部的封装体系稳定，不被需求的变化影响。

• 替换原则（Liskov-Substituion Principle）
  其核心思想是：子类必须能够替换其基类。这一思想体现为对继承机制的约束规范，只有子类能够替换基类时，才能保证系统在运行期内识别子类，这是保证继承复用的基础。在父类和子类的具体行为中，必须严格把握继承层次中的关系和特征，将基类替换为子类，程序的行为不会发生任何变化。同时，这一约束反过来则是不成立的，子类可以替换基类，但是基类不一定能替换子类。
  Liskov替换原则，主要着眼于对抽象和多态建立在继承的基础上，因此只有遵循了Liskov替换原则，才能保证继承复用是可靠地。实现的方法是面向接口编程：将公共部分抽象为基类接口或抽象类，通过Extract Abstract Class，在子类中通过覆写父类的方法实现新的方式支持同样的职责。
  Liskov替换原则是关于继承机制的设计原则，违反了Liskov替换原则就必然导致违反开放封闭原则。
  Liskov替换原则能够保证系统具有良好的拓展性，同时实现基于多态的抽象机制，能够减少代码冗余，避免运行期的类型判别。

• 依赖倒置原则（Dependecy-Inversion Principle）
  其核心思想是：依赖于抽象。具体而言就是高层模块不依赖于底层模块，二者都同依赖于抽象；抽象不依赖于具体，具体依赖于抽象。
  我们知道，依赖一定会存在于类与类、模块与模块之间。当两个模块之间存在紧密的耦合关系时，最好的方法就是分离接口和实现：在依赖之间定义一个抽象的接口使得高层模块调用接口，而底层模块实现接口的定义，以此来有效控制耦合关系，达到依赖于抽象的设计目标。
  抽象的稳定性决定了系统的稳定性，因为抽象是不变的，依赖于抽象是面向对象设计的精髓，也是依赖倒置原则的核心。
  依赖于抽象是一个通用的原则，而某些时候依赖于细节则是在所难免的，必须权衡在抽象和具体之间的取舍，方法不是一层不变的。依赖于抽象，就是对接口编程，不要对实现编程。

• 接口隔离原则（Interface-Segregation Principle）
  其核心思想是：使用多个小的专门的接口，而不要使用一个大的总接口。
  具体而言，接口隔离原则体现在：接口应该是内聚的，应该避免“胖”接口。一个类对另外一个类的依赖应该建立在最小的接口上，不要强迫依赖不用的方法，这是一种接口污染。
  接口有效地将细节和抽象隔离，体现了对抽象编程的一切好处，接口隔离强调接口的单一性。而胖接口存在明显的弊端，会导致实现的类型必须完全实现接口的所有方法、属性等；而某些时候，实现类型并非需要所有的接口定义，在设计上这是“浪费”，而且在实施上这会带来潜在的问题，对胖接口的修改将导致一连串的客户端程序需要修改，有时候这是一种灾难。在这种情况下，将胖接口分解为多个特点的定制化方法，使得客户端仅仅依赖于它们的实际调用的方法，从而解除了客户端不会依赖于它们不用的方法。
  分离的手段主要有以下两种：1、委托分离，通过增加一个新的类型来委托客户的请求，隔离客户和接口的直接依赖，但是会增加系统的开销。2、多重继承分离，通过接口多继承来实现客户的需求，这种方式是较好的。

2.1.1 :

• C++标准规定的各种算术类型的尺寸的最小值, 同时允许编译器赋予这些类型更大的尺寸. 比如char的最小尺寸为8位

• 执行浮点数运算选用double ，这是因为float 通常精度不够而且双精度浮点数和单精度浮点数的计算代价相差无儿。事实上， 对于某些机器来说，双精度运算甚至比单精度还快

2.1.2 :

• 当我们赋给无符号类型一个超出它表示范围的值时，结果是初始值对无符号类型表示数值总数取模后的余数。例如， 8 比特大小的 unsigned char 可以表示0 至
  255 区间内的值，如果我们赋了一个区间以外的值，则实际的结果是该值对256
  取模后所得的余数。因此，把 -1 赋给8 比特大小的 unsigned char 所得的结果
  是255

• 当我们赋给带符号类型一个超出它表示范围的值时，结果是未定义的( undefined )。
  此时， 程序，可能继续工作、可能崩溃，也可能生成垃圾数据。

• 如果表达式里既有带符号类型又有无符号类型， 当带符号类型取值为负时会出现异
  常结果， 这是因为带符号数会自动地转换成无符号数。例如，在一个形如 a*b 的式子
  中，如果a = -1 , b = 1 ，而且a 和b 都是int ，则表达式的值显然为- 1. 然而，如
  果a 是int ， 而b 是unsigned ， 则结果须视在当前机器上int 所占位数而定。在32环境里，因为2的32次方是4294967296, 所以a*b结果是4294967295

. . .

此文用的是最大堆, 最大堆的堆排序之后的数组是升序, 最小堆反之.
堆排序 HeapSort 由 以下两部分组成 :

• 堆化 MaxHeapify
• 建堆 BuildMaxHeap.

. . .

快速排序

与归并排序一样， 快排也是用了分治的思想。

特别注意 : 快排的核心模块是Partition, 而Partition的复杂度为O(N).

你可以想象一个两副牌然后随意取出一张牌pivot，其他的所有牌都跟这张pivot牌比较，

大的放右边那一摞A，小的放左边B。
接着再从左边这一摞B再随意取出一张牌pivot，其他的所有牌都跟这张pivot牌比较，

大的放右边那一摞，小的放左边，递归下去。
A也重复上述步骤递归。

递归结束之后， 左边的都比右边的小， 而且是有序的。

效率很差的情况

对于分治算法，当每次划分时，算法若都能分成两个等长的子序列时，那么分治算法效率会达到最大。也就是说，基准的选择是很重要的。选择基准的方式决定了两个分割后两个子序列的长度，进而对整个算法的效率产生决定性影响
所以当如果一个有序递增序列, 每次选基准都选最后一个, 那肯定效率很差了啊

算法导论的快排C++实现版本

. . .