第三章 栈、队列和数组

第三章 栈、队列和数组

3.1 栈

栈的基本概念

1.栈的定义

栈顶：指线性表允许进行插入删除的那一端

栈尾：固定的，不允许进行插入和删除的那一端

栈的特性为后进先出

栈的数学性质：n个不同元素进栈，出栈元素不同排列个数为$\frac{1}{n+1}{C}_{2n}^n$

栈的顺序存储结构

栈是一种操作受限的线性表，也有两种存储方式：

1.顺序栈

2.链栈

便于节点的插入和删除，但是查找不太方便

3.共享栈

两个顺序栈共享一个一维数组空间，将两个栈的栈底分配到共享空间的两端，两个栈顶向共享空间的中间延伸

栈的链式存储结构

3.2 队列

队列的基本概念

1.队列的定义

队列也是一种操作受限的线性表，只允许在表的一端进行插入，在另一端进行删除。队列的操作特性是先进先出（FIFO）

循环队列

将顺序表视作为首尾相连的环，在进行操作的时候需要进行取余mod操作，比如在大小为n的循环队列中，n-1号元素是其最后的元素，那么查找该元素的下一个元素则执行的是(n-1)+1mod n=0，也就是n-1号元素下一个是0号，实现了循环队列
初始时：Q.front=Q.rear
队首指针进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

3.3 栈和队列的应用

栈在括号匹配中的应用

一.算法思想

1）初始设置一个空栈，顺序读入括号

2）如果是右括号，而且和栈顶的括号相匹配，则两个括号相消除；如果和栈顶的括号不匹配则判断为不合法

3）如果是左括号，则作为优先级更高的括号被压入栈中，使得原来处于栈顶的最高优先级括号向下降一级。算法结束时栈为空，如果非栈空则括号序列不合法。

队列在层次遍历中的应用

层次遍历二叉树的过程如下：

1. 根节点入队
2. 如果队空，则结束遍历；否则重复3的操作
3. 队列中的第一个节点出队，并且访问。如果有左子节点，则左子节点入队；如果有右子节点，则右子节点入读，返回2

3.4 特殊矩阵的压缩存储

！注意：审题需要看清第一个元素是a[0]还是a[1]
数组存储结构：
考点：求n维数组中的某一元素的存储地址

1.对称矩阵

对于n阶对称矩阵，上三角区的所有元素和下三角区的对应元素相同，因此，采用二维数组堆放会浪费几乎一半的空间，为此可以将堆成矩阵A[1…n] [1…n]存放在一维数组B[n(n+1)/2]中。
a [ i ] [ j ] = a [ k ] = { i ( i − 1 ) 2 + j − 1 , i ≥ j ( 下三角 ) j ( j − 1 ) 2 + i − 1 , i < j ( 上三角 ) a[i][j]=a[k]=\left\{

\right. a[i][j]=a[k]=⎩ ⎨ ⎧​2i(i−1)​+j−1,i≥j(下三角)2j(j−1)​+i−1,i<j(上三角)​

2.三角矩阵

下三角矩阵的上三角区的所有元素均为同一常量，不同之处是存储玩下三角区和主对角线上的元素后，紧接着只需要存储对角线上方的常量元素一次（因为上三角区都是同一常量），因此可以将下三角矩阵A[1…n] [1…n]存储在B[n(n+1)/2+1]

3.三对角矩阵

对角矩阵又称为带状矩阵。三对角矩阵也可以采用压缩存储，将三条对角线上的元素按照行优先存储在一维数组B中。
其定义为$a_{i,j}(1\le i,j\le n,|i-j|\le 1)$
因为除了第一行和最后一行存储两个元素外，其他的各行都需要存储3个元素，所以总共需要存储3n-2个元素。

4.稀疏矩阵

稀疏矩阵中非零元素的个数十分少，大部分都是0元素。如果采用常规的方法存储稀疏矩阵会十分浪费存储空间。使用三元组顺序存储稀疏矩阵

struct typedef{
int x;
int y;
int value;
}SqSparseMatrix

十字链表法也可以用来存储稀疏矩阵