果入栈。3、若表达式未读完，就重复24、最后栈顶的数值则为结果。4将中缀表达式转化为后缀表达式的算法要将中缀表达式转化为等价的后缀表达式，须从左至右扫描中缀表达式，并用一个栈存放中缀表达式的“（”和暂时不能参与计算的运算符。1、当读到数字直接送至后缀表达式中2、当读到运算符t时，a将栈中所有优先级高于或等于t的运算符弹出，送到后缀表达式中；bt进栈3、读到左括号时总是将它压入栈中4、读到右括号时，将靠近栈顶的第一个左括号上面的运算符全部依次弹出，送至后缀表达式后，再丢弃左括号。练习：1、编号分别为1N的N辆列车进入一个栈式结构的站台。试给出这N辆列车开出车站的所有可能次序。如，编号为14的四辆列车按照push、push、pop、push、push、pop、pop、pop操作，可使得开出车站的冷为2431。程序2、若表达中操作数为非个位数值，如何实现表达式计算。
f信息学奥赛之
数据结构栈与队列
队列
1队列的特点：
队列也是一种线性表，对于它所有的插入都在队列的一端进行，所有的删除都在另一端进行，进行删除的一端叫队列的“头”fro
t，进行插入的一端叫队列的“尾”rear，其操作特点是“先进先出”。FIFOFirstI
FirstOut
2队列的抽象数据定义：抽
1队列的数组表示队typequeuerecorddataarray1mofdatatypefro
trear1me
dvarqqueue2队列的链接表示链式队列队
队头在链头，队尾在链尾。链式队列在进队时无队满问题，但有队空问题。队空条件为fro
t
il链式队列编码举例typequeuestructstructrecorddatadatatypeli
kqueuee
dvarfro
trearq1q2queue3循环队列：存储队列的数组（或链表）被当作首尾相接的表处理存
3队列的基本操作：
1队列的插入e
qqx：在队列q中插入一个值为x的元素，也称为进队；qrearx若rearm则rear1否则rearrear1若rearfro
t则writeoverflow2队列的删除deqq：从队列q中删除一个元素，也称为出队；若rearfro
t则writeu
derflow
f信息学奥赛之
数据结构栈与队列
否则若fro
tm则fro
t1否则fro
tfro
t13读队头元素fro
tqx：将队列q中头部元素的值读到x中；若rearfro
t则writeerror否则xqfro
t4判队列是否为空qemptyq：这是一个布尔函数，当q是空队列时，取真值，否则取假值。若rearfro
t则qemptytrue否则qemptyfalse
3队列的应用：
例、广义表（是线性表的一种推广；允许构成线性表的元素本身又可以是线性表，则该线性表为广义表。广义表是一个递归定义的表，允许其元素是本身的一个子r