Chapter 3. 栈、队列和数组

概念

• 顺序栈和链式栈都只能顺序存取。

• 单向队列在队尾（数组尾部 or 链尾）插入，在队头（数组头部 or 链头）弹出。

• 对稀疏矩阵采用三元组顺序表进行压缩存储，若要完成对三元组顺序表进行转置操作，不能仅将行与列对换

  还需要保持非零元素的相对顺序（或某种规律）

考点

• 卡特兰公式： f(n)=C ^ n _ {2n} \frac 1 {n+1} ，可求解n个不同元素入栈，不同出栈序列的个数。

• 使用栈实现含 n 个结点的二叉树的非递归遍历（空子树也入栈），在最坏情况下，栈需要的存储空间为 n 。

  算法过程：创建栈，并初始化。遍历结点，若结点存在，则入栈，并输出结点的值，指向其左孩子；否则出栈，访问结点，指向其右孩子。如果结点不存在或者栈为空，则遍历结束。最坏情况为只有左子树的树高为 n 的二叉树，此时需要空间为 n 的栈。

• 对于循环队列，无论指针 rear 指向实际队尾位置还是实际队尾位置的后一位置，队满的判定条件都是 (rear+1) \ \% \ maxSize==front （在 rear 指向实际队尾位置的后一位置时，意味着牺牲一位的空间用来判定队满），队空的判定条件都是 front==rear 。

• 所有的递归算法都可转化为非递归算法。非递归算法的效率不一定比递归算法高。

• 矩阵的下标计算时，注意关注数组的下标起始位置，矩阵的下标起始位置，行优先还是列优先，压缩矩阵时还需关注形状。

• 三对角矩阵的形状：\begin{bmatrix} a_{11} & a_{12} & 0 & 0 & 0 & \cdots & 0 \\ a_{21} & a_{22} & a_{23} & 0 & 0 & \cdots & 0 \\ 0 & a_{32} & a_{33} & a_{34} & 0 & \cdots & 0 \\ \cdots & \cdots & \cdots & \cdots & \cdots & \cdots & \cdots \\ 0 & \cdots & 0 & a_{n-2,n-3} & a_{n-2,n-2} & a_{n-2,n-1} & 0 \\ 0 & \cdots & 0 & 0 & a_{n-1,n-2} & a_{n-1,n-1} & a_{n-1,n} \\ 0 & \cdots & 0 & 0 & 0 & a_{n,n-1} & a_{n,n} \end{bmatrix}

• 用三元组表示稀疏矩阵时，除了需要记录数据的横坐标、纵坐标以及数据本身，还需要记录该矩阵的宽、高以及默认值。