栈与队列
栈
栈的基本概念
栈是一种只允许在一端进行插入或删除的线性表，先入先出。
卡罗兰数，即n个不同元素进栈，出栈元素不同排列的个数：$\frac{1}{n+1}C^{n}_{2n}$
栈的顺序存储结构
采用顺序存储的栈称为顺序栈。
还有一个概念叫共享栈，两个顺序栈共享一个数组空间，让他们的栈底分别设置在共享空间的两端，两个栈顶向共享空间中间延伸。
0号栈top0=-1时0号栈为空，top1=MaxSize时1号栈为空。
先改变栈顶指针，再赋值。出栈则相反。
存取数据的时间复杂度均为$O(1)$
栈的链式存储结构
利用单链表实现，所有操作都是在单链表的表头实现。
优点：
- 便于多个栈共享存储空间提升效率（减少内部碎片）
- 不存在栈满上溢的情况
队列
队列的基本概念
操作受限的线性表，只能在一端插入，另一端删除。先进先出
队列的顺序存储
一块连续的存储单元存放队列的元素，队头指针front，队尾指针rear。
判空：Q.front==Q.rear == 0
进队以及出队，都是先取值、送值，再指针变化。
循环队列
把存储队列的表逻辑上视为一个环。
初始：Q.front == Q.rear == 0
队头+1：Q.front = (Q.front+1)%MaxSize
队尾+1：Q.rear = (Q.rear+1)%MaxSize
队列长度：(Q.rear+MaxSize-Q.front)%MaxSize
判队空：Q.front == Q.rear
判队满：
牺牲一个单元来区分队空和队满，队头指针再队尾指针下一个位置则为队满。
(Q.rear+1)%MaxSize == Q.front
队列链式存储结构
队列的链式结构同时带有一个队头指针和队尾指针。
判空：Q.front==NULL && Q.rear == NULL
优点：
- 适合数据元素变动较大的情形
- 不存在队列满且溢出的问题
栈和队列的应用
栈
中缀表达式转后缀表达式:
- 从左到右扫描中缀表达式
- 遇到数字输出
- 遇到运算符：
- 若为‘（’入栈
- 若为‘）’把栈中运算符输出直到遇到‘（’，然后与它同归于尽
- 若遇到其他，优先级高于（外的运算符时则入栈，否则从栈顶开始依次输出运算不小于当前符号的运算符
队列
队列实现层次遍历
- 根节点入队
- 队空推出，否则循环3
- 出并访问队第一个节点，若他有左孩子则加进队列，若他有右孩子也加入队列，返回第二步。
特殊矩阵的压缩存储
矩阵的压缩存储
对称矩阵
元素$a_{i,j}$在B数组中的下标$k = i(i-1)/2+j-1$
$$k=\left{\begin{array}{ll}\frac{i(i-1)}{2}+j-1, & i \geq j \text { (下三角区和主对角线元素) } \ \frac{j(j-1)}{2}+i-1, & i<j\left(\text { 上三角区元素 } a_{i j}=a_{j i}\right)\end{array}\right.$$
三角矩阵
下三角矩阵: $$k=\left{\begin{array}{ll}\frac{i(i-1)}{2}+j-1, & i \geq j \text { (下三角区和主对角线元素) } \ \frac{n(n+1)}{2}, & i<j \text { (上三角区元素) }\end{array}\right.$$ 上三角矩阵 $$k=\left{\begin{array}{ll}\frac{(i-1)(2 n-i+2)}{2}+(j-i), & i \leq j \text { (上三角区和主对角线元素) } \ \frac{n(n+1)}{2}, & i>j \text { (下三角区元素) }\end{array}\right.$$
三对角矩阵
也就是带状矩阵。
下标：$k=2i+j-3$ 同时如果知道k： $$i=\lfloor(k+1) / 3+1\rfloor$$ $$j=k-2i+3$$