数据结构复习（3）

第三章——线性数据结构

栈

身为 ACMer，其它基本也不用花太多时间记，只需要记一些没有见过的概念就差不多了。基本特性就是先进后出，常见应用就是函数调用，深度优先搜索（迷宫算法），递归函数，括号匹配，表达式扫描。

n 个不同的元素入栈，得到不同出栈结果的个数。

结论：$\frac{1}{n+1}C_{2n}^n$

指两个栈共用一个大数组，其中一个栈顺序增长，另一个栈反方向增长，更大程度避免上溢出，两个栈顶重叠的时候，栈满。

只允许从一端插入，另一端删除，先进先出。

有两种情况需要细致考虑：一个是头指针指向队尾元素，一个是头指针指向队尾的后一个位置，这两个情况略微有差别，此时队列判空判满的条件也有差别。

队头一般使用 head 或者 front，队尾一般使用 tail 或者 rear 变量。为了防止假溢出，出现了循环队列，但是要注意，循环队列需要牺牲一个单元，否则无法判断队满或者队空，因为它们的指针指向一模一样。

开放了其中一端插入或者删除，或者都开放。

做这个题目的时候，一般会出现输入限制或者输出限制的双端队列，然后问你，哪项出队顺序不符合或者符合。其实很简单，一端可以插入删除，那其实相当于是栈了，只不过在栈底也可以插入（或删除，不能同时）数据而已。

栈可以进行括号匹配，表达式求值，递归等等。

队列可以进行层次遍历以及操作系统有很多请求是需要用到队列的。

讲了三种特殊的矩阵以及存储方式。

指的是当矩阵中非 0 元素的个数远远小于矩阵的容积时的矩阵。此时为了节省空间，可以使用三元组或者是十字链表法存储稀疏矩阵。

三元组就是存储行，列值，此时空间复杂度就跟非零元素的个数有关了。

十字链表就是跟存图差不多的道理。有一行和一列的指针，行指针指向了那一行的第一个非零元素，然后用链表连接起来。列指针指向了那一列的第一个非零元素，然后通过链表连接那一行的下一个非零元素和那一列的下一个非零元素，仅此而已。

对称矩阵指的是与主对角线相关元素值相同的矩阵，此时可以选择存一半，存上三角或者下三角的元素，把它压缩到一个一维数组中去。

指的是主对角线和主对角线上下两条对角线上有元素，其余元素为 0 的矩阵，此时可以按行或者按列使用一维数组存储这个三对焦矩阵。