栈和队列

栈的基本概念

栈的定义

栈是只允许在一端进行插入或删除操作的线性表

逻辑结构：与普通线性表相同

数据的运算：插入，删除操作有区别

特点：后进先出，即Last In First Out(LIFO)

 

几个重要术语：

• 空栈
• 栈顶：允许插入和删除的一端
• 栈底：不允许插入和删除的一端
• 栈顶元素
• 栈底元素

栈的基本操作

主要是创建，销毁，改变（进栈，出栈），查找（读栈顶元素）和其他常用操作（判空）

栈的使用场景中大多只访问栈顶元素

栈的常考题型

给定一个进栈顺序，要会判断一个出栈顺序是否合法

$n$个不同元素进栈，出栈元素不同排列的个数为$\frac{1}{n+1}{C}_{2n}^n$。这个公式称为卡特兰数，可采用数学归纳法证明（不要求掌握）

栈的顺序存储结构

销毁一个栈首先要把栈在逻辑上清空，然后回收栈所占用的内存资源。在逻辑上清空一个栈只要把top指针指向-1就可以了。这一节中采用变量声明的方式分配相应的空间，并没有使用malloc函数，所以给栈分配的空间也会在函数运行结束之后由系统自动回收，所以回收内存资源的事情你并不用管

顺序栈除了栈的基本操作外还要注意判满的操作

顺序栈的定义

#define MaxSize 10          //定义栈中元素的最大个数
typedef struct{
    ElemType data[MaxSize]; //静态数组存放栈中元素
    int top;                //栈顶指针
}SqStack;  

//初始化栈
void InitStack(SqStack &S){
    S.top=-1;               //初始化栈顶指针  
}
1
2
3
4
5
6
7
8
9
10

top栈顶指针用于指向此时这个栈的栈顶元素，一般来说这个栈顶指针记录的是数组的下标。初始化栈的时候可以让top指向-1

定义后在函数中使用顺序栈

void testStack(){
    SqStack S; //声明一个顺序栈(分配空间)
    InitStack(S);
    //...后续操作...
}
1
2
3
4
5

利用top栈顶指针也可以判断栈是否为空

book StackEmpty(SqStack S){
    if(top==-1){
        return true;             //栈空
    }else{
        return false;            //不空
    }
}
1
2
3
4
5
6
7

进栈操作，出栈操作，读栈顶元素操作

//新元素入栈
bool Push(SqStack &S,ElemType x){
    if(S.top==MaxSize-1){      //栈满，报错
        reutn false;
    }
    S.top=S.top+1;             //指针先加1
    S.data[s.top]=x;           //新元素入栈
    return true;
}
//中间两步也可以合并为S.data[++S.top]=x;

//出栈操作
bool Pop(SqStack &S,Elemtype &x){
    if(S.top==-1){    //栈空，报错
        return false;
    }        
    x=S.data[S.top];  //栈顶元素先出栈
    S.top=S.top-1;    //指针再减1
    return true;
}
//中间两步也可以合并为x=S.data[S.top--];
//数据还残留在内存中，只是逻辑上被删除了

//读栈顶元素
bool GetTop(SqStack S,ElemType &x){
    if(S.top==-1){
        return false;         //栈空，报错
    }
    x=S.data[S.top];          //x记录栈顶元素
    return true;
}
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

另一种方式

刚才我们所有的操作都是让top指针指向此时的栈顶元素，其实也可以用另一种方法来设计。可以让top指针初始指向0，这种实现方式是让top指向下一个可以插入的位置

相应的判断栈空就看top是否等于0

这种方法如果要入栈就用

S.data[S.top++]=x;
1

出栈就用

x=S.data[--S.top];
1

判断栈满的条件就是top==MaxSize

共享栈

显然顺序栈的缺点是栈的大小不可变。而共享栈就是让两个栈共享一块连续的内存空间以提高内存资源的利用率。在逻辑上实现两个栈，但是在物理上这两个栈共享同一片存储空间

#define MaxSize 10           //定义栈中元素的最大个数
typedef struct{
    ElemType data[MaxSize];  //静态数组存放栈中元素
    int top0;                //0号栈栈顶指针
    int top1;                //1号栈栈顶指针
}ShStack;

//初始化栈
void InitStack(ShStack &S){
    S.top0=-1;            //初始化栈顶指针
    s.top1=MaxSize;
}

//栈满的条件为：top0+1==top1
1
2
3
4
5
6
7
8
9
10
11
12
13
14

栈的链式存储结构

头插法建立单链表与单链表的后删操作

对头结点的后插操作可以对应进栈操作

对头结点的“后删”操作又可以对应出栈

因此用链式存储实现的栈本质上也是一个单链表，只不过我们规定把链头的一端看作栈顶，插入和删除结点只能在链头的一端进行操作，这就对应了栈的出栈和入栈操作

所以对于链栈的定义和对单链表的定义几乎没有区别，只是名字改了下

typedef struct Linknode{
    ElemType data;                //数据域
    struct Linknode *next;        //指针域
}*LiStack                         //栈类型定义
1
2
3
4

和单链表相似，当我们用链式存储来实现链栈的时候，也可以用带头结点的版本和不带头结点的版本（推荐使用不带头结点的实现方式）。两种方式对于判断栈是否为空的方式也不一样

如何在表头位置进行插入和删除，请自行复习单链表

队列的基本概念

队列的定义

队列是只允许在一端进行插入（入队），在另一端删除的线性表（出队）

队列的特点：先进先出，即First in First out（FIFO）

 

几个重要术语

• 空队列
• 队头：允许删除的一端
• 队尾：允许插入的一端
• 队头元素
• 队尾元素

队列的基本操作

队列的使用场景中大多只访问队头元素

队列的顺序存储结构

队列的顺序实现与初始化操作

#define MaxSize 10            //定义队列中元素的最大个数
typedef struct{
    ElemType data[MaxSize];   //用静态数组存放队列元素
    int front,rear;           //队头指针和队头指针
}SqQueue;

//初始化队列
void InitQueue(SqQueue &Q){
    //初始时 队头，队尾指针指向0
    Q.rear=Q.front=0;
}
1
2
3
4
5
6
7
8
9
10
11

rear指向队尾元素的后一个位置（下一个应该插入的位置），front指向队头元素

定义后在函数中使用顺序队列

void testQueue(){
    SqQueue Q;     //声明一个队列(顺序存储)
    InitQueue(Q);
    //...后续操作...
}
1
2
3
4
5

利用队头指针和队尾指针是否相等来判断队列是否为空

bool QueueEmpty(SqQueue Q){
    if(Q.rear==Q.front){
        return true;
    }else{
        return false;
    }
}
1
2
3
4
5
6
7

入队操作

先不考虑怎么判断队列已满，可以写出以下入队操作的代码

//入队
bool EnQueue(SqQueue &Q,ElemType x){
    if(队列已满){
        return false;       //队满则报错
    }
    Q.data[Q.rear]=x;       //将x插入队尾
    Q.rear=Q.rear+1;        //队尾指针后移
    return true;
}
1
2
3
4
5
6
7
8
9

是否可以认为队列已满的判断方式是rear==MaxSize?

为了有效利用先入队元素出队后空出的存储空间，不可以这样判断队列已满

当发现rear指针要指向MaxSize时不应该让它指向MaxSize而是应该让它指向数组下标为0的位置，为了实现这一点可以对之前的代码进行修改

bool EnQueue(SqQueue &Q,ElemType x){
    if(队列已满){
        return false;
    }
    Q.data[Q.rear]=x;
    Q.rear=(Q.rear+1)%MaxSize;   //队尾指针加1取模
    return true;
}
1
2
3
4
5
6
7
8

用模运算将存储空间在逻辑上变成了“环状”。由于这个队列的存储空间在逻辑上是一个环状，是一个循环，所以我们把用这种方式实现的队列叫做循环队列

以下循环队列的各个情况如果看不明白的话最好画一下图

这样就可以得出上面代码中队列已满的条件：队尾指针的再下一个位置是队头，即

(Q.rear+1)%MaxSize==Q.front
1

 

 

为什么这里要留出一个空闲的空间不利用？

我们在初始化队列的时候把front和rear指针指向同一个位置，同时我们也是通过这两个指针是否指向同一个位置来判断这个队列是否为空。如果往这个位置也插入一个元素，同时让rear指针和front指针指向同一个位置的话，那会与之前的逻辑相冲突，因为这样按照之前的判断条件这个队列此时为空，而实际上这个队列是满的

 

所以完整的入队操作是

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

出队操作和获取队头操作

//出队（删除一个队头元素，并用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;
}
1
2
3
4
5
6
7
8
9

//获取队头元素的值，并用x返回
bool GetHead(SqQueue Q,ElemType &x){
    if(Q.rear==Q.front){
        return false;   //队空则报错
    }
    x.Q.data[Q.front];
    return true;
}
1
2
3
4
5
6
7
8

获取队头元素的值操作和出队操作的唯一差别在于不用把队头指针进行后移

判断队列已满/已空的方案

方案一

就是上面我们通常所采取的方式，采用逻辑上的循环结构来实现顺序队列。代价是牺牲一个存储空间

初始化时

rear=front=0
1

对列已满的条件：队尾指针的再下一个位置是队头。即

(Q.rear+1)%MaxSize==Q.front
1

队空条件：

Q.rear==Q.front
1

用这种方式可以很方便的获取队列元素的个数

(rear+MaxSize-front)%MaxSize
1

这种方案是以牺牲了一片存储空间为代价的，日常写代码的时候用这种方案已经很好了，但是笔试有的时候会要求你不可以浪费那片闲置的存储空间

方案二

有的时候要求我们不能浪费这块空间，解决方法是在定义时增加一个变量记录队列当前长度

#define MaxSize 10
typedef struct{
    ElemType data[MaxSize];
    int front,rear;
    int size;  //队列当前长度
}SqQueue;
1
2
3
4
5
6

初始化时

rear=front=0;
size=0;
1
2

每次插入成功或者删除成功时都要

size++;
size--;
1
2

队空条件

size==0;
1

队满条件

size==MaxSize
1

方案三

只有删除操作，才可能导致队空。只有插入操作，才可能导致队满。因此可以设置变量tag表示最近进行的是删除还是插入。0表示最近执行的是删除操作，1表示最近执行的是插入操作

#define MaxSize 10
typedef struct{
    ElemType data[MaxSize];
    int front,rear;
    int tag;      //最近进行的是删除/插入
}SqQueue;
1
2
3
4
5
6

初始化时

rear=front=0;
tag=0;
1
2

每次删除操作成功时，都令

tag=0;
1

每次插入操作成功，都令

tag=1;
1

队满条件：

front==rear&&tag==1
1

队空条件：

front==rear&&tag==0
1

其他出题方法

之前的论述中都让队尾指针指向队尾元素的后一个位置（下一个应该插入的位置），但有的时候会让队尾指针指向队尾元素，这种情况下代码自然又会有一些不同，比如之前的入队操作是

Q.data[Q.rear]=x;
Q.rear=(Q.rear+1)%MaxSize;
1
2

而现在这种情况下会让队尾指针先往后移一位，再往这个位置写入新的元素

Q.rear=(Q.rear+1)%MaxSize;
Q.data[Q.rear]=x;
1
2

除了入队操作之外，由于每次入队的时候都让队尾指针先往后移，再插入新的元素，因此初始化的时候可以让front指针指向0位置，rear指针指向n-1位置，这样插入第一个数据元素的时候rear指针就会先移到0位置再往0位置插入第一个数据元素

 

这种情况下判空看队尾指针的下一个位置是不是队头

(Q.rear+1)%MaxSize==Q.front;
1

至于判满操作和之前的思路一样有多种方案，可以选择牺牲一个存储单元（规定头指针前面的一个单元不可以存储元素，这样头指针在尾指针的后一个位置说明队列为空，头指针在尾指针的后面两个位置说明队列是满的），也可以增加辅助变量（或者是size变量，或者是tag变量）

队列的链式存储结构

队列实际上就是单链表的一个功能阉割版。也有带头结点和不带头结点的版本

队列的链式实现

typedef struct LinkNode{    //链式队列结点
    ElemType data;
    struct LinkNode *next;
}LinkNode;

typedef struct{             //链式队列
    LinkNode *front,*rear;  //队列的队头和队尾
}LinkQueue;                 
1
2
3
4
5
6
7
8

初始化

带头结点

//初始化队列，带头结点
void InitQueue(LinkQueue &Q){
    //初始时front,rear都指向头结点
    Q.front=Q.rear=(LinkNode*)malloc(sizeof(LinkNode));
    Q.front->next=NULL;
}
1
2
3
4
5
6

定义初始化函数后使用

void testLinkQueue{
    LinkQueue Q;     //声明一个队列
    InitQueue(Q);    //初始化队列
    //...后续操作...
}
1
2
3
4
5

判断队列为空可以看头尾结点是否相同

bool IsEmpty(LinkQueue Q){
    if(Q.front==Q.rear){
        return true;
    }else{
        return false;
    }
}
1
2
3
4
5
6
7

不带头结点

void InitQueue(LinkQueue &Q){
    //初始时front,rear都指向NULL
   Q.front=NULL;
   Q.rear=NULL;
}
1
2
3
4
5

判空看队头元素是否为NULL

bool IsEmpty(LinkQueue Q){
    if(Q.front==NULL){
        return true;
    }else{
        return false;
    }
}
1
2
3
4
5
6
7

入队

带头结点

void 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

不带头结点

对于不带头结点的情况，第一个元素入队时要特殊处理。因为一开始这两个指针都是指向NULL的，所以插入第一个元素时对这两个指针都要进行修改

void 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

出队

带头结点

front指向头结点，删除头结点的后一个结点

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
14

不带头结点

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

链式存储一般不会队满，除非内存不足

要统计链式队列有多长的话只能遍历整个队列进行计数，需要用$O(n)$的时间。如果需要频繁的访问队列长度的信息的话，可以在定义链式队列结构体时加一个int类型的length变量用来记录当前队列的长度

双端队列

双端队列是允许从两端插入，两端删除的线性表。

若只使用其中一端的插入，删除操作，则效果等同于栈

双端队列还可以进行一定的变化。变为输入受限的双端队列（只允许从一端插入，两端删除的线性表）。输出受限的双端队列（只允许从两端插入，一端删除的线性表）

考点：判断输出序列合法性

通常就是和上面一样，笔试中给你一个输入序列，判断在栈，输入受限的双端队列，输出受限的双端队列等限制条件下一个输出序列是否合法

栈中合法的序列，双端队列中一定也合法，因此判断输入受限的双端队列，输出受限的双端队列只需要额外看在栈中不合法的那些序列就可以了

做这类题目最重要的一点是如果你在输出序列中看到某一序号的元素，那么在这个元素输出之前意味着输入序列中它之前的所有元素肯定都已经输入到这个序列中了

栈在括号匹配中的应用

括号匹配问题及其算法演示

给出一连串括号序列，检查其是否合法。必须保证在代码出现的这些括号都是成双成对出现的，除了左括号和右括号在数量上要匹配之外，形状上也必须匹配

观察下面的一连串括号，如果是计算机来进行括号匹配检查的话，只能从左到右依次扫描

(((())))
1

不难发现最后出现的左括号最先被匹配（LIFO），可用栈实现这种特性。我们可以把左括号依次压入栈中，越往后被压入的左括号越先被弹出栈进行匹配。每出现一个右括号，就“消耗”一个左括号进行匹配检查，这个过程对应出栈操作。

扫描一连串括号的过程中若发现下列情况都说明括号序列不合法，终止操作

• 弹出栈的左括号与刚刚遇到要检查的右括号不匹配
• 扫描到右括号时发现栈空了（右括号单身）
• 处理完所有括号后，栈非空（左括号单身）

代码实现

#define MaxSize 10                  //定义栈中元素的最大个数
typedef struct{
    char data[MaxSize];             //静态数组存放栈中元素
    int top;                        //栈顶指针
}SqStack;

void InitStack(SqStack &S)          //初始化栈
bool StackEmpty(SqStack S)          //判断栈是否为空
bool Push(SqStack &S,char x)        //新元素入栈
bool Pop(SqStack &S,char &x)        //栈顶元素出栈，用x返回
    
bool bracketCheck(char str[],int length){  //字符数组存储要检查的括号序列，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);       //检查完全部括号后，栈空说明匹配成功
}
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

笔试考试中可以直接使用基本操作，但是建议简要说明接口

栈在表达式求值中的应用（一）

中缀，后缀，前缀表达式

普通的算数表达式由三个部分组成：操作数，运算符，界限符（界限符是必不可少的，反映了计算的先后顺序）。而后缀表达式（逆波兰表达式）和前缀表达式（波兰表达式）可以不用界限符也能无歧义地表达运算顺序。中缀表达式运算符在两个操作数中间，后缀表达式运算符在两个操作数后面，前缀表达式运算符在两个操作数前面

相比前缀表达式，后缀表达式在现实中应用的更多些

中缀表达式转后缀表达式（手算）

有这种“左优先”原则得到的后缀表达式中运算符从左到右出现的顺序和原中缀表达式中这些运算符生效的先后次序是相同

如果想用计算机来实现中缀转后缀的算法，由于算法的确定性，输入同样的中缀表达式应该只输出一种结果。因此客观来讲两种运算顺序得到的后缀表达式都正确，但是如果我们用之后要讲的计算机的算法来实现的话，它得到的应该是上图左边的表达式。所以中缀表达式转后缀表达式最好用“左优先”原则来确定运算符的顺序（可保证运算顺序唯一）来得到对应的后缀表达式，这样就能保征手算和机算结果一致

后缀表达式的计算（手算）

这种运算的特点是最后出现的操作数先被运算，这符合LIFO（后进先出）的原则，所以代码实现可以用栈

后缀表达式的计算(机算)

1.从左到右扫描下一个元素，直到处理完所有元素

2.若扫描到操作数则压入栈，并回到1，否则执行3

3.若扫描到运算符，则弹出两个栈顶元素（注意先出栈的是“右操作数”，这一点不能搞混），执行相应运算，运算结果压回栈顶，回到1

若表达式合法，则最后栈中只会留下一个元素，就是最终结果

对于计算机来说，基于栈，后缀表达式的计算是很方便的，比计算中缀表达式还要方便。因为给计算机一个后缀表达式，它并不需要判断哪些运算符是先生效的，只需要上述过程从左到右挨个算就行了

后缀表达式的应用范围十分广泛，它适用于基于栈的编程语言（如Forth,PostScript）,这些语言在进行算术运算时都用到了后缀表达式

• 后缀表达式怎么转中缀？

中缀表达式转前缀表达式（手算）

按照“右优先”原则确定的这些运算符的生效顺序和前缀表达式中各个运算符从右到左出现的次序是相同的

前缀表达式的计算(机算)

1.从右到左扫描下一个元素，直到处理完所有元素

2.若扫描到操作数则压入栈，并回到1，否则执行3

3.若扫描到运算符，则弹出两个栈顶元素（注意先出栈的是“左操作数”），执行相应运算，运算结果压回栈顶，回到1

若表达式合法，则最后栈中只会留下一个元素，就是最终结果

栈在表达式求值中的应用（二）

中缀表达式转后缀表达式(机算)

中缀表达式的计算(用栈实现)

中缀转后缀+后缀表达式求值 两个算法结合。中缀表达式转后缀表达式中的栈用于存放当前暂时还不能确定运算次序的运算符。后缀表达式求值中的栈用于存放当前暂时还不能确定运算次序的操作数。两个算法可以结合一边生成后缀表达式，一边计算后缀表达式前半部分的值

栈在递归中的应用

函数调用背后的过程

在任何一段代码和任何一段程序运行之前，系统都会给我们开辟一块函数调用栈（这个栈就是内存里的某一片区域）用来保存各个函数在调用的过程中所必须保存的一些信息

我们一般程序的入口是main函数，刚开始运行main函数会把main函数相关的一些必要信息压入栈中，比如main函数里的局部变量a,b,c，它们的值就会被存放入函数调用栈

接下来main函数会调用func1函数，程序执行func1里面的代码，等这些代码执行完后再执行c=a+b继续完成main函数。但这是我们肉眼所看见的，计算机解决这个问题的方式是它会在调用func1这个函数的时候把func1执行结束之后应该执行的这些代码的存储地址压到栈中，除此之外，函数调用的两个参数a,b也会被放到栈里面。这里就解释了在func1里面修改a,b的值为什么不能影响main函数里面的a,b值，因为这两个a,b不是一个东西。除了被调用函数的实参之外，函数里面定义的局部变量x也会被放到栈里面

接下来func1会调用func2。同样我们会记录下来func2执行结束之后我们应该回到哪一句继续执行。就把x=x+10086这一句代码的存放地址也放到栈里面。同时和刚才一样，这里面也要存储实参和局部变量的信息

等func2执行完毕之后，就可以从栈顶的信息得知再往后应该执行的是x=x+10086这句代码。这个函数执行结束之后，就可以把它的相关信息弹出栈也就是释放了这一部分内存空间

再往后的过程也是一样的，这就是函数调用背后所发生的一些事情，需要一个栈来支持

从我们的视角来看程序是从main函数开始的，但是实际上程序编译后，编译器会在main函数之前还给你加一些其他的代码，那些代码执行完毕才会执行main函数。上图图示中栈底的…就表示在main之前还要把一些我们不知道的信息压入栈底。用IDE调试程序的时候，可以设置断点并运行程序到断点处中止后可以在IDE里面观察函数调用栈目前有哪些信息

栈在递归中的应用

适合用“递归”算法解决：可以把原始问题转换为属性相同但规模较小的问题。如求斐波那契数列和阶乘。实现递归算法需要有两个比较重要的东西，一个是递归表达式，一个是边界条件，也就是递归的出口。我们在这里着重要探讨的不是如何设计一个递归算法，而是这个递归算法背后和栈有什么联系

由于内存的限制，太多层递归可能会导致栈溢出。递归层数越多，相应空间复杂度也会越高

 

由于递归算法背后就是用一个栈来实现的。因此可以自定义栈将递归算法改造成非递归算法。

 

通过观察上面例子中红色箭头表示的计算斐波那契数列时递归调用的先后顺序可以看到Fib(2)被计算了两次，同样的Fib(1)和Fib(0)也被重复了多次，从这个例子可以看出递归实现的算法有可能包含很多重复运算，这也是递归算法不太高效的一个原因

队列的应用

树的层次遍历

在“树”章节中会详细介绍

图的广度优先遍历

在“图”章节中会详细介绍

队列在操作系统中的应用

特殊矩阵的压缩存储

前三种属于方阵

一维数组的存储结构

二维数组的存储结构

采用行优先存储（一行存完再存下一行）或者列优先存储（一列存完再存下一列）把非线性的二维数组拉成一个线性的形状，因为计算机内存的存储空间都是线性的。这样有规律的存储数据就能实现随机存取，只要给出行号和列号，计算机就能立即算出这个元素的存储地址

如果采用列优先存储，计算方法也类似

普通矩阵的存储

可用二维数组存储

注意：描述矩阵元素时，行，列号通常从1开始；而描述数组时通常下标从0开始

对称矩阵的压缩存储

下面以主对角线+下三角区的压缩存储策略为例

考虑以下几个问题

• 数组大小应为多少？

显然等差数列求和易得为$\frac{n(n+1)}{2}$

• 站在程序员的角度，对称矩阵压缩存储后怎样才能方便使用？

可以实现一个“映射”函数，将矩阵下标映射为一维数组下标

• 怎么实现矩阵下标$\to$一维数组下标的映射呢?

情况一：$a_{i,j}(i\ge j)\to B[k]$，即访问下三角区和主对角线元素

按行优先原则，$a_{i,j}$是第$[1+2+...+(i-1)]+j=\frac{i(i-1)}{2}+j$个元素，故$k=\frac{i(i-1)}{2}+j-1$

情况二：$a_{i,j}(i<j)\to B[k]$，即访问上三角区元素

利用$a_{i,j}=a_{j,i}$的对称矩阵性质，可以化为访问$a_{j,i}$，得$K=\frac{j(j-1)}{2}+i-1$

• 如果按照列优先原则存储主对角线+下三角区呢？

其实思路是一样的，我们只要算出$a_{i,j}$是第几个元素就可以了，$a_{i,j}$之前应该有$j-1$列，每列分别有$n,n-1,n-2,...,n-j+2$个元素，把它们加起来就是前$j-1$共有多少个元素，此外不难发现$i-j$能得出同一列中在这个元素之前还有多少个元素，由于我们讨论的是这个元素是第几个元素，因此还要再加1。如果考虑到数组下标是从0开始的，则最终可得$k=\frac{(2n-j+2)(j-1)}{2}+i-j$

• 如果存储的是上三角区域呢？

类比上述过程自己推不难得

考试的时候不会看你背书背的熟不熟，存储上三角？下三角？，行优先？列优先？，矩阵元素的下标从0？1？开始，数组下标从0？1？开始等等都是可能出现的变种，要学会自己去推导

三角矩阵的压缩存储

以下三角矩阵为例

可以看见计算方法和对称矩阵几乎一模一样，得出的结果也类似，只不过访问上三角区区域时由于该区域为统一的常量C，因此访问这个区域的任何一个元素都应该把它映射到这个一维数组的最后一个位置

如果是上三角矩阵，计算思路也可以类比对称矩阵，不难得到如下结果

三对角矩阵的压缩存储

不难得出数组要能存储$3n-2$个元素，只要熟悉之前的计算思路，不难得出上图的结论

 

• 如果现在是已知数组下标，怎么得到对应的行号和列号呢？

王道书上的写法中$k$值可以理解为我们要找的元素前面一共有$k$个元素

算出$i$值后利用之前得到的结论$k=2i+j-3$可以求得$j=k-2i+3$

注意体会怎么处理不等式当中“刚好”大于等于和“刚好”小于等于的问题

稀疏矩阵的压缩存储

• 这样的三元组怎么顺序存储呢？

可以定义一个一个有$i,j,v$三个字段的$struct$，每个$struct$定义上面的一行，再定义一个和这个$struct$相对应的一维数组顺序的存储这些三元组了

显然用这种方式存储稀疏矩阵的话，要访问其中的一个元素只能顺序地依次扫描这些三元组，也就是会失去随机存取的特性

 

除此之外，也可以十字链表法存储稀疏矩阵。定义一个数组，数组里面存放的是一个个指针，把这些指针称为向下域，每一个指针都对应稀疏矩阵中的每一列。另外又定义一个指针数组，这些指针对应稀疏矩阵中的各行，每一个非零元素会对应一个结点，这个结点中包含非零元素所在的行列，值，还会有两个指针。下图中第一行的第一个非零元素是4，第一个向右域指针所指向的对应结点就是这个4，该结点的另一个指针指向同一行的下一个非零元素5，其他各行的结点也是类似的。向下域的原理也是相同的，不再赘述