考研数据结构：第三章 栈、队列和数组_考研题-第3章栈和队列-栈

---

一、栈

1.1栈的概念

1.1.1栈的定义

线性表是具有相同数据类型的n（n>=0）个数据元素的有限序列，其中n为表长，当n=0时线性表是一个空表。若用L命名线性表，则一般表示为
L=（a1,a2,…an）

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

先入后出就类似你装手枪弹夹，你先放入的子弹会在弹夹底部，最后放入的子弹是在弹夹顶部，你开手枪是先打出弹夹顶端的子弹。

1.1.2栈的基本操作

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为空，返回true，否则返回false

1.1.3栈的常见考题

如果所有元素都进栈后再出栈，那我们很容易就知道答案edcba

那如果进栈和出栈是穿插进行的呢?
具体解题思路：出栈的每一个元素的后面，其中比该元素先入栈的一定按照入栈逆顺序排列。举例说明：已知入栈顺序：1 2 3 4 5判断出栈顺序：4 3 5 1 2，结果：不合理，原因是出栈元素3之后有 5 1 2 这三个元素，其中1 2 是比3先入栈的，根据规律，这两个出栈的顺序必须和入栈顺序相反，也就是 2 1 出栈，不可能按照1 2 顺序出栈

来具体看几道例题

该题中c项，c后面是ab，我们知道比c先入栈的安装逆序出栈，应该是ba，所以c错误

同理，该题中d项，出栈顺序中c后面中的ab元素应该是ba的顺序

1.1.4小结

1.2栈的顺序存储实现

1.2.1顺序栈的定义

顺序栈既然是用顺序存储方式实现，那么它的实现方式就和顺序表很类似

#define MaxSize 10
typedef struct{
    ElemType data[MaxSize];//静态数组存放栈中元素
    int top;//栈顶指针
}SqStack;//Sq表示sequence顺序

void testStack(){
   SqStack S;//声明一个顺序栈
   //后续操作
}

1
2
3
4
5
6
7
8
9
10
11

在执行完SqStack S之后，就会在内存中申请一整片连续空间，如下图：

给各个数据元素分配的连续空间大小为MaxSize*sizeof（ElemType），

另外还需要分配一个整形大小空间给栈顶指针top
栈顶指针用于指向栈顶元素，一般用于记录数组下标。

举个例子，当前栈中已经压入了5个数据元素，
如下图所示，那么栈顶指针值就是4（第5个元素下标）

1.2.2初始化操作

分配了存储空间后，我们应该进行初始化操作。
刚开始的时候，栈里没有元素，我们top可以设置为-1
ps:如果你定义栈顶指针记录当前可插入位置也可以，那top初值就是0
具体还是看考试怎么要求，考试如果没明确规定，按照top初值-1来写

而判断一个栈是否为空，只需要判断它的top是否为-1即可

#define MaxSize 10
typedef struct{
    ElemType data[MaxSize];//静态数组存放栈中元素
    int top;//栈顶指针
}sqStack;

//初始化栈
void InitStack(SqStack &S){
   S.top=-1;//初始化栈顶指针
}

void testStack(){
   SqStack S;//声明一个顺序栈
   //后续操作
}

//判断栈空
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
16
17
18
19
20
21
22
23

1.2.3进栈操作

对于进栈操作，我们第一步应该判断栈是否已经满了，
而因为顺序栈是用静态数组方式实现的，静态数组是有一个最大容量上限的，
如果top=MaxSize-1，就说明栈已经满了

如果栈未满，我们让top+1,然后入栈元素赋给data[top]

#define MaxSize 10//定义栈中元素最大个数
typedef struct{
    ElemType data[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;//新元素入栈
   return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

1.2.4出栈操作

出栈也就是删除栈顶元素，可以用一个变量x返回出栈元素

出栈第一步，判断栈里面是否一个元素没有
也就是判断top是否=-1

如果栈中有元素，我们先把栈顶元素赋给x，再让栈顶指针top-1

#define MaxSize 10//定义栈中元素最大个数
typedef struct{
    ElemType data[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;//指针再-1
   return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

1.2.5获取栈顶元素操作

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

//读取栈顶元素
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

1.2.6共享栈

到这里，我们也可以清楚的发现顺序栈的缺点：栈的大小不可变。
怎么解决这个问题呢？我们除了可以用链式存储的方式来实现，或者把顺序栈初始大小设大一些
还可以用共享栈的方式来解决，并且提高资源利用率

所谓共享栈，就是两个栈共享同一片内存空间，我们设置两个栈顶指针，比如top0和top1

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

//初始化栈
void InitStck(ShStack &S){
    S.top0=-1;
    S.top1=MaxSize
}
1
2
3
4
5
6
7
8
9
10
11
12

我们给0号栈栈顶指针初值为-1,1号栈栈顶指针初值为MaxSize，如图所示

接下来，如果往top0里面放元素，我们让top从下往上走；
如果往top1里面放元素，我们让top1从上往下走，如下图所示

而共享栈也是有可能满的，如下图

判断共享栈是否已满，就是top0==top1-1

1.2.7小结

1.3栈的链式存储实现

本节我们将会学习如何用链式存储的方式来实现栈，链式存储的方式实现的栈叫作链栈

链式存储实现的栈，它本质上也是一个单链表，
只不过我们规定只能在单链表的链头端进行插入和删除操作，而链头这一端就对应我们的栈顶
比如进栈就对应单链表头插，出栈就对应单链表头删

1.3.1链栈的定义

链栈的定义和单链表定义几乎没有任何区别，只不过是名字稍微改一下罢了

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

和单链表类似的，我们使用链式存储方式来实现链栈时，我们也可以实现带头结点和不带头结点的版本，两种版本对于栈判空是不一样的。

进栈出栈对应单链表中的头插和头删，而如何头删和头插在笔者的线性表文章中讲的很清楚。
这是文章连接，需要可以自行查看，这里不过多赘述

1.3.2小结

二、队列

2.1队列的基本概念

2.1.1队列的定义

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

对队列的插入操作一般称为入队，队列的删除操作一般称为出队
听名字也很好理解，比如我们去食堂吃饭，要排队啊，
你排队肯定是在队尾从后往前排啊，而打到饭是从队头出去啊，如下图：

重要术语：队头、队尾、空队列

如果一个队列里面此时没有任何数据元素，那么这个队列就是一个空队列，如下图：

我们可以往队列中插入数据元素，允许插入数据元素的这一端就称为队尾，此时队列中最靠近队尾的这个元素就是队尾元素

那么相应的可以进行删除操作的那端就称为队头，最靠近队头的元素就是队头元素

队列的特点：先进先出(FIFO)，也就是first in first out

2.1.2基本操作

我们实现的对队列的基本操作其实是和线性表一样的，就是创销、增删改查。

InitQueue(&Q):初始化队列，构造一个空队列

DestroyQueue(&)：销毁队列。销毁并释放队列Q所占内存空间。

EnQueue（&Q,x）:入队，若队列Q.未满，将x假如，使之成为新的队尾。

DeQueue（&q,&x）:出队，若队列Q非空，删除队头元素，并用x返回。

GetHead（Q，&x）：读取队头元素，若队列Q非空，则将队头元素赋值给x。

QueueEmpty（Q）:队列判空，若队列Q为空返回true，否则返回false

2.1.3小结

2.2队列的顺序实现

2.2.1引子

我们知道，队列是一种特殊的线性表，它是操作受限的线性表。

如果用顺序存储方式实现，我们可以使用静态数组来存储队列中的数据元素，同时，由于操作受限，我们只能从队头删除元素，只能从队尾插入元素，因此，我们需要设置两个变量来标记队头和队尾

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

1
2
3
4
5
6

定义了队列的结构体之后，我们可以用变量声明的方式来声明这样的一个队列

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

执行了SqQueue Q；这句代码之后，系统会给我们分配下图这样的连续空间：

我们可以规定让队头指针指向这个队头元素，让队尾指针指向队尾元素的后一个位置，如下图：队列中有abcde5个元素，队头front值应该是0，rear应该是5

2.2.2初始化操作

既然队尾指针是指向接下来要插入元素的位置，队头指针指向队头元素。我们按照这样的设计逻辑，就可以在初始化的时候，让队尾指针和队头指针都指向0

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

//初始化队列
void InitQueue(SqQueue &Q){
     //初始化时，队头、队尾指针指向0
     Q.rear=0;
     Q.front=0;
}

void testQueue(){
    SqQueue Q;//声明一个队列（顺序存储）
    InitQueue(Q);
    //后续操作...
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

而因为队尾指针指向的位置应该是接下来应该插入数据元素的位置，那我们可以用队尾指针和队头指针所指向的位置是否相等 ，来判断这个队列此时是否为空

//判断队列是否为空
bool QueueEmpty(SqQueue Q){
   if(Q.rear==Q.front)//队空
       return true;
   else
       return false;
}
1
2
3
4
5
6
7

2.2.3入队操作

要入队的话，只能从队尾的方向让新元素入队，而由于我们的队列是由静态数组实现的，它的容量有限。所以当我们在插入之前，需要先判断一下这个队列是否已满，满了自然无法插入。
如何判断队列已满我们一会有具体讨论

来看一下怎么插入数据元素，比如我们现在有这样一个空队列：

第一步，把传入的参数x，也就是此次要插入的数据元素放到队尾指针所指向的位置

第二步，把队尾指针+1，也就是往后移一位

到这里就完成了一次简单的入队操作。
如果后面还要插入，那么rear指针就会依次往后移，当整个静态数组被填满，rear指针的值应该是10

那我们是不是可以认为队尾指针的值=MaxSize时，就认为队列是满的呢？（先告诉你是错的）

如果我们让队头的几个元素出队，那么我们的队头指针会依次后移，如下图

如果接下来有新元素入队，那么我们可以把它插入到前面的位置（数组下标012的位置）
而此时rear（队尾指针）等于MaxSize，该队列并没有存满，所以不能用rear=MaxSize来判断队列是否已满

再回到上面说的那种情况，现在数组下标012空出来了，那么怎么样让rear指针回到下标0呢？我们这里用一个取余操作
任意一整数x，x%n最终得到的余数都只能是0,1,2,…n-1
比如n=7，你任一个整数%7都只能得到0123456这7个数。
所以说取余运算x%n，其实就是把无限的整数域映射到有限的整数集合{0,1,2,…n-1}上

举个例子，下图中rear值为9，也就是指向了该数组的最后一个位置

接下来，新元素应该是插入到队尾指针所指位置，

接下来就是让rear=(rear+1)%MaxSize=(9+1)%10=0，这样rear又会回到下标0啦

用取余（有的地方也叫模运算），就可以把存储空间在逻辑上变成环装

由于这个队列的存储空间在逻辑上看是一个环状，是一个循环，所以我们可以把这种方式实现的队列称为循环队列（该术语可能在选择题中进行考察）。

如果还需要继续往这个队列中插入新的数据元素，我们需要把队尾指针（在逻辑上的环中）不断后移

当该队列还剩最后一个存储空间时，就认为此时队列已满。
队列已满的条件：队尾指针的下一个位置是队头，也就是（Q.rear+1）%MaxSize==Q.front
可能有同学会有疑问，下标2这里不是还有一个空闲的空间可以使用？往这里插入一个新的数据元素，同时让rear指针指向后一个位置不行？——需要注意的是，我们初始化的时候也是让front指针和rear指针指向一个位置，我们是通过front指针和rear指针指向一个地方来判断是否为空的，如果你这里也指向一个地方来判满是和判空产生矛盾的。所以我们必须牺牲一个存储单元

到这里就可以写出入队代码啦！

#define MaxSize 10//定义队列中元素的最大个数
typedef struct{
    ElemType data[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;//将x插入队尾
    Q.rear=(Q.rear+1)%MaxSize;//队尾指针后移
    return true;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

2.2.4出队操作

出队操作也就是删除一个数据元素，我们是在队头删除一个数据元素

首先要判断一下这个队列是否为空，如果为空则可以直接return false

如果不为空，先把队头指针指向的数据元素赋给变量x，后续用x返回

接下来，让front指针往后移一位
（这里也要对MaxSize取模，这样才能让front指针在逻辑上是个圈）

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

接下来每一次出队的都是front指针所指向的元素，并且队头指针依次后移

当队头指针和队尾指针再次指向同一位置时，就说明这个队列已经被取空了。（如上图）

2.2.5获取队头元素

获取队头元素很简单，先判断队列是否为空，如果不为空，那么就获取front指向的元素即可

//获取队头元素的值，用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

2.2.6判断队列已满/已空的三个方案

2.2.6.1方案一

队列已满的条件：队尾指针的下一位置是队头，即(Q.rear+1)%MaxSize==Q.front

而这种方案我们也可以很容易的用队头指针和队尾指针值来计算出队列中有多少数据元素：(rear+MaxSize-front)%MaxSize
这个也经常在选择题中考到，比如：

front=8,rear=2,MaxSize=10
(rear+MaxSize-front)%MaxSize=(2+10-8)%10=4
所以选A

当然这种方法的缺陷也显而易见，就是要牺牲一块空间来区别判空和判满，我们自己写代码这样完全没有问题。就怕考试出题人要求你不准浪费空间，就是接下来的方案二

2.2.6.2方案二

我们可以在队列中多定义一个变量size

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

用变量size来记录此时队列中存放几个数据元素，比如刚开始队列中没有数据，size=0

插入成功size++，删除成功size–

有了size之后，妈妈再也不用担心我front==rear了

2.2.6.3方案三

我们可以设置一个变量tag，

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

tag=0表示最近执行了一次删除操作
tag=1表示最近执行了一次插入操作

我们每次删除成功令tag=0，每次插入成功令tag=1
我们知道，只有删除操作会导致队空；只有插入操作会导致队满

举个例子，我们现在有如下队列，现在要往rear指向的位置插入元素

插入，成功后rear后移一位，tag置为1

此时我们rear==front，但是我们tag=1，我们就可以知道此时是队列满的情况
所以，我们所以我们队列判满条件：front= =rear&&tag= =1

相对的，队列判空条件：front= =rear && tag= =0

2.2.7一些考试注意事项

考试中的rear指针的具体含义是有可能变化的，我们上面介绍的rear指向下一元素插入位置
而出题人是有可能是让rear指向队尾元素的，入队操作也会有一些变化，大家注意区别

如果rear指向的是队尾元素，判空也是会出现一些变化

因为rear指向的是队尾元素，我们每次新元素入队，都是先让队尾指针向后移一位，再往里面插入数据元素

那么我们初始化的时候，front=0，rear=n-1。
因为你一开始没数据嘛，而我们实现的队列是一个环状，那么rear往后一位是0，那么rear之前应该是n-1，如下图：

同样，这里会出现一个问题，如果rear下一个位置==front判空，那么判满就没法直接判断了，我们可以通过牺牲一个存储单元或者增加辅助变量来解决问题。

2.2.8小结

2.3队列的链式实现

学完单链表之后，再来学习该小节其实是十分轻松的。队列和单链表相比，无非就是进行插入和删除操作的时候，队列只能在队头和队尾进行操作；而单链表的插入和删除是可以在任何一个位置进行的，所以队列其实是单链表的一个缩减版。

2.3.1定义

和单链表类似，实现队列时，我们也可以实现带头结点的版本和不带头结点的版本

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

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

这里在定义链式队列时，我们除了队头指针还设立了一个队尾指针，这是因为我们队列的插入操作永远是在队尾进行的。设立一个队尾指针就可以立即找到尾结点进行操作了。

带头结点和不带头结点的队列如上图，这种链式存储实现的队列，我们称为链队列

2.3.2初始化

2.3.2.1带头结点

typedef 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;
}

void testLinkQueue(){
   LinkQueue Q;//声明一个队列
   InitQueue(Q);//初始化队列
   //后续操作
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

先来看带头结点的版本，首先LinkQueue Q;声明一个队列对应的结构体，结构体里面有两个指针front和rear。

接下来对这个队列进行初始化操作，malloc申请一个头结点，并且让front和rear两个指针都指向这个头结点，再然后让头结点的指针指向NULL，示意图如下:

所以带头结点的队列判断是否为空，就判断front和rear是否指向一个结点即可，代码如下：

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

ps:你也可以通过判断front->next是否等于NULL来判断是否为空

2.3.2.2不带头结点

如果是不带头结点的情况，我们初始化的时候，要让rear和front都指向NULL，
判空就直接判断front或者rear是否等于NULL即可

//初始化队列(不带头结点)
void InitQueue(LinkQueue &Q){
   //初始化时front和rear都指向NULL
   Q.front=NULL;
   Q.rear=NULL;
}

//判断队列是否为空(不带头结点)
bool IsEmpty(LinkQueue Q){
   if(Q.front==NULL)
      return true;
   else
      return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

2.3.3入队

带头结点
入队，也就是插入操作，首先来看带头结点的怎么实现。

//新元素入队(带头结点)
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
8

现假设有如下空队列：

一个新的元素要入队，首先这个数据元素得被包含在一个结点中，所以我们malloc一个结点，让s指向该结点

再把数据元素x放到s结点中

由于队列的入队是在队尾进行的，那么新插入的元素肯定会成为队尾元素，也就是新元素的next会是NULL，我们这里让s结点指向NULL

接下来，由于rear指针指向的是当前的表尾结点，而我们新插入的新结点应该连到当前表尾结点之后。所以我们把rear的next指向s结点

最后，由于s结点成了新的表尾结点，我们让rear指向s结点

不带头结点
如果是带头结点的，我们插入第一个元素和后续元素，使用的代码逻辑都是一样的。但是如果是不带头结点的，在插入第一个数据元素或者第一个数据元素入队时就需要进行特殊的处理。

因为刚开始rear和front都是指向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
13

我们来看一下上述代码逻辑:
首先我们入队，那得先申请一个结点s，再往该结点中写入数据元素x，然后让s的next指向NULL

由于每次入队的新结点s都是队列中最后一个结点，因此需要让他的next指针域指向NULL，接下来需要进行判断当前队列是否为空。如果为空，则当前申请的s结点是队列中的第一个结点，我们修改front和rear指向，让它们都指向s结点

接下来如果还用其他结点要入队，其实就是对rear指针指向的结点进行一个后插操作。

2.3.4出队

带头结点

//队头元素出队
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

第一步，首先要判断这个队列是否为空，如果为空，则返回false表示出队操作失败，接下来让p指针指向此次要删除的结点，对于带头结点的队列来说，就是删除头结点的下一结点

然后把p的data赋给x（后面需要用x把被删数据带回去）

然后让头结点的next指向p的next

像上面这种情况，要删的p结点并不是队列中最后一个数据结点，所以我们直接把p结点释放掉即可

注意，如果此次删除的结点p是表尾结点（队列中只有一个数据元素，现在被删了）,那么我们需要进行特殊处理，也就是rear指向头结点（rear和front指向同一结点意味着队列为空），流程示意图如下：




不带头结点

//队头元素出队（不带头结点）
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

每次出队的是front指针指向的结点，由于没有头结点，因此每个队头元素出队之后，都需要修改front指针的指向。在最后一个结点出队之后，也需要把front和rear都指向NULL（也就是恢复成空队的状态）

2.3.5队满的条件

我们在队列的顺序实现中学到了如何用顺序存储实现下图中的循环队列

由于给这种循环队列分配的空间都是提前预分配的（用静态数组的方式分配的），因此它的存储空间是有限的、不可拓展的。

但是我们链式存储的队列，它的容量扩展非常方便，只要内存资源足够我们就可以继续为这个队列扩容。

所以我们链式存储就不用关心队满的问题了

2.3.6小结

2.4双端队列

双端队列其实也是一种操作受限的线性表，它是一种只允许在两端进行插入/删除的线性表，示意图如下：

本质上上图三种数据结构它们都是插入和删除操作受限的线性表，只不过对插入和删除的限制不同。

如果我们对双端队列的插入和删除只从一端进行，那么双端队列就退化成了栈，所以栈能实现的功能双端队列也一定能实现。

而由双端队列还可以演化成另两种不同的数据结构，如下图：

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

双端队列这里，如果考察，会让大家判断输出序列是否合法，例题如下：

如果输入序列为1234，那么4个元素排列组合总共有24种输出情况

我们来检查一下这24种中哪些是合法，哪些是非法的。

2.4.1.1栈的情况

我们刚才说过，如果只从双端队列的一端进行插入和删除，它就退化成了一个栈。所以栈满足的输出情况，双端队列也一定是满足的。

先来看一下1234是否合法：

我们先让1入栈，再让1出栈；
让2入栈，让2出栈；
让3入栈，让3出栈；
让4入栈，让4出栈；
所以这样的输出顺序正好是1234，这个输出序列是合法的

再看下一个，有没有可能输出2413呢？

如果第一个输出元素是2，是不是意味着1这个元素肯定在2之前已经输入了
我们这里先只讨论栈的情况（一端进行插入和删除）

因为这是题目规定的输入顺序啊，我们只能让1先入栈，然后2再入栈，接下来2出栈


再往下要输出4这个元素，既然要输出4，那么得先把3压入栈中，然后把4压入栈中，再出4


到这里如果还要出栈，那肯定是3啊
所以对于栈的情况，2413是不对的

最后看一个例子，4321
如果4是最先出栈的，那么意味着123已经入栈

接着4入栈，再出栈


而里面的三个元素顺序已经是不可以改变了，所以出栈只能按照321，所以4321是合法的。
4开头的其他输出序列都是不合法的

这里帮大家标注出来，输入1234，栈的合法输出情况。
绿色为合法，红色为非法
具体解题思路：出栈的每一个元素的后面，其中比该元素先入栈的一定按照入栈逆顺序排列。
举例说明：已知入栈顺序：1 2 3 4 5判断出栈顺序：4 3 5 1 2，结果：不合理，原因是出栈元素3之后有 5 1 2 这三个元素，其中1 2 是比3先入栈的，根据规律，这两个出栈的顺序必须和入栈顺序相反，也就是 2 1 出栈，不可能按照1 2 顺序出栈。

我们之前讲过一个东西，卡特兰数，用卡特兰数可以算出n个元素的输入序列有多少种合法的出栈序列

比如，我们这里有4个元素，n=4，那么用卡特兰数算出来的合法出栈序列和上面绿色标注的序列数量是一样的，都是14

ps：考试不用担心让你列出所有的合法出栈序列，一般都是给选择题给几个序列让你判断是否合法。不过卡特兰数公式建议还是记一下，不要求证明，会求即可。

2.4.1.2输入受限的双端队列的情况

我们在栈中已经验证过如下的合法输出序列，栈中合法的在双端队列中也合法（不管双端队列是否受限）

所以接下来只需要验证栈中不合法的情况即可
先看1423是否合法：
先输出1，那么我们先把1入队，再出队（出队你从哪端都可）


接下来是输出4，而输出4之前你23得先进去啊，而由于只能一端插入，所以234在这个队列中如下图：

然后要输出4，就从右边删除即可

然后输出2，从左边删除

最后是输出3，左边右边删除都可以

所以1423这个序列是正确的

再看一个例子：3142
首先要输出3这个元素，就意味着123这三个元素在输出之前已经输入到该队列中。

然后输出3，把3从右边删除

然后输出1，把1从左边删除

接下来要输出4，此时队列里面没有4，那么我们让4入队再出队


最后输出2，左边或者右边删除都可以

所以3142这个序列是合法的

再看4213的例子

第一个输出是4，那么1234在4输出前，已结是入队了

接下来输出4，就从右边删除4

输出4后，只能输出1或者3，所以4213肯定是错的
同理，4231也一定是错的

下图中，我们下划线标注的序列是在栈中非法但是输出受限的双端队列中合法的

2.4.1.2输出受限的双端队列的情况

同样的，对于输出受限的双端队列的情况，我们只要验证在栈里面非法的序列。

先来看一下1423有没有可能出现
第一个要输出1，那么1先入队再出队即可


接下来是输出4，那么234得先入队
而由于只能一端出队，又因为我们出队序列是423
所以我们在队列中元素应该是下图这样

那么1423是否正确就取决于交替插入是否能形成324的排列了
先让2入队（左边或者右边进去都可以）

再让3从左入队

最后让4从右入队

最后423依次出队就成了

来看一下3142的情况
首先是输出3，所以在3输出前123都得先入队，而由于只能一端出队，所以队列中元素必须如下图

我们可以先插入1，再从左边插入2


接下来就是3出队，从右边插入3，再删除3



接下来1出队

再然后要4出队，此时队里面是没有4，那我们就先入4再出4即可


最后出2就ok了

所以3142是成立的

同样的，下面图片中下划线的序列是栈中不合法，但输出受限的双端队列合法的情况

不知道大家有没有发现，我们在对上图这些序列进行验证时，如果你在输出序列中看到某一个序号的元素，那么在这个元素输出之前，意味着它之前的所有元素都已经输入到该队列中了。

比如上图中第三列都是3开头的序列。3先输出，那么3输出之前1和2的位置都是确定的。

由于只能右边出，所以如果给的输出序列是12，那么肯定是1在右2在左

接下来就是想办法验证两边的插入能否拼凑出你所需要的顺序了。

2.4.2小结

三、栈和队列的应用

3.1栈在括号匹配中的应用

什么是括号匹配问题？如下图，我们写了一段代码，而IDE是报错了。
ps：IDE（可视化编程环境），你可以简单理解为你写代码的东西

大家应该知道，我们写代码时的小括号、中括号、大括号都应该是成双成对出现的，而上图中是少写了一个（右）括号，所以会报错

如果加上了右括号，报错就消失了

写代码的过程中，必须保证我们代码中的括号是成双成对出现的。而除了左括号和右括号数量一样，我们的括号类型也需要匹配，你总不能左边大括号右边小括号吧。

我们先用手算的方式来分析一下括号匹配问题，下图中，四个左括号，四个右括号。我们人第一反应就是从里往外依次匹配。

这是我们人脑的反应，如果是计算机来匹配的话，它是只能从左到右依次扫描

括号匹配过程中，我们不难发现这样一个规律，越往后出现的左括号越优先被匹配。

比如我们从左到右依次扫描，扫描了4个左括号，那么再往后扫描到一个右括号，这个右括号是与最后出现的左括号，也就是4号左括号进行匹配。如果再往后扫描，扫描到一个右括号，这时，3号左括号进行匹配。

该算法的特性和我们栈的后进先出有异曲同工之妙，就是后面的左括号，优先与右括号匹配嘛。我们可以把这些左括号依次压入栈中，然后越往后压，入栈的左括号越先被弹出栈，越先被匹配。

再来看一个例子：

当扫描到第一个右括号时，我们找最后出现的左括号，也就是这里的3号

继续往后扫描，后面一个还是右括号，我们从3号往前找最后出现的左括号，也就是这里的2号

后面过程是类似的，每当出现一个右括号，就需要消耗一个左括号，这样的消耗操作对应出栈的操作

我们来用一段动画，来观察一下几个实际的例子：
例1：所有左括号匹配右括号，且括号类型均能匹配

上面这段动画中，我们依次扫描这些括号，如果遇到左括号，就把它压入栈中；如果遇到右括号，就需要弹出栈顶元素，然后与扫描到的右括号进行匹配，匹配需要注意是否括号类型一样，小括号只能匹配小括号。

例2：括号类型不匹配

该段动画中，我们依次扫描这些括号，如果遇到左括号，就把它压入栈中；如果遇到右括号，就需要弹出栈顶元素，然后与扫描到的右括号进行匹配。
但是和例1不同的是，这里的括号匹配出现了小括号匹配中括号，显然是有问题的，所以后面也不用继续匹配了，直接return即可。

例3：匹配所需左括号缺失

该例中，我们匹配到右括号时，发现栈中已经没有左括号可以弹出并与之匹配了，这里也是有问题的，后面也不用继续遍历了，return即可。

例4：匹配所需右括号缺失

该例中，我们遍历完所有括号之后，发现栈里面还有左括号，说明这时候是右括号不够左括号匹配了，这种也是错误的情况。

下图是一个括号匹配问题的流程图

算法实现：

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

//下面的4个函数，在栈那块已经讲过，需要可以自行查看
//考试周可以直接使用基本操作，简要说明接口即可
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){
//str是一个字符数组，里面存储了各种左括号和右括号
//len表示该字符数组有多长
   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
37
38

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

3.2.1引子

表达式求值问题，一共有三种算术表达式：中缀表达式、后缀表达式、前缀表达式。常考的一般是后缀表达式，下面我们会对三种表达式逐一介绍

先来看看最熟悉的中缀表达式

举个例子，上图这种我们熟悉的算术表达式中有三个部分：操作数、运算符、界限符
很好理解，操作数就是上面的各个数字；运算符就是加减乘除那些运算符；界限符就是这些括号。

界限符（括号）的存在其实就是表名了各个运算符生效的顺序，那么显然，在上图这个式子中，我们首先该运算加法，加法计算和计算减法。。。

而一旦我们将括号去掉，这些运算符生效的次序就会发生改变了

显然，该种情况下，应该先计算除法，然后是减法，再是加法。。。

总之，在我们熟悉的中缀表达式中，界限符的存在是必须的

而又一位波兰数学家就想到了不用界限符也能表达正确的运算顺序的两种方法，也就是我们后面要学的前缀表达式和后缀表达式

3.2.2前、中、后缀表达式

下图是我们前中后缀表达式的规则：

我们举两个例子大家就明白了，比如我们现在有中缀表达式a+b-c*d，如何把它转成后缀表达式和前缀表达式？

中缀转后缀：首先我们中缀表达式中+是先运算的，中缀中是a+b，我们后缀应该是ab+，然后我们把ab+看成一个整体即可；接下来是 * 运算，后缀中应该是cd * ，再把cd * 看成一个整体；最后ab+和cd *两个整体相减，也就是ab+cd * -

中缀转前缀：首先我们中缀表达式中+是先运算的，中缀中是a+b，我们前缀应该是+ab，然后我们把+ab看成一个整体即可；接下来是 * 运算，后缀中应该是 cd ，再把 * cd看成一个整体；最后+ab和 cd两个整体相减，也就是-+ab * cd

需要注意的是，在中缀转前缀或者后缀时，我们这里只能改运算符的位置，不能改操作数的位置。比如ab+你改成ba+好像没什么问题，但是如果是ab/你改成ba/问题就很大了。

3.2.3中缀表达式转后缀表达式

通过上图我们可以发现一个规律：中缀表达式中，加法是第一个生效的，减法第二，除法第三。。。
在转成后缀表达式后，这些运算符在后缀表达式中都是从左到右排列的。

举个例子：

上面这个表达式中，我们下意识是先算减法，然后是乘法，再然后是加法，接下来是除法，最后是减法，顺序如下图：

我们把它转换成后缀表达式应该是(A (B (CD-)*) +) (EF/)-
也就是A B C D - * + EF/-
上面用括号是方便把它看成一个整体，计算过程中比较方便观察，最后你填答案把括号去掉即可。

最后你会发现，和之前统一的规律，在后缀表达式中，各个运算符出现的先后顺序刚好和我们中缀表达式中运算符生效的先后顺序是一一对应的。

我们知道，中缀表达式运算顺序不一定唯一，所以对应的后缀表达式也不唯一，来看一下下面这个表达式运算顺序

该顺序中，我们先算除法，然后是括号中的减法，再然后是乘法，接下来是减法，最后加法。

生成的后缀表达式为：A((B(CD-)*) (EF/)-)+
去掉括号之后就是ABCD- * EF/-+

可以看到，如果我们让运算符按照这种顺序来依次生效，那么得到的后缀表达式的顺序也是挺难看的。

客观来讲，如果是手算，上图这两个后缀表达式运算结果肯定是一样的，但如果我们要用计算机实现中缀转后缀的算法，只应该得到一种输出结果，我们肯定是采用左边这种。（算法又一个必须具备的特性叫作确定性，同样的输入只能得到同样的输出，考试验证算法是否正确也是按左边这种）

那么左边这种运算顺序的确定有什么规律？给大家一个独门秘方：左优先原则
所谓的左优先原则就是：只要左边的运算符能先运算，就先运算左边的

我们知道，中缀转后缀，由于运算顺序不唯一，所以生成的后缀表达式也不唯一，但是如果我们引入左优先原则，就可以保证运算。

来看一个具体的例子：

我们这里采用左优先原则，那么先算A+B，转后缀就是AB+；
然后从左往右是乘法，算C * D，转后缀就是CD * ；
接下来是除法，也就是((CD *)E/)；
再接下来是左边的减法，(AB+) ((CD * )E/)-
最后是右边的加法，((AB+) ((CD *)E/)-)F+

我们把括号去掉，AB+ CD *E/-F+

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

当我们得到一个后缀表达式时，怎么通过后缀表达式计算出他的最终结果呢？

我们还是用之前的例子，把中缀和后缀放在一起方便对比：

从中缀表达式的角度，第一个应该计算的是1+1，那么我们后缀表达式从左往右扫描第一个出现的运算符就是加法，而加法的两个操作数正好是后缀表达式中+前面两个数 1 1。这样我们就消耗了一个运算符，并且将两个操作数合并为一个操作数

接下来的运算就是7-(1+1)，也就是7-2。类似的，你会发现，从左往右扫描第一个运算符是减号（加号已经在上一轮被消耗掉了），而后缀表达式中减法前面两个数也是7-2

再往后从左往右扫描，扫描到除号，就是15除以后面的一坨

接下来以此类推

3.2.4后缀表达式的计算（机算）

接下来要思考的问题是，如何用代码实现刚才我们说的后缀表达式的计算过程？刚才我们提到，我们会让离运算符前面最近的两个操作数进行相应的运算，也就说越往后出现的操作数，越先被运算。这就是和栈的后进先出吻合上了。

来看一个例子，我们现在有如下运算和一个栈


首先从左到右扫描后缀表达式，先扫描到了一个操作数A，而只要是操作数我们就压入栈


继续扫描，扫描到B，B是一个操作数，放到栈里面


继续往后扫描，扫描到运算符+，而扫描到运算符要弹出两个栈顶元素，执行相应运算，运算结果压回栈顶



继续往后扫描，扫描到C，放入栈中


继续扫描，扫描到D，放入栈中


再往后扫描，扫描到操作符 *，那么弹出栈顶两个元素，进行乘法操作，再把结果压回栈中



后面以此类推，不再赘述

3.2.5前缀表达式的计算（手算）

中缀转后缀明白后，中缀转前缀也很好理解了。
以A+B * (C-D) -E / F为例
先确定中缀表达式中各个运算符的生效次序，

然后按照前缀表达式的规则，把他们一一组合。比如C-D转成-CD，然后把-CD看成一个整体

接下来生效的是乘法，即 * B(-CD)

接下来生效的是加法，即 + A（* B(-CD)）

接下来生效的是除法，即/ E F

最后是减法，生成-（ + A（* B(-CD)））（/EF）

然后我们把括号去掉，就是答案-+A * B -C D / E F

可以发现这些运算符的生效顺序在前缀表达式中看，好像没有任何规律。但是如果我们按照右优先原则来规定运算符生效顺序，那么我们就会得到一个很舒服的结果，

右优先和左优先类似：只要能右边运算符能优先计算，就先计算右边
那么按照右优先的规则，我们的运算可以有下面的顺序

那么我们生成的后缀表达式如下，运算符从右到左依次生效

3.2.5前缀表达式的计算（机算）

我们这里用一个例子来简单演示一下，现有一个中缀表达式，然后们给它转成前缀表达式，如下图：

我们从右往左进行扫描，扫描到1，1入栈


继续从右往左扫描，扫描到1，1入栈


继续扫描，扫描到+，弹出栈顶两个元素，进行运算，再把运算结果压回栈中


接下来，继续从右往左扫，扫描到2，2入栈


继续扫描，扫描到+，弹出栈顶两元素，进行操作，把结果返回栈中

注意，这里先弹出的是左操作数


再次强调，这里左右操作数顺序不能换，这里加法你看不出来，如果是减法或者除法问题就很大了。
后续过程不再赘述，以此类推

3.2.6小结

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

3.3.1中缀表达式转后缀表达式（机算，用栈实现）

先来回顾一下中缀表达式转后缀表达式（手算）是怎么实现的，如下图：

那接下来，我将介绍中缀表达式转后缀表达式如何用计算机的算法来实现，下图先给出方法，后面会具体进行介绍：

可以发现，在中缀表达式转后缀表达式时，中缀表达式这些操作数出现的顺序是ABCDEF，然后变成后缀表达式还是ABCDEF，这些操作数的相对顺序不会改变。但是运算符之间的相对运算顺序是会改变的

我们用一个栈来存储当前暂时还不能确定运算顺序的运算符。

关于上图中的情况三：当遇到运算符，一次弹出栈中优先级高于或等于当前运算符的所有运算符。这里解释一下，我们的运算符加减乘除，是有所谓的优先级的，显然，乘除的优先级高于加减嘛，然后乘除两个优先级是相同的。

举个例子：
现在有如下的中缀表达式和一个栈

我们从左往右依次扫描中缀表达式中的各个元素，

如果我们扫描到的是一个操作数，则把它直接输出到后缀表达式中，比如我们刚开始扫描到A，如下图，直接输出A即可

接下来往后扫描，扫描到一个运算符+，由于此时栈是空的状态，所以我们可以直接把这个运算符压入栈中。

继续扫描，扫描到操作数B，直接输出即可

继续扫描，扫描到一个运算符-，由于此时栈是非空的，所以要依次弹出栈中比这个运算符优先级高或者同级的运算符。
此时栈顶的运算符是加号，加号和减号优先级相同，我们弹出加号

然后还要把扫描到的减号放回栈中

解释说明：在中缀表达式中，除了第一个和最后一个操作数，操作数两边都是有运算符的，比如A+B-C。
我们这里处理中缀表达式的时候，是从左往右依次扫描的，所以如果之前这个栈里面是一个+，在这个加号后面扫描到一个减号，那么就可以说明加号和减号之间有一个操作数。

比如A+B-C，这个B就是+和-中间那个操作数，而这个操作数既要进行加法运算，也要进行减法运算。而由于这两个运算优先级是相等的，根据我们前面提到的左优先原则，就可以大胆的先让操作数B进行左边运算符+的运算，所以我们就可以把+先弹出栈。

而我们也知道，后缀表达式中各个运算符出现的先后顺序是它们生效的优先顺序，所以A+B-C中，先弹出+，意味着让加法先生效。其实我们在中缀表达式中就相当于要把A+B看成一个整体了

继续往后扫描，C是一个操作数，直接输出

再往后，扫描到一个乘号 * ，而经过检查发现，栈中是一个减号-。这就意味着，当前扫描到的乘法，它左边的操作数前面的运算符是一个减法。

我们知道先乘除后加减，所以这里不能把减号弹出栈。因为如果减号弹出栈，就意味着减号比乘号先生效，不符合运算规则。那能不能直接把这个乘号 * 放到栈里面再弹出来呢？也不可以，因为如果乘法后面有一个括号，乘法的优先级就不是最高了，比如A * （B-C）

所以，当我们扫到这个乘号 * 我们是暂时不能确定它能不能先运算，所以先把它压入栈中。

继续往右扫描，扫描到操作数D，直接输出即可

继续往后扫描，扫描到一个运算符除号/，类似的，我们检查栈顶元素，发现是一个乘号，那么就意味着除号左边的操作数，再左边是的运算符是一个乘号 * ，比如这里C * D / E。

当D既需要乘也需要除的时候，由于乘法和除法的优先级是相等的，我们根据左优先，先让左边的乘法生效，也就是把栈中的乘号弹出，乘法生效后，就需要把C * D 看成一个整体

前面也说了，A+B的加法也生效了，A+B也应该看成一个整体，图示如下：

这时，再检查，发现栈顶元素是一个减号-，就说明除号左边的操作数再左边的运算符是一个减号，如下图。

虽然除法的优先级比减号更高，但是我们并不能确定除号后面有没有括号之类改变优先级的东西，所以这里也不能直接弹出除号/，还是得把除号放到栈里

接下来继续扫描，是操作数E，直接输出

继续扫描，是运算符加号+，检查栈顶元素发现是除号/，就说明加号左边的操作数再左边的运算符是除号。那么该操作数既需要除也需要加，那么我们就可以确定，应该让除号先操作。那么就可以大胆的把除号弹出来了，弹出除号就意味着除号生效了，就需要把前面的部分看称整体了，如下图：

这时候再看栈顶元素是一个减号，而我们现在扫描到的是一个加号啊，就说明加号左边的操作数再左边是减号，减号是和加号同优先级的，根据左优先，先运算减号，那么弹出减号

再接下来，是最后一个操作数F，直接输出即可。

当所有的都遍历完了，把栈里面剩余的操作符依次弹出即可

到这里就得到了最终的后缀表达式，和手算得到的后缀表达式是一样的。

3.4栈在递归中的应用

学过c语言应该都知道，递归算法其实就是递归函数调用它自己的一个过程，所以递归的过程本质就是函数调用的过程，我们下图这样一个简单的函数调用让大家理解一下，也将用下图这样一个简单的函数调用进行讲解：

如上图所示，大家可以看到函数调用的一个特性，最后被调用的函数最先执行结束（LIFO），这个特性就和栈的后进先出一样了。

事实上，在我们任何一段代码或者程序运行之前，系统都会给我们开辟一个函数调用栈，用这个栈来保存各个函数在调用过程中所需要的一些信息：1.调用返回地址，2.实参，3.局部变量


我们知道，程序的入口是main函数，那么运行main函数时，会把main函数相关的信息压入栈中，比如main函数里面的局部变量abc。而下图可以看出，main函数之前还需要把一些东西压入栈中（不过作为程序员你不用管这些）

接下来main函数调用func1()函数，同样的存储一些必要信息，这里的#1是func1()函数的地址，后面需要返回
而这里func1放进去的ab也就是新的实参，这里的ab和main里面的ab是不一样的。
另外再把func1里面的局部变量x放进去

再接下来func1调用func2，把func2相关信息放入栈中

func2执行完，弹出栈

func1调用func2结束，然后func1把剩余代码执行完，弹出栈

到这里大家就明白函数调用栈的基本原理了，本节着重探讨栈在递归中的应用，我们很多问题都可以通过递归算法来解决，使用递归算法的特点：可以将原始问题转换成属性相同，但是规模更小的问题

3.5队列的应用

队列的应用涉及其他还未学习的数据结构，这些我们会在后面进行详细介绍，这里只是简单介绍一下思路和方法。

3.5.1树的层序遍历

在后面的章节中，我们会学到一种数据结构“树”，这里我们会简单介绍一下，后面学到树的时候我会详细进行介绍。

不难发现，树这种数据结构是分层的，如果我们要进行层次遍历：就是一层一层的遍历树中的各个节点，如下图：

要实现层次遍历，就需要先队列的帮助。来简单看一下层次遍历的基本思想：先创建一个队列，然后从根节点出发，按层次进行遍历。

首先被遍历的是根节点（1号结点），在遍历到1号结点时，我们就需要把该结点的左右孩子结点（2号和3号）入队，然后1号结点出队

接下来，检查队头结点（2号结点），同样的把2号结点的左右孩子结点（4号和5号）入队，然后2号出队

再往下，检查队头结点（3号结点），同样的把3号结点的左右孩子结点（6号和7号）入队，然后3号出队

再往下，检查队头结点（4号结点），但是4号结点没有孩子结点，所以直接让4出队

后面以此类推，不再赘述。

按照层序遍历的顺序，我们每处理一个结点，都需要把该结点的左右孩子结点放到队尾，然后我们每次遍历处理的是队头的那个结点。这样我们就可以用队列完成树的层序遍历。

3.5.2图的广度优先遍历

现在有如下的图，假设我们从1号结点出发来按广度优先的方式遍历图里面的各个结点，我们这里也创建一个队列来辅助：

刚开始要遍历的是1号结点

当我们遍历一个结点时，就需要检查和这个结点相邻的其他结点有没有被遍历过，现在2号和3号结点没有被遍历过，所以可以把他们放到队列队尾

和刚才类似，处理完1号结点就可以让它出队了

接下来是2号结点，类似的，检查2号结点相邻结点中有没有还没有被遍历过的结点，这里1号已经被遍历过了，但是4号还没被遍历，把4号放入队尾。然后2号出队。


再往后，遍历到3号结点，检查3号结点相邻结点中没有被遍历过的，发现5号和6号还没有被遍历过，加入队列。然后3号出队


接下来处理4号结点，显然和4号相邻的都被遍历过，那么4号直接出队

接下来是5号，和5号相邻且没有被遍历的就是7号和8号，将其加入队列，然后5号出队


后续的遍历都不会加入任何结点了，直到整个队列为空就完成了图的广度优先遍历。

3.5.3队列在操作系统中的应用

我们操作系统需要管理系统中的一些硬件资源，比如CPU和一些I/O设备等。但这些资源是非常有限的，而我们系统中会有多个进程并发的运行，这些资源都会争抢的来使用这些系统资源，那么操作系统是如何分配系统资源的呢？

一个很常用的策略就是先来先服务，就是哪个进程先申请系统资源我就把这个资源分配给哪个进程。

这种先来先服务的思想就和队列的先进先出是一样的了，因此，要实现先来先服务的管理策略，其实一般都是需要用一个队列来辅助完成。

比如，我们CPU资源其实是有限的，但是系统中可能同时启动了多个进程。那么操作系统会让这些进程排成一个所谓的就绪队列，如下图：

然后每次选择队头元素，让他上CPU执行一个较短的时间片，然后迅速的下CPU，再回到队尾


接下来让下一个进程上CPU，运行一小段时间，之后再下CPU


这样循环往复，你的所有进程都可以轮流得到CPU服务了

四、数组和特殊矩阵

4.1数组的存储结构

4.1.1一维数组

4.1.2二维数组

4.2特殊矩阵的压缩存储

对于普通的矩阵，我们可以直接用二维数组进行存储，需要注意的是我们数组下标从0开始，而描述矩阵时，行号和列号一般从1开始。

4.2.1对称矩阵

对称矩阵是什么？首先，它是一个方阵，也就是说n行n列
另外由于是对称矩阵，所以该矩阵中的任一元素都有a[i][j]==a[j][i]

也就是说这种矩阵关于主对角线对称

我们刚才也说了，我们可以用一个二维数组来存储这个矩阵的数据。而由于对称矩阵两个三角区数据完全相同，所以在存储对称矩阵数据时，我们只需要存储两三角区其中一个，再加上主对角线上数据即可。

那我们设置一个一维数组，可以按照行优先原则把这些元素依次存进去。所谓行优先，就可以先存第一行，再存第二行，再存第三行…示意图如下：

而接下来就是要探讨两个问题：
1.我们设置的一维数组应该设置多大？

可以看到，第一行1个数据，第二行2个数据，第三行3个数据…而由于是n阶矩阵一共n行，那么到第n行共1+2+3+…n=(1+n)*n/2

2.站在程序员角度，对称矩阵压缩存储后怎样才方便使用？
站在程序员角度，我们把一个矩阵的数据存储后最终目的就是想要用这些数据。

当你在用这些数据时，你肯定希望以你的视角看到的是一个矩阵，而不是一个一维数组。也就是说，你是想用矩阵的元素下标来访问各个元素的，比如a32你知道是矩阵中3行2列的位置，但你不能直接知道a32在一维数组哪个下标啊。

为了实现这个目的，很简单的一个方法，你可以自己实现一个映射函数，你输入一个矩阵下标，可以获得其一维数组下标。

我们来探讨一下，下三角按照行优先原则，aij是一维数组中第几个元素
首先aij的i是行号，说明前面还有i-1行，那么前面一共是1+2+3+…(i-1)=(1+i-1)*(i-1)/2

然后aij的j是列号，反应了它在i行第j个

那么aij对应的应该是第(1+i-1) * (i-1)/2+j个，而数组下标是从0开始的，所以aij在一维数组中下标(1+i-1) * (i-1)/2+j-1，即i * (i-1) /2+j-1

讨论完下三角，继续讨论，上三角的情况

如果要访问上三角，我们实际存的是下三角嘛，如下图

如果要用下三角这样的一维数组来访问上三角元素，因为是对称矩阵所以aij=aji，所以我们可以把上三角元素转成下三角，同样的可以用刚才的方法算出aij的实际存放位置即j*(j-1)/2+i-1

这里具体公式不需要死记硬背，你知道怎么推就行，考场上也能很快推出来。

4.2.2三角矩阵

三角矩阵也可以分为下三角矩阵和上三角矩阵，如下图

看图很好理解，所谓下三角矩阵就是除了主对角线和下三角区，其余的元素都相同。

然后上三角矩阵：除了主对角线和上三角区其余元素都相同

也就是说，我们重点存储的是下三角的下半部，上三角的上半部。这样的话，这些数据的压缩存储方法就和刚才的对策矩阵是一样的了。

4.2.3三对角矩阵

三对角矩阵，又称带状矩阵。这种矩阵的特点就是行号和列号之差大于1时，那么元素值均为0

直观看的话，所谓带状矩阵或者三对角矩阵就是，所有在主对角线上的元素可以是非0元素，另外，从主对角线出发，与它们相邻的元素也可以是非零元素，如下图：

基于这种特点，我们只需要存储带状矩阵的非零元素即可，思想都是类似的。比如我们可以行优先原则，一行一行的存储这些非零元素，把它们依次存到一个一维数组中，如下图：

不难发现，对于带状矩阵来说，除了第一行和最后一行只有两个元素之外，其他每一行都有三个元素。所以一个n阶的带状矩阵，我们需要存储的元素个数应该是4+(n-2)*3=3n-2，由于数组下标是从0开始，所以最后一个元素下标应该是3n-3

接下来要解决的问题就是怎么把行号和列号映射为与之对应的数组下标了。

如果要访问的元素，行号和列号差值大于1，这种情况都不用去数组里面找，该元素肯定就是0。

如果要访问的元素，行号和列号差值小于等于1，我们就看aij这个元素按照行优先规则是第几个元素即可。

现假设要确定aij是数组中第几个元素，第一行2个，第二行到第i行每行3个，所以前i-1行共2+(i-2) * 3=3i-4个元素，然后aij是第i行第j-i+2个，所以aij是第2i-2+j。考虑到数组下标从0开始，所以aij的数组下标为2i-3+j

下面是已知数组中元素下标，确定其在第几行第几列

4.2.4稀疏矩阵

稀疏矩阵就是指非零元素个数远远少于矩阵元素的个数，如下图

如果我们定义一个和矩阵大小一样的数组，其中很多0其实就是浪费空间。所以我们只需要存储非零值的位置就很节约空间了，如上图所示。

还有一种方法就是十字链表法，如下图

4.2.5小结