第三节 - 队列(二)
发布时间：2020-09-20 10:42来源：未知
第三节 队列（二）
四、栈和队列的应用实例
1、中缀表达式和后缀表达式
中缀表达式：9-(2+4*7)/5+3 -----------适合人的习惯
后缀表达式：9247*+5/-3+ -----------适合计算机操作的特点
后缀表达式特点：
（1）从左向右数字的顺序与中缀表达式完全相同；
（2）从左向右运算符的顺序与中缀表达式的计算顺序完全相同；
（3）后缀表达式没有括号，运算规则简单，方法见后面讲解。
2、中缀表达式到后缀表达式的转换
中缀表达式转换为后缀表达式的算法思想：
顺序扫描中缀算术表达式
（1）当读到数字时，直接将其送至输出队列中；
（2）当读到运算符时，将栈中所有优先级高于或等于该运算符的运算符弹出，送至输出队列中，再将当前运算符入栈；
（3）当读入左括号时，即入栈；
（4）当读到右括号时，将靠近栈顶的第一个左括号上面的运算符全部依次弹出，送至输出队列中，再删除栈中的左括号。
中缀表达式：9-(2+4*7)/5+3转换为后缀表达式的过程：
| 转换步骤 | 中缀表达式读入 | 运算符栈OS | 后缀表达式PostQ |
| 初始 |
9-(2+4*7)/5+3# （#作为结束标志） |
# （预先压入栈方便算法） | 空 |
| 1 | -(2+4*7)/5+3# | # - | 9 |
| 2 | (2+4*7)/5+3# | # - | 9 |
| 3 | 2+4*7)/5+3# | # -( | 9 |
| 4 | +4*7)/5+3# | # -( | 92 |
| 5 | 4*7)/5+3# | # -(+ | 92 |
| 6 | *7)/5+3# | # -(+ | 924 |
| 7 | 7)/5+3# | # -(+* | 924 |
| 8 | )/5+3# | # -(+* | 9247 |
| 9 | /5+3# | # - | 9247*+ |
| 10 | 5+3# | # -/ | 9247*+ |
| 11 | +3# | # -/ | 9247*+5 |
| 12 | 3# | # + | 9247*+5/- |
| 13 | # | # + | 9247*+5/-3 |
| 14 | # | 9247*+5/-3+ |
【算法描述】
int Priority(DataType op)
{ //运算符优先级别判断函数
switch(op)
{ case '(':
case '#': return 0;
case '-':
case '+': return 1;
case '*':
case '/': return 2;
}
return -1;
}
void CTPostExp(CirQueue *Q)
{ SeqStack S；
char c，t ；
InitStack(&S)；
Push(&S，'#')； //预先将#压入栈方便算法
do
{ c=getchar()；
switch(c)
{ case ' '：break； //去除空格符
case'0'：
case'1'：
case'2'：
case'3'：
case'4'：
case'5'：
case'6'：
case'7'：
case'8'：
case'9'： EnQueue(Q，C)；break； //数字1~9入队
case'('： Push(&S，c)； break； //左括号入栈
case')'：
case'#'： //右括号和#
do
{ t=pop(&S)； //出栈
if(t!='('&&t!='#') EnQueue(Q，t)； //如果是运算符则入队
}while(t!='('&&S.top!=-1)；break；
//直到左括号出栈或栈空循环结束
case'+'：
case'-'：
case'*'：
case'/'：
while(Priority(c)<=Priority(GetTop(S)))
//当前运算符优先级小于等于栈顶运算符优先级
{ t=pop(&S)；EnQueue(Q，t)； //运算符出栈、入队
}
push(&S，c)； break； //当前运算符入栈
} //EndSwitch
}while(c!='#')； //以'#'号结束表达式扫描
}
3、后缀表达式的计算
后缀表达式9247*+5/-3+的计算过程
| 计算步骤 | 后缀表达式的读入 | 运算结果栈 |
| 初始 | 9247*+5/-3+ | 空 |
| 1 | 247*+5/-3+ | 9 |
| 2 | 47*+5/-3+ | 9 2 |
| 3 | 7*+5/-3+ | 9 2 4 |
| 4 | *+5/-3+ | 9 2 4 7 |
| 5 | +5/-3+ | 9 2 28 |
| 6 | 5/-3+ | 9 30 |
| 7 | /-3+ | 9 30 5 |
| 8 | -3+ | 9 6 |
| 9 | 3+ | 3 |
| 10 | + | 3 3 |
| 11 | 6 |
【算法描述】
int CPostExp(SeqQueue Q) //后缀表达式在队列Q中
{ SeqStackl S； //S是顺序栈
char ch； int x，y；
InitStackl(&S)； //初始化栈S
while(!QueueEmpty(Q))
{ ch=DeQueue(&Q)； //出队
if(ch>='0'&&ch<='9') //是1~9
Pushl(&S，ch-'0')； //入栈
else //是运算符
{ y=Popl(&S)； //两个操作数出栈
x=Popl(&S)；
switch(ch) //两操作数进行计算，结果入栈
{ case '+'： Pushl(&S，x+y)；break；
case '-'： Pushl(&S，x-y)； break；
case '*'： Pushl(&S，x*y)；break；
case '/'： Pushl(&S，x/y)； break；
}
}
}
return GetTopl(S)；//最后栈顶元素就是最终结果
}
【真题选解】阅读下列算法，并回答问题：
（1）假设栈S=（3，8，6，2，5），其中5为栈顶元素，写出执行函数f31（&S）后的S；
（2）简述函数f31的功能。
void f31(Stack *S)
{ Queue Q；InitQueue(&Q); //建立空队Q
while(!StackEmpty(S))
EnQueue(&Q,Pop(&S));
while(!QueueEmpty(Q))
Push(&S,DeQueue(&Q));
}
（1）
（2）
本章小结
本章重点介绍了顺序栈、链栈、循环队列及链队列的存储结构及其基本运算，要求考生能够熟练地掌握。本章的难点是理解递归算法执行过程中栈的状态变化过程以及循环队列对边界条件的处理问题。
在本章中介绍了多个利用队列或栈设计算法解决简单应用问题的实例，特别是表达式求值问题的例子，它是一个综合的应用实例，几乎用到栈和队列的各种运算。通过这些例子，考生可以更好地理解栈和队列的特点和应用，增强分析问题解决问题的能力。
从历年考试情况来看，本章主要考顺序栈、链栈、循环队列及链队列的存储结构及其基本运算，以选择题、填空题为主，有时有简答题或算法阅读理解题。
