【3.1】栈和队列

前言

栈和队列是线性表的另一种变形，它拥有一些各自的特点。

如下所有代码需要做如下引用：

#include <stdio.h>
#include <stdbool.h>
#include <malloc.h>

//如果你使用的是Visual Studio，则还需要添加如下一条引用
#define _CRT_SECURE_NO_WARNINGS

关于上述引用的说明，原因参考关于C语言的一些零碎思考

栈

栈的基本概念

栈的定义

栈(Stack)本质来说还是一种线性表，栈是只允许在一端进行插入或者删除操作的线性表。

• 空栈：栈中不存储任何数据
• 栈顶：栈的最顶端
• 栈底：栈的最低端

栈的特点：后进先出（Last In First Out，LIFO）

栈的基本操作

操作	说明
InitStack()	初始化栈。创造一个空栈，分配内存空间
DestoryStack()	销毁栈。销毁并释放栈所占的内存空间
Push()	进栈。如果栈未满，则将新元素压入栈顶
Pop()	出栈。如果栈不是空栈，则将栈顶元素弹出栈
GetTop()	读取栈顶元素。
StackEmpty()	判断是否为空栈。

栈的实现

栈的顺序存储实现

类似于线性表的顺序实现，不过使用的是栈的规则，即后进先出。

栈的结构

#define Maxsize 10  //栈的存储数量
#define ElemType int    //栈存储的数据类型

//栈的结构
typedef struct stack
{
    ElemType data[Maxsize]; //存放栈的元素
    int top;    //栈指针
}Stack;

初始化栈

//初始化栈
void InitStack(Stack * s){
    s->top = -1;    //表示栈为空栈
    printf("初始化栈:成功\n");
}

进栈（压入栈）

//压入栈（进栈）
void Push(Stack *s,ElemType data){
    if(s->top == Maxsize-1){
        printf("栈已满，进栈失败\n");
    }
    s->data[s->top + 1] = data;
    s->top++;
    printf("元素 %d 入栈：成功\n", data);
}

出栈（弹出栈）

//弹出栈（出栈）
ElemType Pop(Stack *s){
    if (s->top == -1)
    {
        printf("栈为空栈，弹出失败\n");
        return -1;
    }
    s->top--;
    printf("栈顶元素 %d 弹出成功\n", s->data[s->top + 1]);
    return s->data[s->top + 1];
}

销毁栈

//销毁栈
void DestoryStack(Stack *s){
    s->top = -1;
    printf("销毁栈成功\n");
}

读取栈顶元素

//读取栈顶元素
ElemType GetTop(Stack *s){
    printf("读取栈顶元素: %d\n",s->data[s->top]);
    return s->data[s->top];
}

判断空栈

//判读是否为空栈
bool StackEmpty(Stack *s){
    if(s->top==-1){
        printf("栈为空\n");
        return true;
    }else{
        printf("栈非空栈\n");
        return false;
    }
}

共享栈

共享栈是栈的另一种使用：两个栈指针，分别从栈顶和栈底计数，共享同一片物理内存空间，一定程度上提高的栈的利用率。

栈的链式存储实现

链式存储通用的可以有带头结点的和不带头结点的，如下代码示例为带头结点的。

其实在线性表的链式存储的头插法建立链表的时候，就是栈的一种类似情况。

栈的结构

#define ElemType int    //栈的元素数据类型

//栈的结构
typedef struct linkNode
{
    ElemType data;	//栈的数据
    struct linkNode *next;	//下一个位置
}LinkNode,*LinkStack;

初始化栈

//初始化栈
void InitStack(LinkStack *s){
    LinkNode *newNode = malloc(sizeof(LinkNode));   //申请头结点内存空间
    newNode->next = NULL;   //头结点下一结点为空
    newNode->data = -1; //数据域为-1
    (*s) = newNode; //指针指向头结点
    printf("栈初始化头结点成功\n");
}

进栈（压入栈）

//进栈（压入栈）
bool Push(LinkStack *s,ElemType data){
    LinkNode *newNode = malloc(sizeof(LinkNode));   //申请头结点内存空间
    newNode->data = data;
    newNode->next = (*s)->next; //新结点指向头结点指向的结点
    (*s)->next = newNode; //头结点指向新结点
    printf("元素: %d 入栈成功\n", data);
    return true;
}

出栈（弹出栈）

//出栈（弹出栈）
bool Pop(LinkStack *s){
    if((*s)->next ==NULL){
        printf("栈为空，弹出栈顶元素失败\n");
        return false;
    }else{
        LinkNode *newNode = malloc(sizeof(LinkNode));   //申请头结点内存空间
        newNode = (*s)->next;   //获取栈顶元素
        (*s)->next = newNode->next;     //头结点指向新栈顶元素
        printf("弹出元素:%d 成功\n", newNode->data);
        free(newNode);
        return true;
    }
}

读取栈顶元素

//读取栈顶元素
ElemType GetTop(LinkStack* s) {
    if ((*s)->next == NULL)
        return -1;  //判断是否为空栈
    LinkNode* newNode = (*s)->next;
    return newNode->data;
}

队列

队列的基本概念

队列的定义

队列(Queue)本质也是一种线性表，其特点是：只允许在一端进行插入，在另一端进行删除的线性表。

• 入队：队列的插入操作
• 出队：队列的删除操作
• 队尾：允许插入操作进行的一端
• 队头：允许删除操作进行的一端

队列的特点：先进先出(First in First Out，FIFO)

队列的基本操作

操作	说明
InitQueue()	初始化队列，构造空队列
Destory()	销毁队列，销毁并释放队列所占的内存空间。
EnQueue()	入队，若队列未满，则将其加入队尾
DeQueue()	出队，若队列非空，则删除并返回对头元素
GetHead()	读取队头元素
QueueEmpty()	判断队列是否为空

队列的实现

队列的顺序存储实现

队列的定义

队头指针始终指向第一个元素，队尾指针指向最后一个可用的位置（而不是队尾元素）。

#define MaxSize 10
#define ElemType int

//队列的结构
typedef struct queue{
    int front;  //队头指针
    int rear;   //队尾指针
    ElemType data[MaxSize]; //队列元素区域
}Queue;

队列的初始化

//初始化队列
void InitQueue(Queue *q){
    q->front = 0;   //队头指针初始化
    q->rear = 0;    //队尾指针初始化
    printf("队列初始化成功\n");
}

入队操作

//入队
void EnQueue(Queue *q,ElemType data){
    if ((q->rear+1)% MaxSize==q->front)
    {
        printf("队列已满，入队失败\n");
    }else{
        q->data[q->rear] = data;
        q->rear = ((q->rear+1) % MaxSize);  //取模运算获得让队列形成循环
    }
}

出队操作

//出队
ElemType DeQueue(Queue *q){
    if (q->front==q->rear)
        return -1;  //判断是否为空队列
    ElemType temp = q->data[q->front];
    q->front =  (q->front+1) % MaxSize;
    printf("出队元素：%d 成功\n", temp);
    return temp;
}

读取队头元素

//读取队头元素
ElemType GetHead(Queue *q){
    if (q->front==q->rear)
        return -1;  //判断是否为空队列
    printf("读取队头元素 %d 成功,位置:%d\n", q->data[q->front],q->front);
    return q->data[q->front];
}

判断队列是否为空

//判断队列是否为空
bool QueueEmpty(Queue *q){
    if (q->front==q->rear)
    {
        printf("队列为空队列\n");
        return true;
    }else{
        printf("队列非空队列\n");
        return false;
    }
}

队列的链式存储实现

队列的定义（不带头结点）

#define ElemType int

//队列元素结构
typedef struct node
{
    ElemType data;  //队列元素的数据域
    struct node* next; //下一个结点的指针
}QNode;

//队列结构
typedef struct head
{
    struct node *front; //队列队头指针
    struct node *rear;  //队列队尾指针
    int size;   //队列的大小
}QHead;

队列初始化

//初始化队列-不带头结点
void InitQueue(QHead * q){
    q->front = NULL;    //队头指针初始化
    q->rear = NULL; //队尾指针初始化
    q->size = 0;    //初始化队列大小
    printf("队列初始化成功\n");
}

入队操作

bool EnQueue(QHead *q,ElemType data){
    QNode *qn = (QNode*)malloc(sizeof(QNode));  //新元素结点申请内存空间
    qn->data = data;
    if (q->size<1)
    {
        qn->next = NULL;    //尾指针为空
        q->front = qn;  //头指针指向第一个元素
    }else{
    qn->next = q->rear->next;   //新元素的下一个元素指针指向队尾指针的下一个
    q->rear->next = qn; //原来的队尾元素指向新队尾元素
    }
    q->rear = qn;   //尾指针指向第一个元素
    q->size++;  //队列的长度+1
    printf("元素 %d 入队成功,当前队列长度为:%d\n",data,q->size);
    return true;
}

出队操作

//出队操作
ElemType DeQueue(QHead *q){
    if(q->front==NULL)  //判断队列是否为空
        return -1;
    QNode *tempNode = q->front;
    ElemType tempdata = tempNode->data; //获取队头元素
    q->front = tempNode->next;  //队头指向新的队头元素
    if (q->rear==tempNode)
    {
        q->rear = NULL; //如果出队最后一个，则将尾指针设置为NULL
    }
    
    free(tempNode); //释放出队元素的内存空间
    q->size--;  //队列元素-1
    printf("队友元素 %d 已释放\n", tempdata);
    return tempdata;    //返回出队元素数据
}

读取队头元素

//读取队头元素
ElemType GetHead(QHead *q){
    if(q->front==NULL){
        printf("队列为空队列\n");
        return -1;
    }  //判断队列是否为空
    printf("队头元素为:%d\n", q->front->data);
    return q->front->data;
}

双端队列

队列是允许数据从一端插入，从另一端删除，而双端队列允许两端插入，两端删除的线性表。

本质上来说，不论是栈，还是队列，都是一种特殊规则的线性表。

当限制双端队列的一端删除和插入操作后，双端队列就变成了只有一端删除和插入的栈了，由此可以将双端队列演变成不同的类型，例如：

栈和队列的应用

栈在括号匹配中的应用

括号匹配机制

在我们常规的表达式中，例如 $2 \times [3 \times (3+2)+1]$ ，或者代码中的每个()[]{}的校验中，如何来校验我们在写代码的时候是否会多了个括号或者少了个括号。

经过观察你会发现，正确的匹配规则是：每一个右括号都有与之对应的唯一的左括号，现在我们就可以将一堆括号从左往右或者从右往左扫描，每次扫描到一个左括号，将其压入栈中，每扫描到一个右括号就将栈顶元素弹出，表示与之匹配。其扫描匹配过程会遇到如下情况：

图片来源：王道数据结构

算法实例

#include <stdio.h>
#include <stdbool.h>
#include <malloc.h>
#define MaxSize 10
#define ElemType char

//栈的结构
typedef struct stack
{
    int top;    //栈顶指针
    ElemType brackets[MaxSize]; //栈内存空间
}Stack;

//初始化栈
void InitStack(Stack *s){
    s->top = -1;    //栈顶指针设置为-1
}

//入栈
void Push(Stack *s,ElemType data){
    if (s->top==MaxSize-1)
    {
        printf("栈已满，入栈失败\n");
    }else{
        s->top++;   //栈顶指针+1
        s->brackets[s->top] = data; //新数据填入栈顶
        printf("元素 %c 入栈成功\n", data);
        printf("当前栈顶指针为：%d\n", s->top);
    }
}

//出栈
ElemType Pop(Stack *s){
    if (s->top==-1)
    {
        return 'n';
        printf("栈为空栈，弹出失败\n");
    }else{
        s->top--;
        printf("元素 %c 弹出成功\n", s->brackets[s->top + 1]);
        if (s->top == -1)
        {
            printf("当前栈为空栈\n");
        }else
        {
            printf("当前栈顶指针为：%d,栈顶元素为 %c\n", s->top,s->brackets[s->top]);
        }
        return s->brackets[s->top + 1];
    }
}

//判断是否为空栈
bool StackEmpty(Stack *s){
    if(s->top==-1)
        return true;
    else
        return false;
}

//判断括号是否合法
bool BracketCheck(char str[],int length){
    Stack 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)){
                printf("扫描到右括号，但是栈为空\n");
                return false;
            }
            char temp = Pop(&s);
            if (temp+1==str[i] || temp+2==str[i])	//()[]{}的ASCII码差1或者2
            {
                printf("括号匹配成功，位置 %d\n", i+1);
            }else{
                printf("括号为：%c不匹配数组 %c位置 %d\n",temp,str[i],i+1);
                return false;
            }
        }
        if (i==length-1 && !StackEmpty(&s))
        {
            printf("还有未匹配的左括号在栈中\n");
            return false;
        }
    }
    printf("括号匹配合法\n");
    return true;
}

//运行测试
int main(){
    char str[10] = {'{', '(', '[', ']', ')', '}', '}'};
    BracketCheck(str, 7);
}

运行结果：

栈在表达式求值中的应用

表达式基础

现在看一个我们小学熟悉的式子：$(5 \times (3+2)) \div 3-2$ ，这个式子，它由于有运算符和括号优先级，而导致其计算需要一定的顺序。这种我们常见的式子被称为：中缀表达式。它由三个部分组成：操作数，运算符，界限符（即括号）。

不难发现，这三者不可缺一，否则会导致结果出错，和常规的线性代数一样，数学家发现方程式的未知数指代可以用矩阵的位置来表示。同样的，波兰的一个数学家发明了：前缀表达式（波兰表达式）和后缀表达式（逆波兰表达式）来去除了界限符的使用，同样可以正确的得到计算结果。

综上所述，表达式可以分为如下三种：

• 中缀表达式：也就是我们所熟悉的表达式，例如 $a \times b$ ，它将运算符放在两个操作数的中间。
• 前缀表达式：波兰表达式，例如 $\times a b$ ，它将运算符放在两个操作数的前面。
• 后缀表达式：逆波兰表达式，例如 $a b \times$ ，它将运算符放在两个操作数的后面 。

算法思路

中缀表达式转后缀表达式

初始化一个栈，用于保存暂时还不能确定运算顺序的运算符。

从左到右处理各个元素，直到末尾。可能遇到三种情况：

• 遇到操作数：直接加入后缀表达式

• 遇到界限符：遇到(直接入栈；遇到)则依次弹出栈内运算符并加入后缀表达式，直到弹出(为止

  (不加入后缀表达式

• 遇到运算符：依次弹出栈中优先级高于或者等于当前运算符的所有运算符，并加入后缀表达式，若碰到(或者栈空则停止。之后再把当前运算符入栈。

后缀/前缀表达式计算

后缀表达式计算：从左往右扫描，遇到操作数则压入栈中，遇到操作符，就将栈中最近的两个操作数弹出进行计算，其结果再压入栈中，直到最后，栈中只有一个元素，其就是运算结果。

前缀表达式计算：从右往左扫描，遇到操作数则压入栈中，遇到操作符，则将栈中最近的两个操作数弹出进行计算并将结果压入栈中，直到最后，栈中只有一个元素，其为运算结果。

需要注意的是，后缀表达式中先弹出的操作数是被操作数（即后弹出来的操作数 操作符 先弹出来的操作数），而前缀表达式中先弹出的操作数是操作数（**即先弹出的操作数 操作符 后弹出来的操作数**）。

中缀表达式的计算

中缀表达式的计算就是上述两个算法的结合，先将中缀表达式转换为后缀表达式，再利用后缀表达式计算结果。

如下算法是两个算法的结合版，即一边转后缀表达式一边计算，而不是先后顺序，用栈实现：

• 初始化两个栈，操作数栈和运算符栈
• 若扫描到操作数，压入操作数栈
• 若扫描到运算符或者界限符，则按照“中缀转后缀”相同的逻辑压入运算符栈（期间也会弹出运算符，每当弹出一个运算符时，就需要再弹出两个操作数栈的栈顶元素并执行相应的运算，运算结果再压回栈内）

算法实例

说明：我使用了两种方法分别实现了中缀表达式的计算

• 第一种是常规的先将中缀表达式转换为后缀表达式，然后再通过后缀表达式来计算获得结果。
• 第二种是将两者结合起来，一边转换为中缀表达式一边来计算结果，即上述的中缀表达式的计算的算法说明

第一种

#include <stdio.h>
#include <stdbool.h>
#include <malloc.h>
#include <string.h>
#define MaxSize 18
#define ElemType int

//栈的结构
typedef struct stack
{
    int top;    //栈顶指针
    ElemType brackets[MaxSize]; //栈内存空间
}Stack;

//初始化栈
void InitStack(Stack* s) {
    s->top = -1;    //栈顶指针设置为-1
}

//入栈
void Push(Stack* s, ElemType data) {
    if (s->top == MaxSize - 1)
    {
        printf("栈已满，入栈失败\n");
    }
    else {
        s->top++;   //栈顶指针+1
        s->brackets[s->top] = data; //新数据填入栈顶
        printf("元素 %d 入栈成功\n", data);
        //printf("当前栈顶指针为：%d\n", s->top);
    }
}

//出栈
ElemType Pop(Stack* s) {
    if (s->top == -1)
    {
        return 'n';
        printf("栈为空栈，弹出失败\n");
    }
    else {
        s->top--;
        printf("元素 %d 弹出成功\n", s->brackets[s->top + 1]);
        if (s->top == -1)
        {
            printf("当前栈为空栈\n");
        }
        else
        {
            printf("当前栈顶指针为：%d,栈顶元素为 %d\n", s->top, s->brackets[s->top]);
        }
        return s->brackets[s->top + 1];
    }
}

//判断是否为空栈
bool StackEmpty(Stack* s) {
    if (s->top == -1)
        return true;
    else
        return false;
}

//读取栈顶元素
ElemType ReadStackHead(Stack* s) {
    if (StackEmpty(&s))
    {
        return -99;
    }
    else {
        return s->brackets[s->top];
    }
}

//运算符优先级判断
int Priority(char x) {
    if (x=='*' || x=='/')
    {
        return 2;
    }
    else if(x=='(' || x==')')
    {
        return 3;
    }
    else
    {
        return 1;
    }
}

//判断后缀或者前缀表达式是否正确
bool CheckExpression(char str[], int length) {
    int operand = 0;    //操作数的个数
    int operator= 0;    //操作符的个数
    int bracketsNum = 0;    //括号计数器
    bool lastIsNum =false;  //记录扫描到的是不是数值
    for (int i = 0; i < length; i++)
    {
        if (str[i] == '+' || str[i] == '-' || str[i] == '*' || str[i] == '/')
        {
            //如果连续是运算符则返回表达式错误
            if (!lastIsNum)
            {
                printf("输入的表达式错误\n");
                return false;
            }
            operator++;
            lastIsNum = false;
        }
        else if(str[i]=='(')
        {
            bracketsNum++;
        }
        else if(str[i] == ')')
        {
            bracketsNum--;
        }
        else {
            //如果连续两个都是数值就直接返回表达式错误
            if (lastIsNum)
            {
                printf("输入的表达式错误\n");
                return false;
            }
            operand++;
            lastIsNum = true;
        }
    }
    //只有操作数的数量-运算符的数量=1以及括号都配对了
    if (operand == operator+1 && bracketsNum ==0)
    {
        printf("表达式正确\n");
        return true;
    }
    else {
        printf("输入的表达式错误\n");
        return false;
    }
}

//计算后缀表达式
int Rpn(char str[], int length) {
    Stack s;    //声明栈
    InitStack(&s);  //初始化栈
    int ltemp = 0;  //声明左临时操作数
    int rtemp = 0;  //声明右临时操作数
    int res = 0;    //临时计算结果
    for (int i = 0; i < length; i++)
    {
        if (str[i] == '+' || str[i] == '-' || str[i] == '*' || str[i] == '/')
        {
            rtemp = Pop(&s);    //先弹出来的
            ltemp = Pop(&s);    //后弹出来
            switch (str[i])
            {
            case '+':
                res = ltemp + rtemp;
                break;
            case '-':
                res = ltemp - rtemp;
                break;
            case '*':
                res = ltemp * rtemp;
                break;
            case '/':
                res = ltemp / rtemp;
                break;
            }
            Push(&s, res);  //结果压入栈中
        }
        else {
            Push(&s, str[i]);   //遇到操作数压入栈中
            printf("扫描到数值:%d位置:%d 已成功入栈\n", str[i], i + 1);
        }
    }
    printf("计算完成，返回结果:%d", res);
    return res;
}

//中缀表达式转后缀表达式
bool ConvertRpn(char str[],int length) {
    if (!CheckExpression(str, length))   //检查表达式是否正确
    {
        return false;
    }
    Stack opStack;  //声明运算符栈
    InitStack(&opStack);    //初始化栈
    char rpn[MaxSize];  //后缀表达式数组
    int j = 0;  //后缀表达式数组临时指针
    char tempchar;  //创建一个临时变量承载栈弹出的数据
    for (int i = 0; i < length; i++)
    {
        if (str[i] == '+' || str[i] == '-' || str[i] == '*' || str[i] == '/')
        {
            //空栈的时候或者扫描到的运算符优先级大于栈中运算符的优先级直接将字符压入栈中
            if (StackEmpty(&opStack)||  Priority((char)str[i]) > Priority((char)ReadStackHead(&opStack)))
            {
                Push(&opStack, str[i]); //遇到不确定操作符压入栈
            }
            else
            {
                //当扫描到的运算符优先级小于等于栈顶元素的优先级，将栈顶运算符弹出加入后缀表达式数组
                if (Priority((char)str[i]) <= Priority((char)ReadStackHead(&opStack)))
                {
                    while ((char)ReadStackHead(&opStack)!='(')
                    {
                        tempchar = Pop(&opStack);   //弹出运算符
                        rpn[j] = tempchar;  //运算符加入后缀表达式
                        j++;
                        if (StackEmpty(&opStack))
                        {
                            break;
                        }
                    }
                    Push(&opStack, str[i]); //遇到不确定操作符压入栈
                }
            }
        }
        else if(str[i] == '('){
            Push(&opStack, str[i]); //遇到左括号压入栈中
        }
        else if (str[i] == ')') {
            tempchar = Pop(&opStack);   //弹出运算符
            while (tempchar!='(')
            {
                rpn[j] = tempchar;  //运算符加入后缀表达式
                tempchar = Pop(&opStack);   //弹出运算符
                j++;
            }
        }
        else {
            rpn[j] = str[i];    //扫描到操作数，直接加入后缀表达式中
            j++;
            printf("操作数 %d 放入后缀表达式数组\n", str[i]);
        }
    }
    //最后判断栈中有没有运算符 有就直接输出加入到后缀表达式数组
    if (!StackEmpty(&opStack))
    {
        while (opStack.top != -1) {
            tempchar = Pop(&opStack);   //弹出运算符
            rpn[j] = tempchar;  //运算符加入后缀表达式
            j++;
        }
    }

    //输出转换后的后缀表达式-因为字符问题，输出的+-*/为ASCII对应的十进制数值
    printf("转换后的后缀表达式为：");
    for (int k = 0; k < j; k++)
    {
        printf("%d", rpn[k]);
    }
    printf("\n");

    printf("新数组的数量为：%d\n", j);
    //转换完成的后缀表达式传递给后缀表达式计算函数
    Rpn(rpn,j);

    return true;
    
}

int main() {
    //这是个正确的后缀表达式，如果直接使用中缀转后缀会给表达式合法性检测返回错误，其表达式值我记得是5
    //char st[MaxSize] = { 15,7,1,1,'+','-','/',3,'*',2,1,1,'+','+','-'};
    //中缀表达式数组——该中缀表达式正确值为16
    char st[MaxSize] = { 2,'*','(',9,'+',6,'/',3,'-',5,')','+',4 };
    //计算结果-我将中缀转后缀和后缀表达式的计算写在一起了，详情可以查看中缀转后缀表达式导数第二行
    ConvertRpn(st, strlen(&st));
}

如上算法，说明以及注意事项：

1. 需要将表达式输入到main函数中的st数组中，如果你给定的数组字符大于MaxSize(18)的数量建议将MaxSize修改为大于你输入的表达式的字符数量，以防栈溢出而出现错误。

2. 对于你给定的式子，例如 $2 \times (2+3)$ ，除了字符需要加单引号，数值不需要加单引号('')，由于我利用了char类型的内存占用，所以你可以输入参与计算的单个数值范围为$-128 \sim 127$ 。

   具体原理查看关于C语言的一些零碎思考

3. 我加入了中缀表达式验证函数，原理是根据括号的匹配和操作符和运算符的关系，以及不可能出现的连续两个数值或者运算符来验证的，我不确定是否还有一些能够逃过该验证的表达式，除非你输入了非法数值。

4. 如上代码在Visual Studio的C++模块编译可以正确运行，但是会产生一个警告可能没有为“st”添加字符串零终止符，在Visual Studio Code链接的GCC编译器无报错可以正确运行。

第二种

//中缀表达式计算-结合版
bool InfixExpCalculate(char str[],int length) {
    //中缀表达式合法性检测
    if (!CheckExpression(str, length))   
    {
        return false;
    }
    Stack operandStack; //操作数栈
    Stack operatorStack;    //运算符栈
    InitStack(&operandStack);   //初始化栈
    InitStack(&operatorStack);  //初始化栈
    //遍历中缀表达式——即传入的数组
    for (int i = 0; i < length; i++)
    {
        //扫描到运算符或者左括号
        if (str[i] == '+' || str[i] == '-' || str[i] == '*' || str[i] == '/' || str[i] == '(' || str[i] == ')' || str[i]=='!')
        {
            printf("当前数值:%d,当前字符为:%c\n", str[i]);
            //如果运算符栈为空或者扫描到的运算符优先级大于栈顶运算符的优先级
            if (StackEmpty(&operatorStack) || ReadStackHead(&operatorStack) == '('|| str[i] == '(' || ((str[i]+3)%10 < (ReadStackHead(&operatorStack))%10 &&  str[i]!=')'))
            {
                Push(&operatorStack, str[i]);   //将未确定的运算符压入栈中
            }
            else
            {
                //弹出运算符到左括号前
                while (ReadStackHead(&operatorStack) != '(' && !StackEmpty(&operatorStack))
                {
                    //弹出运算符-紧接着计算值再压回操作数栈内
                    printf("当前操作符栈顶为   %c\n", ReadStackHead(&operatorStack));
                    switch ((char)Pop(&operatorStack))
                    {
                    case '+':
                        Push(&operandStack, (Pop(&operandStack) + Pop(&operandStack)));
                        break;
                    case '-':
                        Push(&operandStack, -(Pop(&operandStack) - Pop(&operandStack)));
                        break;
                    case '*':
                        Push(&operandStack, (Pop(&operandStack) * Pop(&operandStack)));
                        break;
                    case '/':
                        {
                            int temp1 = Pop(&operandStack);
                            int temp2 = Pop(&operandStack);
                            Push(&operandStack, temp2/temp1);
                            break;
                        }
                    }
                }
                //如果扫描到右括号
                if (ReadStackHead(&operatorStack) == '(' && str[i]==')') {
                    Pop(&operatorStack); //将左括号弹出
                }
                else
                {
                    if ((int)str[i] !=33)
                    {
                        Push(&operatorStack, str[i]);   //将未确定的运算符压入栈中
                    }
                }
            }
        }else {
           //扫描到数值
            Push(&operandStack, str[i]);    //将操作数压入操作数栈
        }
    }
    printf("计算结果为: %d", Pop(&operandStack));
    return true;
}

int main() {
    char st[MaxSize] = { '(','(',15,'/','(',7,'-','(',1,'+',1,')',')',')','*',3,')','-','(',2,'+','(',1,'+',1,')',')','!'};
    //中缀表达式数组
    //char st[MaxSize] = { 2,'*','(',9,'+',6,'/',3,'-',5,')','+',4,'!' };
    //计算结果
    InfixExpCalculate(st, strlen(st));
}

注意事项：

1. 该代码兼容上述的第一种方法，是在同一个文件内编写的，所以如果你要使用需要将代码复制在同一个文件夹内的代码最下面。

2. 除法部分请不要修改，我尝试使用Push(&operandStack, 1/(Pop(&operandStack)/Pop(&operandStack)));来提高代码复用，很不幸，此代码逻辑上没有问题，但是无法通过编译器，给我反馈的错误是整数除以零，我不得已借助变量来完成运算。

3. 使用第二章同步的中缀表达式计算需要注意，表达式仍然和第一种的规则一致，不过最后需要加上'!'来表示表达式结束，因为我尝试去少写代码，来完成更多的工作，所以请在最后加上'!'表示结束。

4. 同样的，为了防止因为表达式的问题而导致计算结果错误，我改进了表达式检测合法函数的部分代码，如果你需要使用第二种算法来计算，则需要使用这部分检测代码，当然你也可以继续使用第一种的检测代码，不过需要将for循环中的length进行-1即可。改进后的代码如下：

   //判断后缀或者前缀表达式是否正确
   bool CheckExpression(char str[], int length) {
       if (length>=MaxSize)
       {
           printf("表达式可能会溢出栈，请修改MaxSize大小");
           return false;
       }
       if (str[length-1] != '!')
       {
           printf("缺少表达式结束符 '!'");
           return false;
       }
       int operand = 0;    //操作数的个数
       int operator= 0;    //操作符的个数
       int bracketsNum = 0;    //括号计数器
       bool lastIsNum =false;  //记录扫描到的是不是数值
       for (int i = 0; i < length-1; i++)
       {
           printf("当前数值:%d,当前字符:%c\n", str[i], str[i]);
           if (str[i] == '+' || str[i] == '-' || str[i] == '*' || str[i] == '/')
           {
               //如果连续是运算符则返回表达式错误
               if (!lastIsNum)
               {
                   printf("输入的表达式错误,位置 %d,字符 %c\n",i+1,str[i]);
                   return false;
               }
               operator++;
               lastIsNum = false;
           }
           else if(str[i]=='(')
           {
               bracketsNum++;
           }
           else if(str[i] == ')')
           {
               bracketsNum--;
           }
           else {
               //如果连续两个都是数值就直接返回表达式错误
               if (lastIsNum)
               {
                   printf("输入的表达式错误,位置 %d,字符 %c\n", i + 1, str[i]);
                   return false;
               }
               operand++;
               lastIsNum = true;
           }
       }
       //只有操作数的数量-运算符的数量=1以及括号都配对了
       if (operand == operator+1 && bracketsNum ==0)
       {
           printf("表达式正确\n");
           return true;
       }
       else {
           printf("输入的表达式错误\n");
           return false;
       }
   }

   注意：改进后的函数和第一种算法的函数不兼容，也就是说你使用第一种算法只能用第一种该函数检测合法性，而第二种算法可以选择稍微修改第一种函数代码来兼容或者使用该改进后的代码

5. 如上代码在Visual Studio的C++模块编译可以正确运行无报错，很不幸第二种在Visual Studio Code链接的GCC编译器可以正确运行但是计算结果会出现偏差，具体原因我并未研究。

栈在递归中的应用

递归函数的特点是最后执行的，最先结束，这点和栈如出一辙。

对于C语言来说，函数的递归就是将每个函数压入栈的过程，当最后的递归函数被返回时，则依次将其弹出函数栈来表示函数的结束，进而完成整个递归函数。

更多详细内容查看【C语言】函数——栈帧的创建和销毁

递归适合解决的问题：可以把原始问题转换为属性相同，但是规模较小的问题。

队列应用

树的层次遍历

这是树，当然这些会在后面树的部分进行详细说明：

我们在遍历树的时候，就需要利用队列的队头出，队尾增。我们在遍历节点 1 的时候，需要将其子节点 2 ，3 加入到队列后紧跟节点 1 ，处理完节点 1 后将节点 1 弹出，处理节点 2 ，3 。同理处理节点 2，3 的时候将其子节点加入队列，依次反复，直到完成树的遍历。

图的广度优先遍历

这是一个图，同样的会在后面图的部分进行详细说明：

我们在对图的广度优先遍历的时候也需要用到队列的思想，和树的层次遍历类似，从节点1 开始，处理节点 1 的时候将其子节点加入到队列中，然后再处理子节点的时候再将其子节点的节点加入队列，如此反复。

队列在操作系统中的应用

多个进程争抢使用有限的系统资源时，FCFS（First Come First Service，先来先服务）。

多个进程进行队列，先进入队列的程序（进程）会先在 CPU 执行一个时间片，然后弹出队列，执行下一个队头进程，如此反复。

End

不想写啊啊啊啊啊。