第4章栈和队列.ppt

栈表达式求值队列优先队列栈(Stack)栈和队列都是受限的线性表只允许在一端插入和删除的线性表允许插入和删除的一端称为栈顶(top)，另一端称为栈底(bottom)特点后进先出(LIFO)栈的抽象数据类型栈的数组表示—顺序栈栈的链接表示—链式栈链式栈无栈满问题，空间可扩充插入与删除仅在栈顶处执行链式栈不需要表头结点队列(Queue)定义队列是只允许在一端删除，在另一端插入的线性表允许删除的一端叫做队头(front)，允许插入的一端叫做队尾(rear)。特性先进先出(FIFO,FirstInFirstOut)队列的抽象数据类型队头指针进1:front=(front+1)%size;队尾指针进1:rear=(rear+1)%size;队列初始化：front=rear=0;队空条件：front==rear;队满条件：(rear+1)%size==front循环队列的类定义队列的链接表示—链式队列队头在链头，队尾在链尾。链式队列在进队时无队满问题，但有队空问题。队空条件为front==NULL表达式求值一个表达式由操作数(亦称运算对象)、操作符(亦称运算符)和分界符组成。算术表达式有三种表示：中缀(infix)表示操作数操作符操作数，如A+B；前缀(prefix)表示操作符操作数操作数，如+AB；后缀(postfix)表示操作数操作数操作符，如AB+；表达式的中缀表示a+b*(c-d)-e^f/g表达式中相邻两个操作符的计算次序为：优先级高的先计算；优先级相同的自左向右计算；当使用括号时从最内层括号开始计算。C++中操作符的优先级优先级 操作符 1 单目-、！2 *、/、% 3 +、- 4 、=、、=5==、!= 6 7 || 一般表达式的操作符有4种类型：算术操作符如双目操作符（+、-、*、/和%）以及单目操作符（-）。关系操作符包括、=、==、!=、=、。这些操作符主要用于比较。逻辑操作符如与()、或(||)、非(!)。括号‘(’和‘)’它们的作用是改变运算顺序。应用后缀表示计算表达式的值从左向右顺序地扫描表达式，并用一个栈暂存扫描到的操作数或计算结果。在后缀表达式的计算顺序中已隐含了加括号的优先次序，括号在后缀表达式中不出现。计算例abcd-*+ef^g/-通过后缀表示计算表达式值的过程顺序扫描表达式的每一项，根据它的类型做如下相应操作：若该项是操作数，则将其压栈；若该项是操作符op，则连续从栈中退出两个操作数Y和X，形成运算指令XopY，并将计算结果重新压栈。当表达式的所有项都扫描并处理完后，栈顶存放的就是最后的计算结果。voidCalculator::Run(){charch;doublenewoperand;while(cinch,ch!=‘=’){switch(ch){case‘+’:case‘-’:case‘*’:case‘/’: DoOperator(ch);break;//计算default:cin.putback(ch);//将字符放回输入流cinnewoperand;//读操作数AddOperand(newoperand);}}}利用栈将中缀表示转换为后缀表示使用栈可将表达式的中缀表示转换成它的前缀表示和后缀表示。为了实现这种转换，需要考虑各操作符的优先级。各个算术操作符的优先级isp叫做栈内(instackpriority)优先数icp叫做栈外(incomingpriority)优先数。操作符优先数相等的情况只出现在括号配对或栈