【精品数据结构】栈和队列4.pptVIP

(3)判断队列是否为空QueueEmpty(q) 若队列q满足q-front==q-rear条件,则返回1；否则返回0。对应算法如下: int QueueEmpty(SqQueue *q) { return(q-front==q-rear); } (4)入队列enQueue(q,e) 在队列不满的条件下,先将队尾指针rear循环增1,然后将元素添加到该位置。对应算法如下: int enQueue(SqQueue *q,ElemType e) { if ((q-rear+1)%MaxSize==q-front) /*队满*/ return 0; q-rear=(q-rear+1)%MaxSize; q-elem[q-rear]=e; return 1; } (5)出队列deQueue(q,e) 在队列q不为空的条件下,将队首指针front循环增1,并将该位置的元素值赋给e。对应算法如下: int deQueue(SqQueue *q,ElemType e) { if (q-front==q-rear) /*队空*/ return 0; q-front=(q-front+1)%MaxSize; e=q-elem[q-front]; return 1; } 例3.5 假设表达式中允许包含三种括号:圆括号、方括号和大括号。编写一个算法判断表达式中的括号是否正确配对。 3.1.4 栈的应用例子 解:对应的算法如下: int correct(char exp[],int n) { char st[MaxSize]; int top=-1,i=0,tag=1; while (in tag) { if (exp[i]==( || exp[i]==[ || exp[i]=={) /*遇到(、[或{,则将其入栈*/ { top++; st[top]=exp[i]; } if (exp[i]==‘)’) /*遇到‘)’,若栈顶是‘(’,则继续处 理,否则以不配对返回*/ if (st[top]==() top--; else tag=0; if (exp[i]==‘]’) /*遇到‘]’,若栈顶是‘[’, 则继续处 理,否则以不配对返回*/ if (st[top]==[) top--; else tag=0; if (exp[i]==‘}’) /*遇到‘}’,若栈顶是 ‘{’,则继续处 理,否则以不配对返回*/ if (st[top]=={) top--; else tag=0; i++; } if (top-1) tag=0; /*若栈不空,则不配对*/ return(tag); } 1. 表达式求值 这里限定的表达式求值问题是:用户输入一个包含“+”、“-”、“*”、“/”、正整数和圆括号的合法数学表达式,计算该表达式的运算结果。 在程序语言中,运算符位于两个操作数中间的表达式称为中缀表达式,例如,1+2*3就是一个中缀表达式,中缀表达式是最常用的一种表达式方式。对中缀表达式的运算一般遵循“先乘除,后加减,从左到右计算,先括号内,后括号外”的规则。因此,中缀表达式不仅要依赖运算符优先级,而且还要处理括号。 所谓后缀表达式,就是运算符在操作数的后面,如1+2*3的后缀表达式为123*+。在后缀表达式中已考虑了运算符的优先级,没有括号,只有操作数和运算符。 对后缀表达式求值过程是:从左到右读入后缀表达式,若读入的是一个操作数,就将它入数值栈,若读入的是一个运算符op,就从数值栈中连续出栈两个元素(两个操作数),假设为x和y,计算x op y之值,并将计