基本数据结构（栈、队列、链表、树、堆）

栈##

栈是一种动态集合，它是一种LIFO（last in first out后进先出）结构
栈的实现：
（1）数组
（2）链表
栈要记录的数据：
（1）栈顶位置top
注意这个top有两种理解方式，一种是表示栈的最后一个数据的位置，另一种是表示栈的最后一个数据的下一个位置，这两种理解对栈的操作代码有一定的影响
（2）栈最大大小size
栈的操作：
（1）STACK_EMPTY（）：判断栈是否为空
（2）PUSH（X）：向栈中添加一个值，注意栈是否为满的
（3）POP（）：从栈中弹出一个值，注意栈是否为空

栈

栈的简要实现：github栈
栈的应用：
（1）括号匹配问题

队列##

与栈不同，它是一种FIFO（first in first out先进先出）结构
队列的实现：
（1）数组
（2）链表
队列要记录的数据：
（1）队首位置head：第一个元素位置
（2）队尾位置tail：下一个元素要插入的位置（最后一个元素的下一个位置）
（3）队列最大大小size
队列的操作：
（1）ENQUEUE（x）：入队
（2）DEQUEUE（）：出队
（3）EMPTY（）：队列为空，head=tail
（4）FULL（）：队列为满，head=（tail+1）%size

队列

队列的简要实现：github队列
队列的应用：
（1）

链表##

与数组中元素地址连续不同，链表中两个元素地址不一定连续，而是由专门的一个指针指明该元素的后一个（前一个）元素的地址。
链表种类：
（1）单向链表：只有指向后一个元素的指针
（2）双向链表：有指向后一个和前一个元素的指针
（3）循环链表：链表内存在一个环
链表节点（Node）记录的数据：
（1）要存储的数据data
（2）下一个节点地址Node* next
（3）若是双向链表还要存储前一个节点地址Node prev
链表（LinkedList）记录的数据：
（1）链表的头指针Node head
（2）可能还记录链表的尾指针 Node* tail
链表的操作：
（1）SEARCH(x)：链表的搜索
（2）INSERT(i,x)：链表的插入，在第i个位置插入x
（3）DELETE（x）:链表的删除
哨兵（sentinel）：
为了减少边界条件的判断（是否为空链表等等），引入哨兵，使得链表永远不为“空”。
指针和对象的实现：
有些语言比如Java没有指针（C中就存在指针），这时我们需要考虑指针的替代实现方式。
（1）用二维数组表示指针
我们可以设置一个n*3的数组记录n个节点，那个3就表示存储的数据、前一个元素的坐标（index）和后一个元素的坐标。
（2）用一维数组表示指针

一维数组代替指针

树##

树的种类：
（1）二叉树
二叉树要存储4个数据，分别是节点携带的信息和其父节点、左右子节点的指针。
（2）分支无限制的有根树：
上面二叉树每个节点最多有两个子节点，而分支无限制的有根数则没有这个限制，可能有3个、5个甚至更多子节点。所以存储这种数据结构的问题在于我们事先并不知道应该设置多少个child指针，若设置的少了不能满足要求，设置的过多又会浪费空间。所以这里提出一种新的描述这种数据结构的方法——左孩子右兄弟表示法，这种方法每个节点设置3个指针：父指针、从左数第一个孩子的指针、其右侧相邻的兄弟指针，如下图所示

左孩子右兄弟表示法

堆##

堆实际上是以数组形式存储的二叉树
堆需要存储的数据:
（1）数组的大小max-size
（2）堆元素个数size，这里size要小于max-size
堆中元素通过坐标来确定父节点、左右子节点，具体来说：
一个节点i的父节点：[i/2]
一个节点i的左子节点：[i2]
一个节点i的右子节点：[i2+1]
堆的分类：
（1）最大堆
满足所有节点都比其父节点值小（小于等于）的堆
A[i/2]>=A[i]
（2）最小堆
满足所有节点都比其父节点值大（大于等于）的堆
A[i/2]<=A[i]
堆的操作：
（1）维护堆的性质（HEAPIFY）
这里指维护最大堆或最小堆的性质。假设一个数组中下标为i的节点的子节点满足最大（小）堆性质，但自身不一定满足这个性质，这时就需要HEAPIFY，具体来说是要比较这个节点和其两个子节点的大小，将其中的大（小）的和该节点位置交换，这样这个节点及其两个子节点就满足最大（小）堆的性质了，但是可能交换后子节点不满足堆的性质，所以这里要递归调用HEAPIFY，直到达到最下层节点，这样就维护了堆的性质。HEAPIFY耗时O（lgn）
（2）建堆（BUILD-HEAPIFY）
从中间那个元素开始到第一个元素，逐一调用HEAPIFY函数，即可完成建堆。
逐一从中间那个元素开始递减而不是从第一个元素递增，这时为了保证每次调用HEAPIFY都能保证该节点的子节点都满足最大（小）堆的性质，否则无法调用HEAPIFY。中间那个元素是第一个可能不满足最大（小）堆性质的节点，所以从这里开始维护（HEAPIFY）。一个建堆的例子如下所示：[5,3,17,10,84,19,6,22,9]

建堆

建堆的期望时间为O（n）

堆的应用:
（1）堆排序（详见排序算法）
（2）优先队列