数据结构java版第3章.ppt

第3章栈与队列3.1栈和队列基本概念3.2栈的入栈与出栈3.3队列的入队与出队3.4栈与队列的应用3.5程序集锦3.6思考题13.1栈和队列基本概念在算法（algorithms）中，栈（stack）与队列（queue）是常用到的数据结构。栈是一个有序列表（orderlist），其插入（insert）和删除（delete）操作都在同一端，这一端通常称为栈顶（top）。队列（queue）也属于线性列表，与栈不同的是加入和删除不在同一端，删除的那一端称为队头（front），而加入的一端称为队尾（rear）。2栈与队列33.1栈和队列基本概念加入一个元素到栈的操作称为入栈（push），与之相反的是从栈中删除一个元素，称为出栈（pop）。栈是一种后进先出（LastInFirstOut，LIFO）线性表。而队列具有先进先出（FirstInFirstOut，FIFO）的特性。43.2栈的入栈与出栈3.2.1入栈3.2.2出栈53.2.1入栈入栈Java程序片断publicstaticvoidpush_f()/入栈函数DataInputStreamin=newDataInputStream(System.in);if(top=MAX-1)/当栈已满，则显示错误System.out.print(nStackisfull!n);elsetop+;System.out.print(nPleaseenteritemtoinsert:);63.2.1入栈System.out.flush();try stacktop=in.readLine();catch(IOExceptione)73.2.2出栈出栈Java程序片断：publicvoidpop_f()/出栈函数if(top0)/当栈没有数据时，则显示错误System.out.print(nNoitem,stackisempty!n);elseSystem.out.print(nItem+stacktop+deleted!n);top-;System.out.println();83.3队列的入队与出队3.3.1入队3.3.2出队3.3.3循环队列的入队3.3.4循环队列的出队93.3.1入队入队是在队尾，其程序如下：publicvoidenqueue_f()/入队函数DataInputStreamin=newDataInputStream(System.in);if(rear=MAX-1)/当队列已满，则显示错误System.out.println(nQueueisfull!n);elserear+;103.3.1入队System.out.print(nPleaseenteritemtoinsert:);System.out.flush();tryqrear=in.readLine();catch(IOExceptione)System.out.println();113.3.2出队出队是在队头，其Java程序片断如下：publicvoiddequeue_f()/删除函数if(frontrear)/当队列中没有元素存在时，则显示错误System.out.print(nNoitem,queueisempty!n);else123.3.2出队System.out.print(nItem+qfront+deleted!n);front+;System.out.println();133.3.3循环队列的入队循环队列开始的时候，将front与rear的初值均设为MAX1。其Java程序片断如下：publicvoidenqueue_f()/入队函数DataInputStreamin=newDataInputStream(System.in);rear=(rear+1)%MAX;if(front=rear)/当队列已满，则显示错误if(rear=0)rear=MAX1;143.3.3循环队列的入队elserear=rear1;System.out.print(nnQueueisfull!n);elseSystem.out.print(nPleaseenteritemtoinsert:);System.out.flush();trycqrear=in.readLine();catch(IOExceptione)153.3.4循环队列的出队Java程序片断：循环队列的出队函数。publicvoiddequeue_f()/出队函数if(front=rear)/当队列中没有元素存在时，则显示错误System.out.print(nQueueisempty!nn);elsefront=(front+1)%MAX;System.out.print(nnItem+cqfront+deleted!n);163.4栈与队列的应用3.4.1中缀表达式转为后缀表达式（前锥表达式）3.4.2计算后缀表达式173.4.1中缀表达式转为后缀表达式（前缀）栈还有一些很好的用途，就是如何将算术表达式由中缀表达式变为后缀表达式。一般的算术表达式都是以中缀法来表示，即运算符（operator）置于操作数（operand）的中间（假如只有一个操作数，则运算符置于操作数的前面）。而后缀法表示运算符在操作数后面，如：A*B/C，这是中缀表达式，其后缀表达式是AB*C/。18将中缀表达式转换为后缀表达式的算法思想：(从左往右读）1、如果遇到数字，直接放到后缀表达式尾；2、如果遇到遇到运算符 a:若此时站空，则直接入栈；b:循环：若栈不空且栈顶运算符的优先级大于等于当前的运算符，则栈顶运算符出栈，置于后缀表达式尾；直到栈顶运算符的优先级小于当前运算符，把当前运算符入栈置于栈顶。3、反复执行1，2，直到整个中缀表达式扫描完毕，若此时栈不空，则将栈顶的运算符依次出栈，依次置于后缀表达式尾。读到左括号时总是将它压入栈中 读到右括号时，将靠近栈顶的第一个左括号上面的运算符全部依次弹出，送至输出队列后，再丢弃左括号。19将中缀表达式转换为后缀表达式的算法思想：(从左往右读）（从右向左）1、如果遇到数字，直接放到后缀表达式尾；（前端）2、如果遇到遇到运算符 a:若此时站空，则直接入栈；b:循环：若栈不空且栈顶运算符的优先级大于等于当前的运算符，则栈顶运算符出栈，置于后缀表达式尾（前端）；直到栈顶运算符的优先级小于当前运算符，把当前运算符入栈置于栈顶。3、反复执行1，2，直到整个中缀表达式扫描完毕，若此时栈不空，则将栈顶的运算符依次出栈，依次置于后缀表达式尾（前端）。读到左（右）括号时总是将它压入栈中 读到右（左）括号时，将靠近栈顶的第一个左（右）括号上面的运算符全部依次弹出，送至输出队列后，再丢弃左（右）括号。3.4.1 3.4.1 中缀表达式转为前缀表达式 中缀表达式转为前缀表达式20其他能做出正确结果的方法a+b*c-(d+e)第一步：按照运算符的优先级对所有的运算单位加括号式子变成拉：(a+(b*c)-(d+e)第二步：转换前缀与后缀表达式前缀：把运算符号移动到对应的括号前面则变成拉：-(+(a*(bc)+(de)把括号去掉：-+a*bc+de前缀式子出现后缀：把运算符号移动到对应的括号后面则变成拉：(a(bc)*)+(de)+)-把括号去掉：abc*+de+-后缀式子出现213.4.2计算后缀表达式当将中缀表达式转换为后缀表达式后，就可以很容易将此表达式的值计算出来，其步骤如下：1.将后缀表达式用字符串表示。2.从左往右取，每次取一个token，若此token为一操作数则将它push到栈，若此token为一运算符，则自栈pop出两个操作数并做适当的运算，若此token为0则goto步骤4。3.将步骤2的结果再push到栈，goto步骤2。4.将栈中的数据出栈，这个数即为后缀表达式计算的结果。223.4.2计算后缀表达式举例说明，如果有一个中缀表达式为10+86*5转换为后缀表达式为108+65*，利用上述的规则执行。（1）因为10为一操作数故将它push到栈，同理8也是，故栈有2个数据分别为10和8，如图（a）所示。（2）之后的token为+，故pop栈的8和10做加法运算，结果为18，再次将18push到栈，如图（b）所示。233.4.2计算后缀表达式（3）接下来将6和5push到栈，如图（c）所示。（4）之后的token为*，故pop5和6做乘法运算为30，并将它push到栈，如图（d）所示。（5）之后的token为，故pop30和18，此时要注意的是18减去30，答案为12（是下面的数据减去上面的数据）。对于+和*，此顺序并不影响，但对和/就非常重要。2 43.4.2计算前缀表达式当将中缀表达式转换为前缀表达式后，就可以很容易将此表达式的值计算出来，其步骤如下：1.将后缀表达式用字符串表示。2.从左往右取（从右往左取），每次取一个token，若此token为一操作数则将它push到栈，若此token为一运算符，则自栈pop出两个操作数并做适当的运算，若此token为0则goto步骤4。3.将步骤2的结果再push到栈，goto步骤2。4.将栈中的数据出栈，这个数即为后缀表达式计算的结果。25