栈和队列
例1-1
设计一个算法利用顺序栈判断一个字符串是否是对乘串。所谓对称串是指从左向右读和从右向左读的序列相同。
解：字符串str的所有元素依次进栈,产生的出栈序列正好与str的顺序相同，则str是对称串。
bool symmetry(ElemType str[]){
int i;
ElementType e;
SqStack *st;
InitStack(st); //初始化栈
for(i=0;str[i]!+'\0';i++) //将串所有元素入栈
push(st,str[i]); //元素进栈
for(i=0;str[i]!+'\0';i++){
pop(st,e); //退栈元素e
if(str[i]!=e){ //若e与当前串元素不同时则不是对称串
destroyStack(st); //销毁栈
return false;
}
}
destroyStack(st); //销毁栈
return true;
}
例1-2
编写一个算法判断输入的表达式中括号是否配对。
解：一个表达式中的左右括号是按最近位置配对的。所以利用一个栈来进行求解。这里采用链栈。
遇到”(“入栈，遇到”)”出栈，匹配条件：栈为空且指针指向字符串末
bool Match(char exp[],int n){
int i=0;char e;
bool match=true;
LiStack *st;
InitStack(st); //初始化栈
whle(i<n && match){ //扫描exp中的所有字符
if(exp[i]=='(')
Push（st,exp[i]);
else if(exp[i]==')'){ //当前字符为右括号
if(e!='(') //栈顶元素不为(时表示不匹配
match=false;
else
Pop(st,e); //将栈顶元素出栈
}else match=false; //无法取栈顶元素时表示不匹配
}
if(!StackEmpty(st)) match=false; //栈不空时，表示不匹配
DestroyStack(st); //销毁栈
return match;
}
例1-3
给定一个M * N的迷宫图、入口与出口、行走规则。求一条从指定入口到出口的路径。所求路径必须是简单路径，不能重复。
设置一个迷宫数组mg，其中每个元素表示一个方块的状态，为0时表示对应方块是通道，为1时表示对应方块不可走
bool mgpath(int xi,int yi, int xe,int ye){
int i,j,k,di,find;
StType st;
st.top=-1; //定义栈st并初始化
st.top++; //初始方块进栈
st.data[st.top].i=xi; st.data[st.top].j=yi;
st.data[st.top].di=-1; mg[xi][yi]=-1;
while(st.top>-1){ //栈不空时循环
i=st.data[st.top].i;
j=st.data[st.top].j;
di=st.data[st.top].di; //取栈顶方块
if(i==xe && j=ye){
for(k=0;k<=st.top;k++)
}
}
}
中缀表达式转后缀表达式
while(从exp读取字符ch，ch!='0'){
ch为数字：将后续的所有数字均依次存放到postexp中，并以字符"#"标志数值串结束；
ch为左括号"("：将此括号进栈到Optr中；
ch为右括号")"：将Optr中出栈时遇到的第一个左括号"("以前的运算符依次出栈并存放到postexp中，然后将左括号"("出栈;
ch为其他运算符：if(栈空或者栈顶运算符为'(') 直接将ch进栈；
else if(ch的优先级高于栈顶运算符的优先级)
直接将ch进栈
else
依次出栈并存入到postexp中，直到栈顶运算符优先级小于ch的优先级，然后将ch出栈；
}
若exp扫描完毕，则将Optr中所有运算符依次出栈并存放到postexp中。
//对postexp进行求值
while(从postexp读取字符ch，ch!='\0'){
ch为'+':从Opnd栈中出栈两个数值a和b，计算c=b+a;将c入栈;
ch为'-':从Opnd栈中出栈两个数值a和b，计算c=b-a;将c入栈;
ch为'*':从Opnd栈中出栈两个数值a和b，计算c=b*a;将c入栈;
ch为'/':从Opnd栈中出栈两个数值a和b，若a不为零;计算c=b/a;将c进栈;
ch为数字字符:将连续的数字串转换成数值d，将d进栈;
}
返回Opnd栈的栈顶操作数即后缀表达式的值；