（41）5.6-5.7数据结构（栈和队列的应用）

1.栈在括号匹配中的应用

#define _CRT_SECURE_NO_WARNINGS
#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);
//栈顶元素出栈，用x返回
bool Pop(SqStack& S, char& x);

bool brackCheck(char str[], int length)
{
    SqStack S;
    InitStack(S);//初始化一个栈
}
bool brackCheck(char str[], int lenght)
{
    SqStack S;
    InitStack(S);//初始化一个栈
    for (int i = 0; i < lenght; 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);//检查全部括号后，栈空说明匹配成功
}

2.栈在表达式求值的应用

//表达式的组成：操作数，运算符，界限符
//中转前(右优先)
//中转后(左优先)  //可保证运算顺序唯一

2.1中级转后缀表达式

小结总结

3.栈在递归中的应用

//计算整数n！

#include<stdio.h>
int factorial(int n)
{
    if (n == 0 || n == 1)
        return 1;
    else
        return n * factorial(n - 1);
}
int main()
{
    int x = factorial(10);
    printf("奥里给");

}
//递归调用时;函数调用时函数栈可称为“递归工作栈”
//每进入一层递归，就将递归调用所需的信息压入栈中;
//每退出一层递归，就从栈顶弹出相应信息;
//缺点：太多层递归可能会导致溢出

//2.斐波那契数

int F(int n)
{
    if (n == 0)               
        return 0;          //边界条件
    else if (n == 1)
        return 1;          //边界条件
    else
        return F(n - 1) + F(n - 2);//递归表达式
}
//优点：代码简单容易理解
//缺点：效率低下

3.函数调用背后过程

 小结

4.队列在操作系统中的应用