2024/11/1 数据结构大题打卡

#difine maxsize 50
typedef struct Linknode{ElemType data[maxsize];    //数据域int top;
}SqStack;
void InitStack(sqstack &s)
{s.top=-1;
}
bool stackempty(sqstack &s)
{if(s.top==-1)return true;elsereturn false;
}
bool push(sqstack &s,elemtype x)
{if(s.top==maxsize-1){return false;}s.data[++s.top]=x;return true;}
bool pop(sqstack &s,elemtype &x)
{if(s.top==-1)return false;x=s.data(s.top--);return true;
}

typedef struct SNode{int data;struct SNode *next;
}Snode,*LiStack;
bool InitStack(LiStack &S)
{S=(Snode *)malloc(sizeof(Snode));S->next=NULL;return true;
}
bool StackEmpty(LiStack S)
{if(S->next=NULL)return true;elsereturn false; 
}
bool Pop(LiStack &S,int &x)
{if (StackEmpty(s))return false;SNode *p=S->next;x=p->data;S->next=p->next;free(p);return true;
}

后缀表达式机算

运算数依次入栈，遇到运算符就出栈，先出栈的是右操作数。

中缀转后缀：
遇到运算数，直接写

遇到操作符，入栈，如果栈里有一个比他高或者等级一样的，把那个弹出去。

遇到左括号直接入栈，直到遇到右括号，把里面的都弹出。

最后结束，把栈里剩余符号弹出。

栈的括号匹配：

从左向右一次扫描，当遇到左括号入栈，遇到右括号，出栈，若匹配，继续。若不匹配，失败。

最后若栈是空的则匹配成功，失败则匹配失败。