第三章栈和队列

复习时间轴

6.28-29：看书复习、王道数据结构复习书相应部分并做题
6.30：

3.1.1 栈的定义和特点
3.1.2 栈的表示和操作实现
3.1.3 栈的应用：递归实现

知识框架

graph LR; 线性表-->栈; 线性表-->队列; 线性表-->数组; 栈-->顺序栈; 栈-->链栈; 栈-->共享栈; 队列-->循环队列; 队列-->链式队列; 队列-->双端队列; 数组-->一维数组; 数组-->多维数组;

复习要点

本章通常是考选择题，题目不难但是命题形式比较灵活，其中栈（出入栈的过程、出栈序列的合法性）和队列的操作及其特征是重点。由于它们是线性表的应用和推广，因此也容易出现在算法设计题中。此外，栈和队列的顺序存储、链式存储及其特点、双端队列的特点、栈和队列的常见应用，以及数组和特殊矩阵的压缩存储都是必须掌握的内容。
线性表的应用以表的合并为重点，不仅要学会算法的实现，也要掌握合并算法复杂度的分析
递归是栈的最常见应用，结合算法实例理解

栈

n个不同元素进栈，出栈元素不同排列的个数为卡特兰数：$\frac{1}{n+1}C_{2n}^{n}$
栈的基本操作

栈的顺序存储（顺序栈）

采用顺序存储的栈叫做顺序栈，存储地址连续，设定top指针

静态分配

#define MaxSize 50
typedef struct{
    Elemtype data[MaxSize];
    int top;
}SqStack;

动态分配
因为栈在使用过程中所需最大空间的大小很难估计，因此一般来说，在初始化设定栈的时候不应该限定栈的最大容量，一个较合理的做法是：先分配一个初始容量，然后随着使用需要更多空间再重新分配。

#define InitSize 50
typedef struct{
    Elemtype *base;
    Elemtype *top;
    int stacksize;
}SqStack;

base叫做栈底指针，在顺序栈中，它始终指向栈底的位置，若base的值为NULL，则栈不存在（不代表栈为空），top为栈顶指针，初始化栈时会分配一个起始地址给top，并将base=top，即top=base为栈空条件

栈的链式存储

叫做链栈，优点是便于多个栈共享同一块存储空间和提高效率，不存在栈满上溢的情况。

typedef struct LinkNode{
    Elemtype data;
    struct LinkNode *next;
}*LiStack;

栈的操作

初始化InitStack

静态分配
将top置为-1即可

1
2
3

void InitStack(SqStack &S){
    S.top=-1;
}

动态分配
要分配空间，还要进行判断是否初始化成功

bool InitStack(SqStack &S){
    S.base=(Elemtype*)malloc(InitSize*sizeof(Elemtype));
    if(S.base==NULL)return false;
    S.top=S.base;
    S.stacksize=InitSize;
    return true;
}

进栈

出栈

判断栈空

读栈顶元素

共享栈

栈的应用

数制转换

因为辗转相除法最后逆序正好符合了栈的LIFO的特点，所以可以用栈实现数制转换

void transform(){
    SqStack S;
    InitStack(S);
    int N;
    scanf("%d", &N);
    while(N){
        S.Push(N%2);
        N=N/2;
    }
    int e;
    while(!Empty(S)){
        S.pop(e);
        printf("%d", e);
    }
}

括号匹配

因为括号后面出现的右括号也是要先匹配前面最后一个左括号，也就是栈顶括号，也符合

行编辑程序

用来设定输入缓冲区，根据栈顶是不是特殊字符判断什么操作

迷宫求解

表达式求值

中缀表达式可以用符号栈和操作数栈分开

函数调用栈

这个栈每个节点存储返回地址以及参数值

栈与递归的实现

利用函数调用栈，在程序设计语言中实现递归。
**递归函数：**一个直接调用自己或者通过一系列调用语句间接调用自己的函数，叫做递归函数。
在一个函数的运行期间要调用其他函数的时候，系统需要做三件事

将被调用的函数所需要的参数和执行完需要返回的地址传给被调用函数
分配存储空间给被调用函数存储局部变量
最后将控制权交给被调用函数
被调用函数执行完之后，保存计算结果，并释放局部变量的存储空间，返回到原先传给它的返回地址。
可以看出是后调用的函数先计算出结果，也就是先运行完，类似于栈的后进先出结构，所以使用函数调用栈来处理函数的调用问题。当一个函数执行完之后，就从栈顶弹出。

第三章 栈和队列