8.栈和队列的应用

一、栈的应用

1.1 括号匹配问题

怎样判断是不是匹配序列呢？

算法思想：
1)初始一个空栈，顺序读入括号。
2)若是右括号，则与栈顶元素进行匹配
●若匹配，则弹出栈顶元素并进行下一个元素
●若不匹配，则该序列不合法
3)若是左括号，则压入栈中
4)若全部元素遍历完毕，栈中非空则序列不合法

代码如下：

#include <malloc.h>
#include <stdio.h>
#include <stdlib.h>
#define MaxSize 50
#define ElemType char
typedef struct
{
    ElemType data[MaxSize];
    int top;
}SqStack;
void InitStack(SqStack *&s){
    s = (SqStack*)malloc(sizeof(SqStack));
    s->top=-1;
}
bool IsEmpty(SqStack *&s){
    return s->top == -1;
}
bool Push(SqStack *&s, ElemType e){
    //判断栈有没有满
    if(s->top == MaxSize)
        return false;
    s->data[++s->top] = e;
    return true;
}
bool Pop(SqStack *&s, ElemType &e){
    //如果栈为空，则返回false
    if(s->top == -1)
        return false;
    e = s->data[s->top--];
    return true;
}
bool GetTop(SqStack *&s, ElemType &e){
    if(s->top==-1)
        return false;
    e = s->data[s->top];
    return true;
}
void DestroyStack(SqStack *&s){
    free(s);
}

//括号匹配问题
bool Match(char exp[],int n)
{
    int i=0; char e;
    bool match=true;
    SqStack *st;
    InitStack(st);                      //初始化栈
    while (i<n && match)                //扫描exp中所有字符
    {
        if (exp[i]=='(')                //当前字符为左括号,将其进栈
            Push(st,exp[i]);
        else if (exp[i]==')')           //当前字符为右括号
        {
            if (GetTop(st,e)==true)
            {   
                if (e!='(')             //栈顶元素不为'('时表示不匹配
                    match=false;
                else
                    Pop(st,e);          //将栈顶元素出栈
            }
            else  match=false;          //无法取栈顶元素时表示不匹配
        }
        i++;                            //继续处理其他字符
    }
    if (!IsEmpty(st))               //栈不空时表示不匹配
        match=false;
    DestroyStack(st);                   //销毁栈
    return match;
}

2.2 表达式求值问题

((2+3)*4)-(5-3)

1. 先要中缀转后缀：
2. 计算后缀

中缀转后缀算法思想:
数字直接加入后缀表达式运算符时:
a.若为’(’，入栈;
b.若为")"，则依次把栈中的运算符加入后缀表达式，直到出现’(’, 并从栈中删除’(’;
C.若为’+’, ‘’, ‘*’, ‘/’,
  ●栈空，入栈;
  ●栈顶元素为’(’,入栈;
  ●高于栈顶元素优先级，入栈;
  ●否则，依次弹出栈顶运算符，直到-一个优先级比它低的运算符或(为止; 
d.遍历完成，若栈非空依次弹出所有元素。

void trans(char *exp,char postexp[])    //将算术表达式exp转换成后缀表达式postexp
{
    char e;
    SqStack *Optr;                      //定义运算符栈
    InitStack(Optr);                    //初始化运算符栈
    int i=0;                            //i作为postexp的下标
    while (*exp!='\0')                  //exp表达式未扫描完时循环
    {   switch(*exp)
        {
        case '(':                       //判定为左括号
            Push(Optr,'(');             //左括号进栈
            exp++;                      //继续扫描其他字符
            break;
        case ')':                       //判定为右括号
            Pop(Optr,e);                //出栈元素e
            while (e!='(')              //不为'('时循环
            {
                postexp[i++]=e;         //将e存放到postexp中
                Pop(Optr,e);            //继续出栈元素e
            }
            exp++;                      //继续扫描其他字符
            break;
        case '+':                       //判定为加或减号
        case '-':
            while (!IsEmpty(Optr))   //栈不空循环
            {
                GetTop(Optr,e);         //取栈顶元素e
                if (e!='(')             //e不是'('
                {
                    postexp[i++]=e;     //将e存放到postexp中
                    Pop(Optr,e);        //出栈元素e
                }
                else                    //e是'(时退出循环
                    break;
            }
            Push(Optr,*exp);            //将'+'或'-'进栈
            exp++;                      //继续扫描其他字符
            break;
        case '*':                       //判定为'*'或'/'号
        case '/':
            while (!IsEmpty(Optr))   //栈不空循环
            {
                GetTop(Optr,e);         //取栈顶元素e
                if (e=='*' || e=='/')   //将栈顶'*'或'/'运算符出栈并存放到postexp中
                {
                    postexp[i++]=e;     //将e存放到postexp中
                    Pop(Optr,e);        //出栈元素e
                }
                else                    //e为非'*'或'/'运算符时退出循环
                    break;
            }
            Push(Optr,*exp);            //将'*'或'/'进栈
            exp++;                      //继续扫描其他字符
            break;
        default:                //处理数字字符
            while (*exp>='0' && *exp<='9') //判定为数字
            {   postexp[i++]=*exp;
                exp++;
            }
            postexp[i++]='#';   //用#标识一个数值串结束
        }
    }
    while (!IsEmpty(Optr))   //此时exp扫描完毕,栈不空时循环
    {
        Pop(Optr,e);            //出栈元素e
        postexp[i++]=e;         //将e存放到postexp中
    }
    postexp[i]='\0';            //给postexp表达式添加结束标识
    DestroyStack(Optr);         //销毁栈       
}

计算后缀算法思想

double compvalue(char *postexp) //计算后缀表达式的值
{
    double d,a,b,c,e;
    SqStack *Opnd;             //定义操作数栈
    InitStack(Opnd);           //初始化操作数栈
    while (*postexp!='\0')      //postexp字符串未扫描完时循环
    {   
        switch (*postexp)
        {
        case '+':               //判定为'+'号
            Pop(Opnd,a);       //出栈元素a
            Pop(Opnd,b);       //出栈元素b
            c=b+a;              //计算c
            Push(Opnd,c);      //将计算结果c进栈
            break;
        case '-':               //判定为'-'号
            Pop(Opnd,a);       //出栈元素a
            Pop(Opnd,b);       //出栈元素b
            c=b-a;              //计算c
            Push(Opnd,c);      //将计算结果c进栈
            break;
        case '*':               //判定为'*'号
            Pop1(Opnd,a);       //出栈元素a
            Pop(Opnd,b);       //出栈元素b
            c=b*a;              //计算c
            Push(Opnd,c);      //将计算结果c进栈
            break;
        case '/':               //判定为'/'号
            Pop(Opnd,a);       //出栈元素a
            Pop(Opnd,b);       //出栈元素b
            if (a!=0)
            {
                c=b/a;          //计算c
                Push(Opnd,c);  //将计算结果c进栈
                break;
            }
            else
            {   
                printf("\n\t除零错误!\n");
                exit(0);        //异常退出
            }
            break;
        default:                //处理数字字符
            d=0;                //将连续的数字字符转换成对应的数值存放到d中
            while (*postexp>='0' && *postexp<='9')   //判定为数字字符
            {   
                d=10*d+*postexp-'0';  
                postexp++;
            }
            Push(Opnd,d);      //将数值d进栈
            break;
        }
        postexp++;              //继续处理其他字符
    }
    GetTop(Opnd,e);            //取栈顶元素e
    DestroyStack(Opnd);        //销毁栈       
    return e;                   //返回e
}

2.3 递归

我们可以用栈来实现递归过程

斐波拉契数列：0,1,1,2,3,5,…

//递归做法
int Fib(int n) {
  if(n == 0)
    return 0;
  else if(n == 1)
    return 1 ;
  else
    return Fib(n-1) + Fib(n-2) ;
}

使用栈：

int Fib(int n){
    int ans;
  if(n == 0)
    return 0;
  else if(n == 1)
    return 1;
  else{
   SqStack *s;
   InitStack(s);
   Push(s,0);
   Push(s,1);
     while(n-- > 1){
       int a,b;
       Pop(s,a);
       Pop(s,b);
       Push(s,a);
       Push(s,a+b);
     }
     GetTop(s,ans);
   }
   return ans;
}