-
定义
栈(Stack)是只允许在一端插入或删除元素的线性表。
特点：FILO
栈顶：允许插入/删除的一端。 栈底：固定，不允许插入/删除的一端。 空栈：不包含任何元素的栈。
n个不同元素进栈/出栈共有$\frac{1}{n+1}C_{2n}^{n}$（卡特兰数）种排列方式。
-
基本操作
InitStack(&S) // 初始化栈 StackEmpty(S) // 判空 Push(&S, x) // 进栈 Pop(&S, &x) // 出栈 GetTop(S, &x) // 读取栈顶 DestroyStack(&S)// 销毁栈
-
共享栈
两个栈共享一个一维数组，一个从低地址增长，一个从高地址递减。 此时判空/满为
-
top0 = -1一号空top1 = MaxSize二号空 -
top1-top0=1栈满，即栈顶相邻
-
-
链式存储的栈
第一个元素为栈顶，即等同于在链表上第一个位置进行插入/删除操作。
-
定义
队列（Queue）只允许在一端进行插入，另一端进行删除的线性表。
特点：FIFO
队头：允许删除的一端 队尾：允许插入的一端 空队列：不包含任何元素
-
基本操作
InitQueue(&Q) // 初始化 QueueEmpty(Q) // 判空 EnQueue(&Q, x) // 进队 DeQueue(&Q, &x) // 出队 GetHead(Q, &x) // 读取队头
-
顺序存储
缺点：因为队头和队尾指针不固定，但存储数组是固定的，会导致两个指针不断向数组尾部移动，造成“上溢出”的假象，实际在低地址空间还有存储位置。
-
循环队列
每次入队或者出队都取模，使得指针能够回到低地址。
判空：
-
让队尾不要作为存储单元，此时
队满：(Q.rear+1)%MaxSize == Q.front队空：Q.rear == Q.front -
增加单独的size变量记录个数
-
增加一个tag变量代表是满还是空
当tag=0，且删除时
Q.rear == Q.front，则队空。 当tag=1，且插入时Q.rear == Q.front，则队满。
-
-
链式存储
即保存表头和表尾指针。在表尾增加，在表头删除。
-
双端队列（Deque）
即两边都可以插入/删除。
-
栈在括号匹配中的引用
原理即右括号必须要一个对应的左括号进行匹配。每次遍历左括号则压栈，右括号则取出栈顶并比较。
-
栈在表达式求值的应用
正常书写的表达式为中缀表达式，首先转换为后缀表达式。
转换方式为，对中缀表达式建树，然后按左叶子结点、右叶子结点的顺序递归取出即得后缀表达式。
对于后缀表达式进行遍历，如果是操作数则压栈，是运算符则取出两个数Y和X，进行
X op Y运算并压栈，注意，第一次取的作为被操作数。 -
栈在递归中的应用
递归模型为：
- 递归表达式
- 边界出口
本质就是将大问题分解为属性相同但规模较小的问题。
递归的每一层函数调用/返回本质是一次压栈和出栈。
递归有栈溢出风险，一般效率并不是太高但简单。
-
队列在层次遍历中的应用
要遍历一颗树，要想实现广度优先遍历，即一层一层遍历可以使用队列进行遍历
- 根结点入队
- 若队空则结束遍历，否则出队并检测是否有左右子结点，如果有则入队。
这样可以保证每次遍历的都是同一层元素并且将下一层元素全部入队。
-
队列在计算机系统中的应用
-
解决主机与外部设备速度不匹配的问题
例如缓冲区。
-
解决多用户引起的资源竞争问题
例如OS中的进程调度队列、SPOOLing技术中的等待队列。
-
-
定义
由n个相同类型的数据元素构成的有限序列。
数组是线性表的推广，因为一维数组可以看作线性表，但数组还可以有多维数组
-
存储结构
一个数组所有元素在内存中占用一段连续的存储空间。
$LOC(a_i) = LOC(a_0)+i*L$ 多维数组则有：按行优先和按列优先两种映射方式。
按行优先：每一行接在前一行后面存储，此时存储关系为
$$ LOC(a_{i,j}) = LOC(a_{0,0}) + [i*(h_2+1)+j]*L $$
按列优先：每一列接在前一列后面存储，此时存储关系为
$$ LOC(a_{i,j}) = LOC(a_{0,0}) + [j*(h_1+1)+i]*L $$
其中$(h_1,h_2)$分别表示最大行下标和最大列下标。
-
对称矩阵
$A=A^{T}$ 时，可以使用一维数组存储对角线和下三角（上三角）部分元素即可。以存储下三角为例，此时对应关系为
$$ k = \begin{cases} \frac{i(i-1)}{2} + j - 1,&i\ge j （下三角区和主对角线元素）\ \frac{j(j-1)}{2} + i - 1,&i < j （上三角区域元素a_{ij}=a_{ji}） \end{cases} $$
-
三角矩阵
即上三角或下三角矩阵，只需要存储三角区域和主对角线，以及存储一次另一块三角区域的常量。
以上三角为例
$$ k = \begin{cases} \frac{(i-1)(2n-i+2)}{2} + j - i,&i\le j （上三角区和主对角线元素）\ \frac{n(n+1)}{2},&i > j （下三角区域元素） \end{cases} $$
这里的推导是，第一行包含$n$个元素，第i-1行包含$n-i+2$个元素，所以第i行前元素之和为
$$ \begin{aligned} n + \dots + (n-i+2) &= (n-i+2+n)*(n-(n-i+2)+1)/2\ &= \frac{(2n-i+2)(i-1)}{2} \end{aligned} $$
然后再加上偏移即$j-i$即为最终位置。
-
三对角矩阵
即所有元素在主对角线和两边的三条线上，其他元素为0。存储方式还是和之前一样按行优先存储到一维数组中。
此时
$$ k=2*(i-1) + (j-1) $$
因为除了第一和最后一行，每行都是三个元素，所以第i行前的元素个数为
$$ 3*(i-1) - 1 $$ 而元素在当前行的偏移为$j-i+1$，综合可得任意元素下标为$2(i-1)+(j-1)$。同时如果我们知道$k$逆向计算元素位置时可以让k+1再被3整除即可得到行数，再减去i-1行元素个数即可得到偏移
$$ i = (k+1)/3 + 1\ j = k-(3*(i-1)-1)+i-1=k-2i+3$$
-
稀疏矩阵
即空间非常大，但实际存储的元素很少，此时可以将行列和元素值组成一个三元组进行存储。注意这样存储会导致失去随机存储特性（只能每次遍历找到特定的行列）
这个三元组可以采用数组存储，也可以采用十字链表法存储。