顺序栈

先是对栈的基础操作

#include "stdio.h"
#include "stdlib.h"

#define ElemType int
#define MaxSize 10

typedef struct {
    ElemType data[MaxSize];
    int top;
}SqStack;

void InitStack(SqStack &S)
{
    S.top=0;
}

bool Empty(SqStack &S)
{
    if(S.top==0)
        return true;
    else
        return false;
}

void Push(SqStack &S,ElemType e)
{
    if(S.top>MaxSize-1)
    {
        printf("Stack is full");
        printf("\n");
    }
    else
    {
        S.data[S.top]=e;
        S.top++;
    }
}

void Pop(SqStack &S,ElemType &e)
{
    if(S.top==0){
        printf("Stack is Empty");
        printf("\n");
    }
    else{
        S.top--;
        e=S.data[S.top];
    }
}

ElemType GetTop(SqStack &S)
{
    ElemType e;
    if(S.top==0){
        printf("Stack is Empty");
        printf("\n");
    }
    else{
        e=S.data[S.top-1];
        return e;
    }
}

以下是参考《2022年数据结构考研复习指导》

//习题3.1---检测括号匹配
bool bracketCheck(char *str)
{
    SqStack S;
    InitStack(S);
    int i;
    ElemType e;
    while(str[i]!='\0'){
        if(str[i] =='(' || str[i] =='[' || str[i] =='{')
        {
            Push(S,str[i]);
        }else{
            if(Empty(S))
                return false;
            else{
                e=GetTop(S);
                if(e=='(' && str[i]==')')
                    Pop(S,e);
                if(e=='{' && str[i]=='}')
                    Pop(S,e);
                if(e=='[' && str[i]==']')
                    Pop(S,e);
                else
                    return false;
            }
        }
        i++;
    }
    if(Empty(S))
        return true;
    else
        return false;
}

//习题3.2---火车调度
void Train(char *train)
{
    char *p=train,*q=train,c;
    ElemType e;
    SqStack S;
    InitStack(S);
    while(*p){
        if(*p=='H')
            Push(S,*p);
        else
            *(q++)=*p;
        p++;
    }
    while(!Empty(S))
    {
        Pop(S,e);
        *(q++)=c;
    }
}

//习题3.3---用栈实现非递归
double f(int n,double x)
{
    struct stack{
        int no;
        double pn;
    }st[MaxSize];
    int top=-1,i;
    double pn0,pn1=2*x;
    for(i=n;i>=2;i--)
    {
        top++;
        st[top].no=i;
    }
    while(top>=0)
    {
        st[top].pn=2*x*pn1-2*(st[top].no-1)*pn0;
        pn0=pn1;
        pn1=st[top].pn;
        top--;
    }
    if(n==0)
        return pn0;
    return  pn1;
}