3. 栈、队列和数组

栈

一句话： 出栈的顺序中不允许跳过

栈的链式存储结构

通常使用单链表实现链栈，入栈和出栈均表头执行

优点： 不存在栈满溢出的问题

共享栈

队列

队首 出队

队尾 入队

循环队列

一句话：从 $front\to rear$ 顺时针

如果数组是[0,n] Maxsize = n + 1;

循环队列里的指针位置：

其中为了区分队满和队空可以利用下面三种方法

1. 牺牲一个存储单元：入队时少用一个存储单元，这是一种较为普遍的做法，约定以“队尾指针的下一位置为队首”作为队满标志

2. 增设 size 成员：记录当前元素个数。若入队成功，则 size++，若出队成功，则 size—

3. 增设tag标志位：出队后置 tag=0，此时 Q.front == Q.rear，则为队空。入队后置tag=1 ，此时 Qfront == Q.rear ,则为队满。

栈在括号匹配中的应用

栈在表达式求值中的应用

两步走： 中缀表达式 $\to$ 后缀表达式 、 后缀表达式求值

其中，后缀表达式暗含的逻辑 与 树里的 后序遍历 一致

表达式树的构造

Example

你是否想过一个 表达式 通过什么方式 能够变成一个树

首先 必须认同 该树 的根节点都是 op 操作符，叶节点 是被操作数

其次我们通过 口诀：

1. 加括号，确定优先级

2. 找最后执行的 运算符

3. 递归拆解（以根运算符为界 将表达式分到 左子树 和 右子树 中）

对表达式树遍历

遍历方式		对应结果
先序遍历		前缀表达式（波兰式）
中序遍历		中缀表达式
后序遍历		后缀表达式（逆波兰式）

数组 和 特殊矩阵

数据结构中，对于矩阵本身并不过多关注，其重点是如何以最小的内存空间高效存储矩阵，并支持对元素的便携访问

数组的存储结构

分为 一维 多维 数组

实际多维在内存中存储的形式也是线性的（通过映射）可以看出

特殊矩阵的压缩存储

对称矩阵

二维 n 阶对称矩阵$A[n][n]$ == 一维数组 $B\left[\frac{n(n+1)}{2}\right]$ 下标都是从1开始.

既然数值都对称，则对应 $a_{i,j}=a_{j,i}$，所以矩阵下标

$$k=\{\begin{array}{llc}\frac{i(i-1)}{2}+j-1,& & i\ge j(下三角区和主对角线元素)\\ & & \\ \frac{j(j-1)}{2}+i-1,& & i<j(上三角区元素)\end{array}$$

提示

此处以及后面的下标都默认数组是从0开始的

三角矩阵

最大容量： $B\left[\frac{n(n+1)}{2}+1\right]$

根据上三角和下三角矩阵会有两个下标方程

$$k=\{\begin{array}{llc}\frac{i(i-1)}{2}+j-1,& & i\ge j(下三角区和主对角线元素)\\ & & \\ \frac{n(n+1)}{2},& & i<j(上三角区元素)\end{array}$$ $$k=\{\begin{array}{llc}\frac{(i-1)(2n-i+2)}{2}+j-i,& & i\ge j(下三角区和主对角线元素)\\ & & \\ \frac{n(n+1)}{2},& & i<j(上三角区元素)\end{array}$$

三对角矩阵

因为三对角矩阵 不一定是方阵 所以只有下标计算：

关键： 做题时 ，重点查看 存储的方向 是按行还是按列 其次要看一维数组B的下标是从0开始还是从1开始，如果是0需要减1；

稀疏矩阵

问题：

为什么栈和数组的算法实现中不添加头结点

答： 可能是其逻辑结构导致的

题集

链栈 + 循环单链表

链栈中较难的题目，将循环单链表和栈的特性结合到一起的一道综合考察题

循环单链表，找尾（指针）比找头（指针）有用得多

错题

栈

错因 脑抽又算了一遍结果错了，本质是简单的，将 入栈出栈 顺序列出来会比较好出结果

队列

错因 Maxsize的实际含义出不清楚，例如说数组是[0, n],则Maxsize = n + 1。再简单点说就是去思考一个 数组的长度。

矩阵

错因 以上两题都是忘记了-1导致的，一般存入C语言这样的字眼都默认数组是从0开始的，算完实际位数需要-1匹配数组下标

总结：

1. Maxsize = 数组长度

2. 下标牢记 -1