第三章 栈和队列
栈的基本概念
- 栈（Stack）：一种操作受限的线性表，只允许在一端进行插入和删除操作的线性表。
- 特点：后进先出（Last In First Out，LIFO）
- 逻辑结构：与普通线性表相同
- 数据的运算：插入、删除操作有区别
- 重要术语：
- 空栈：栈里面没有任何数据元素
- 栈顶：允许插入和删除的一端
- 栈底：不允许插入和删除的一端
- 基本操作：
InitStack(&S)：初始化栈。构造一个空栈 S，分配内存空间。DestroyStack(&S)：销毁栈。销毁并释放栈 S 所占用的内存空间。Push(&S, x)：进栈，若栈 S 未满，则将 x 加入使其成为新栈顶。Pop(&S, &x)：出栈，若栈 S 非空，则弹出栈顶元素，并用 x 返回。GetTop(S, &x)：读栈顶元素。若栈 S 非空，则用 x 返回栈顶元素。StackEmpty(S)：判断一个栈 S 是否为空。若 S 为空，返回 ture，否则返回 false。
- n 个不同元素进栈，出栈元素不同排列的个数为$\frac{1}{n+1}C^n_{2n}$，上述公式称为卡特兰（Catalan）数，可采用数学归纳法证明。
顺序栈的实现
顺序栈的定义
1
2
3
4
5
typedef struct {
ElemType date[MaxSize]; //静态数组存放栈中元素
int top; //栈顶指针
} SqStack;初始化操作
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
typedef struct {
ElemType date[MaxSize]; //静态数组存放栈中元素
int top; //栈顶指针
} SqStack;
//初始化栈
void InitStack(Sqtack &S) {
S.top = -1; //初始化栈顶指针
}
//判断栈空
bool StackEmpty(SqStack S){
if(S.top == -1) //栈空
return true;
else //不空
return false;
}进栈操作
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
typedef struct {
ElemType date[MaxSize]; //静态数组存放栈中元素
int top; //栈顶指针
} SqStack;
//新元素入栈
bool Push(SqStack &S, ElemType x) {
if(S.top == MaxSize - 1) //栈满，报错
return false;
S.top = S.top + 1; //指针先加1
S.data[S.top] = x; //新元素入栈
//以上两行代码等价于 S.data[++S.top] = x;
return true;
}出栈操作
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
typedef struct {
ElemType date[MaxSize]; //静态数组存放栈中元素
int top; //栈顶指针
} SqStack;
//出栈操作
bool Pop(SqStack &S, ElemType &x) {
if(S.top == -1) //栈空，报错
return false;
x = S.data[S.top]; //栈顶元素先出栈
S.top = S.top - 1; //指针再减一
//以上两行代码等价于 x = S.data[S.top--];
return true;
}读栈顶操作
1
2
3
4
5
6
7
8
9
10
11
12
13
typedef struct {
ElemType date[MaxSize]; //静态数组存放栈中元素
int top; //栈顶指针
} SqStack;
//出栈操作
bool GetTop(SqStack &S, ElemType &x) {
if(S.top == -1) //栈空，报错
return false;
x = S.data[S.top]; //x记录栈顶元素
return true;
}初始化，入栈，出栈和读栈顶都是O(1)时间复杂度。
SqStack S;声明栈时分配内存，函数运行结束后系统自动回收内存。栈满的条件：top == MaxSize - 1
另一种方式
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
typedef struct {
ElemType date[MaxSize]; //静态数组存放栈中元素
int top; //栈顶指针
} SqStack;
//初始化栈
void InitStack(Sqtack &S) {
S.top = 0; //top指向下一个可以插入元素的位置
}
//判断栈空
bool StackEmpty(SqStack S){
if(S.top == 0) //栈空
return true;
else //不空
return false;
}
//进栈
S.data[S.top] = x;
S.top = S.top + 1;
等价于 S.data[S.top++] = x;
//出栈
S.top = S.top - 1;
x = S.data[S.top];
等价于 x = S.data[--S.top];栈满的条件：top == MaxSize
顺序栈的缺点：栈的大小不可变。
共享栈：两个栈共享同一片空间。
1
2
3
4
5
6
7
8
9
10
11
12
typedef struct {
ElemType date[MaxSize]; //静态数组存放栈中元素
int top0; //0号栈栈顶指针
int top1; //1号栈栈顶指针
} SqStack;
//初始化栈
void InitStack(Sqtack &S) {
S.top0 = -1; //初始化栈顶指针
S.top1 = MaxSize;
}栈满的条件：top0 + 1 == top1
链栈的实现
链栈：用链式存储方式实现的栈。
链栈的定义
1
2
3
4typedef struct Linknode {
ElemType data; //数据域
struct Linknode *next; //指针域
} *LiStack; //栈类型定义进栈：对头结点后插操作。
出栈：对头结点“后删”操作。
进栈和出栈操作都只能在栈顶一端进行（链头作为栈顶）。
实现方式推荐不带头结点。
队列的基本概念
- 队列（Queue）：一种操作受限的线性表，只允许在一端进行插入，在另一端删除的线性表。
- 特点：先进先出（Firstt In First Out，FIFO）
- 重要术语：
- 空队列：队列里面没有任何数据元素。
- 队尾：允许插入的一端。
- 队头：允许删除的一端。
- 基本操作：
InitQueue(&Q)：初始化队列。构造一个空队列 Q。DestroyQueue(&Q)：销毁队列。销毁并释放队列 Q 所占用的内存空间。Push(&Q, x)：进队，若队列 Q 未满，则将 x 加入使其成为新的队尾。Pop(&Q, &x)：出队，若队列 Q 非空，则弹出队顶元素，并用 x 返回。GetTop(Q, &x)：读队头元素。若队列 Q 非空，则用 x 返回队头元素。QueuekEmpty(Q)：判断一个队列 Q 是否为空。若 Q 为空，返回 ture，否则返回 false。
队列的顺序实现
队列的顺序实现
1
2
3
4
5
typedef struct {
ElemeType date[MaxSize]; //静态数组存放队列元素
int front, rear; //队头指针和队尾指针
} SqQueue;队头指针指向头元素；队尾指针指向下一个应该插入的位置
初始化操作
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
typedef struct {
ElemeType date[MaxSize]; //静态数组存放队列元素
int front, rear; //队头指针和队尾指针
} SqQueue;
//初始化队列
void InitQueue(SqQueue &Q) {
//初始时 队头、队尾指针指向0
Q.rear = Q.front = 0;
}
//判断队列是否为空
bool QueueEmpty(SqQueue) {
if (Q.rear == Q.front)
return true;
else
return false;
}入队操作（循环队列）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
typedef struct {
ElemeType date[MaxSize]; //静态数组存放队列元素
int front, rear; //队头指针和队尾指针
} SqQueue;
//入队（循环队列）
bool EnQueue(SqQueue &Q, ElemType x) {
if ((Q.rear + 1) % MaxSize == Q.front)
return false; //队满则报错
Q.data[Q.rear] = x; //新元素插入队尾
Q.rear = (Q.rear + 1) % MaxSize; //队尾指针加1取模
return true;
}出队操作（循环队列）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15//出队（删除一个队头元素，并用x返回）
bool DeQueue(SqQueue &Q, ElemType &x) {
if (Q.rear == Q.front)
return false; //队空则报错
x = Q.data[Q.front];
Q.front = (Q.front + 1) % MaxSize;
return true;
}
//获取队头元素的值，用x返回
bool GetHead(SqQueue Q, ElemType &x) {
if (Q.rear == Q.front)
return false; //队空则报错
x = Q.data[Q.front];
return true;
}判断队列已满/已空
方案一：
- 队满条件：队尾指针的下一个位置是队头
(Q.rear + 1) % MaxSize == Q.front - 队空条件：
Q.rear == Q.front
1
2
3
4
5
typedef struct {
ElemeType date[MaxSize]; //静态数组存放队列元素
int front, rear; //队头指针和队尾指针（初始化时 rear = front = 0)
} SqQueue;- 队满条件：队尾指针的下一个位置是队头
方案二：
- 队满条件：
size == MaxSize - 队空条件：
size == 0 - 插入成功 size++；删除成功 size–
1
2
3
4
5
6
typedef struct {
ElemeType date[MaxSize]; //静态数组存放队列元素
int front, rear; //队头指针和队尾指针
int size; //队列当前长度（初始化时：size = 0）
} SqQueue;- 队满条件：
方案三：
- 队满条件：
front == rear && tag == 1 - 队空条件：
front == rear && tag == 0 - 插入成功
tag = 0；删除成功tag = 1
1
2
3
4
5
6
typedef struct {
ElemeType date[MaxSize]; //静态数组存放队列元素
int front, rear; //队头指针和队尾指针
int tag; //最近进行的是删除/插入（初始化时：tag = 0）
} SqQueue;- 队满条件：
注意：
- 队尾指针指向队尾元素下一个位置
- 队尾指针指向指向队尾元素
- 初始化：front = 0；rear = n-1
- 插入：队尾指针先后移，再插入元素
- 判空：(Q.rear+1)%MaxSize == Q.front
- 判满：
- 牺牲一个存储单元
- 增加辅助变量
队列的链式实现
队列的链式实现
1
2
3
4
5
6
7
8typedef struct Linknode { //链式队列结点
ElemType data;
struct Linknode *next;
} LinkNode;
typedef struct { //链式队列
LinkNode *front, *rear; //队列的队头和队尾指针
} LinkQueue;初始化（带头结点）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22typedef struct Linknode { //链式队列结点
ElemType data;
struct Linknode *next;
} LinkNode;
typedef struct { //链式队列
LinkNode *front, *rear; //队列的队头和队尾指针
} LinkQueue;
//初始化队列（带头结点）
void InitQueue(LinkQueue &Q) {
//初始时 front 和 rear 都指向头结点
Q.front = Q.rear = (LinkNode*)malloc(sizeof(LinkNode));
Q.front->next = NULL;
}
//判断队列是否为空
bool isEmpy(LinkQueue Q) {
if (Q.front == Q.rear)
return true;
else
return false;
}初始化（不带头结点）
1
2
3
4
5
6
7
8
9
10
11
12
13//初始化队列（不带头结点）
void InitQueue(LinkQueue &Q) {
//初始时 front 和 rear 都指向NULL
Q.front = NULL;
Q.rear= NULL;
}
//判断队列是否为空
bool isEmpy(LinkQueue Q) {
if (Q.front == NULL)
return true;
else
return false;
}入队（带头结点）
1
2
3
4
5
6
7void EnQueue(LinkQueue &Q, ElemType x) {
LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode));
s->data = x;
s->next = NULL;
Q.rear->next = s; //新结点插入到rear之后
Q.rear = s; //修改表尾指针
}入队（不带头结点）
1
2
3
4
5
6
7
8
9
10
11void EnQueue(LinkQueue &Q, ElemType x) {
LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode));
s->data = x;
s->next = NULL;
if (Q.front == NULL) { //在空队列中插入第一个元素
Q.front = s; //修改队头队尾指针
Q.rear = s;
} else {
Q.rear->next = s; //新结点插入到 rear 结点之后
Q.rear = s; //修改 rear 指针
}出队（带头结点）
1
2
3
4
5
6
7
8
9
10
11
12//队头元素出队（带头结点）
bool DeQueue(LinkQueue &Q, ElemType &x) {
if(Q.front == Q.rear)
return false; //空队
LinkNode *p = Q.front->next;
x = p->data; //用变量 x 返回队头元素
Q.front->next = p->next; //修改头结点的 next 指针
if(Q.rear == p) //此次是最后一个极点出队
Q.rear == Q.front; //修改 rear 指针
free(p); //释放结点空间
return true;
}出队（不带头结点）
1
2
3
4
5
6
7
8
9
10
11
12
13//队头元素出队（不带头结点）
bool DeQueue(LinkQueue &Q, ElemType &x) {
if(Q.front == NULL)
return false; //空队
LinkNode *p = Q.front; //p 指向此次出队的结点
x = p->data; //用变量 x 返回队头元素
Q.front = p->next; //修改 front 指针
if(Q.rear == p) //此次是最后一个极点出队
Q.front == NULL; //front 指向 NULL
Q.rear == NULL; //rear 指针 NULL
free(p); //释放结点空间
return true;
}链式存储——一般不会队满，除非内存不足。
双端队列
- 只允许从两端插入，两端删除的线性表。
- 输入受限的双端队列：只允许从一端插入，两端删除的线性表。
- 输出受限的双端队列：只允许从两端插入，一端删除的线性表。
栈的应用——括号匹配问题
最后出现的左括号最先被匹配（LIFO）
算法实现：依次扫描所有字符，遇到左括号进栈，遇到右括号则弹出栈顶元素检查是否匹配。
- 匹配失败情况：
- 剩余左（右）括号
- 左右括号不匹配
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
typedef struct {
char date[MaxSize]; //静态数组存放栈中元素
int top; //栈顶指针
} SqStack;
//初始化栈
void InitStack(SqStack &s);
//判断栈是否为空
bool StackEmpty(SqStack S);
//新元素入栈
bool Push(SqStack &S, char x);
//栈顶元素出栈，用 x 返回
bool Pop(SqStack &S, char &x);
bool bracketCheck(char str[], int length) {
SqStack S;
InitStack(S); //初始化一个栈
for (int i = 0; i < length; i++) {
if (str[i] == '(' || str[i] == '[' || str[i] == '{') {
Push(S, str[i]); //匹配到左括号，入栈
} else {
if(StackEmpty(S)) //匹配到右括号，且当前栈空
return false; //匹配失效
char topElem;
Pop(S, topElem); //栈顶元素出栈
if(str[i] == ')' && topElem!='(')
return false;
if (str[i] == ']' && topElem != '[')
return false;
if (str[i] == '}' && topElem != '{')
return false;
}
}
return StackEmpty(S);
}- 匹配失败情况：
栈的应用——表达式求值
- 中缀表达式：运算符在两个操作数中间
- 后缀表达式（逆波兰表达式）：运算符在两个操作数后面
- 前缀表达式（波兰表达式）：运算符在两个操作数前面
- 中缀转后缀的手算方法：
- 确定中缀表达式中各个运算符的运算顺序
- 选择下一个运算符，按照（左操作数 右操作数 运算符）的方式组成一个新的操作数
- 如果还有运算符没被处理，就继续上一步
- “左优先“原则：只要左边的运算符能先计算，就优先算左边的。保证手算和机算结果相同。
- 从左往右扫描，每遇到一个运算符，就让运算符前面最近的两个操作数执行对运算，合体为一个操作数。
- 用栈实现后缀表达式的计算：
- 从左往右扫描下一个元素，直到处理完所有元素
- 若扫描到操作数则压入栈，回到上一步；否则执行下一步
- 若扫描到运算符，则弹出两个栈顶元素（先出栈的是“右操作数”），执行相应运算，运算结果压回栈顶，回到第一步
- 中缀转前缀的手算方法：
- 确定中缀表达式中各个运算符的运算顺序
- 选择下一个运算符，按照（运算符 左操作数 右操作数）的方式组成一个新的操作数
- 如果还有运算符没被处理，就继续上一步
- “右优先“原则：只要右边的运算符能先计算，就优先算右边的。保证手算和机算结果相同。
- 用栈实现前缀表达式的计算：
- 从右往左扫描下一个元素，直到处理完所有元素
- 若扫描到操作数则压入栈，回到上一步；否则执行下一步
- 若扫描到运算符，则弹出两个栈顶元素（先出栈的是“左操作数”），执行相应运算，运算结果压回栈顶，回到第一步
- 中缀表达式转后缀表达式（机算）
- 初始化一个栈，用于保存暂时还不能确定运算顺序的运算符。
- 从左到右处理各个元素，直到末尾。可能遇到三种情况：
- 遇到操作数。直接假如后缀表达式。
- 遇到界限符。遇到 “(“ 直接入栈；遇到 “)” 则依次弹出栈内运算符并加入后缀表达式，直到弹出 “(“ 为止。注意：”(“ 不加入后缀表达式。
- 遇到运算符。依次弹出栈中优先级高于或等于当前运算符的所有运算符，并加入后缀表达式，若碰到 “(“ 或栈空则停止。之后再把当前运算符入栈。
- 按上述方法处理完所有字符后，将栈中剩余运算符依次弹出，并加入后缀表达式。
- 中缀表达式的计算（用栈实现）：
- 初始化两个栈，操作数栈和运算符栈
- 若扫描到操作数，压入操作数栈
- 若扫描到运算符或界限符，则按照“中缀转后缀”相同的逻辑压入运算符栈（期间也会弹出运算符，每当弹出一个运算符时，就需要再弹出两个操作数栈的栈顶元素并执行相应元素，运算结果再压回操作数栈）
栈的应用——递归
- 函数调用的特点：最后被调用的函数最先执行结束（LIFO）
- 函数调用时，需要用到一个栈存储：
- 调用返回地址
- 实参
- 局部变量
- 适合用“递归”算法解决：可以把原始问题转换为属性相同，但规模较小的问题。例如：
- 计算正整数的阶乘！
- 求斐波那契数列
- 递归调用时，函数调用栈可称为“递归工作栈”。
- 每进入一层递归，就将递归调用所需信息压入栈顶。
- 每退出一层递归，每退出一层递归，就从栈顶弹出相应信息。
- 缺点：效率低，太多层递归可能会导致栈溢出；可能包含很多重复计算。
- 可以自定义栈将递归算法改造成非递归算法。
队列的应用
- 树的层次遍历
- 图的广度优先遍历
- 队列在操作系统中应用
- 多个进程争抢着使用有限的系统资源，FCFS（First Come First Service，先来先服务）是一种常用策略。
- 打印数据缓冲区。
特殊矩阵压缩存储
数组的存储结构
- 一维数组的存储结构
ElemType a[10];- 起始地址：LOC
- 各组元素大小相同，且物理上连续存放。
- 数组元素 a[i] 的存放地址 = LOC+ i*sizeof(Elemtype)
- 数组下标默认从0开始。
- 二维数组的存储结构
- 两种存储策略：行优先存储；列优先存储。
- 起始地址：LOC
- 在M行N列的二维数组中
- 若行优先存储，b[ i ] [ j ]的存储地址 = LOC + (i * N + j) * sizeof(ElemType)
- 若列优先存储，b[ i ] [ j ]的存储地址 = LOC + (i * M + i) * sizeof(ElemType)
普通矩阵的存储
- 可用二维数组存储
- 描述矩阵元素时行和列通常从1开始，描述数组时通常从0开始。
对称矩阵的压缩存储
- 对称矩阵：元素值关于主对角线对称。
- 策略：只存储主对角线 + 下三角区。
- 按行优先原则将各元素存入一维数组中。
- 共有$\frac{n * (n+1)}{2}$个元素，按行优先原则ai,j是第$\frac{i * (i -1)}{2} + j$个元素。
- 找上三角区元素：找aj,i
- 按列优先原则将各元素存入一维数组中。
- 共有$\frac{n * (n+1)}{2}$个元素，按行优先原则ai,j是第[n + (n-1) + … + (n-j+2)] + (i-j) +1个元素。
- 找上三角区元素：找aj,i
三角矩阵的压缩存储
下三角矩阵：除了主对角线和下三角区，其余的元素都相同
压缩存储策略：
按行优先原则将下三角区存入一维数组中。并在最后一个位置存储常量C。
共有$\frac{n * (n+1)}{2} + 1$个元素，按行优先原则：
- 若i >= j，ai,j是第$\frac{i * (i -1)}{2} + j$个元素。
- 若i < j，ai,j是第$\frac{n * (n + 1)}{2} + j$个元素。
按行优先原则将上三角区存入一维数组中。并在最后一个位置存储常量C。
共有$\frac{n * (n+1)}{2} + 1$个元素，按行优先原则：
- 若i <= j，ai,j是第[n + (n - 1) + … + (n - j + 2)] + (i - j) +1个元素。
- 若i > j，ai,j是第$\frac{n * (n + 1)}{2} + j$个元素。
三对角矩阵的压缩存储
- 三对角矩阵：又称带状矩阵。主对角线及其相邻对角线元素可以不为0，其余元素均为0。（除了第一行和最后一行至多有两个不为0元素，其余行至多有三个不为0元素。
- 共有3n-2个元素，按行优先原则，ai,j是第2*i+j-2个元素。
- 第 k 个元素在第(k+2) /3行，第k-2*i+3列。
稀疏矩阵的压缩存储
- 稀疏矩阵：非零元素远远少于矩阵元素的个数。
- 策略：
- 顺序存储——三元组<行，列，值>（
struct） - 链式存储——十字链表法
- 向下域down：指向同列的下一个非零元素
- 向右域right：指向同行的下一个非零元素
- 顺序存储——三元组<行，列，值>（