《数据结构java版第3章.ppt》由会员分享，可在线阅读，更多相关《数据结构java版第3章.ppt（33页珍藏版）》请在三一办公上搜索。
1、1,第3章 栈与队列,3.1 栈和队列基本概念3.2 栈的入栈与出栈 3.3 队列的入队与出队 3.4 栈与队列的应用 3.5 程序集锦3.6 思考题,2,3.1 栈和队列基本概念,在算法（algorithms）中，栈（stack）与队列（queue）是常用到的数据结构。栈是一个有序列表（order list），其插入（insert）和删除（delete）操作都在同一端，这一端通常称为栈顶（top）。队列（queue）也属于线性列表，与栈不同的是加入和删除不在同一端，删除的那一端称为队头（front），而加入的一端称为队尾（rear）。,3,栈与队列,4,3.1 栈和队列基本概念,加入一个元素
2、到栈的操作称为入栈（push），与之相反的是从栈中删除一个元素，称为出栈（pop）。栈是一种后进先出（Last In First Out，LIFO）线性表。而队列具有先进先出（First In First Out，FIFO）的特性。,5,3.2 栈的入栈与出栈,3.2.1 入栈 3.2.2 出栈,6,3.2.1 入栈,入栈Java程序片断 public static void push_f()/入栈函数DataInputStream in=new DataInputStream(System.in);if(top=MAX-1)/当栈已满，则显示错误 System.out.print(n Sta
3、ck is full!n);else top+;System.out.print(n Please enter item to insert:);,7,3.2.1 入栈,System.out.flush();try stacktop=in.readLine();catch(IOException e),8,3.2.2 出栈,出栈Java程序片断：public void pop_f()/出栈函数if(top 0)/当栈没有数据时，则显示错误 System.out.print(n No item,stack is empty!n);else System.out.print(n Item+stac
4、ktop+deleted!n);top-;System.out.println();,9,3.3 队列的入队与出队,3.3.1 入队3.3.2 出队3.3.3 循环队列的入队3.3.4 循环队列的出队,10,3.3.1 入队,入队是在队尾，其程序如下：public void enqueue_f()/入队函数DataInputStream in=new DataInputStream(System.in);if(rear=MAX-1)/当队列已满，则显示错误 System.out.println(n Queue is full!n);else rear+;,11,3.3.1 入队,System.
5、out.print(n Please enter item to insert:);System.out.flush();try qrear=in.readLine();catch(IOException e)System.out.println();,12,3.3.2 出队,出队是在队头，其Java程序片断如下：public void dequeue_f()/删除函数if(front rear)/当队列中没有元素存在时，则显示错误 System.out.print(n No item,queue is empty!n);else,13,3.3.2 出队,System.out.print(n
6、Item+qfront+deleted!n);front+;System.out.println();,14,3.3.3 循环队列的入队,循环队列开始的时候，将front与rear的初值均设为MAX1。其Java程序片断如下：public void enqueue_f()/入队函数DataInputStream in=new DataInputStream(System.in);rear=(rear+1)%MAX;if(front=rear)/当队列已满，则显示错误if(rear=0)rear=MAX1;,15,3.3.3 循环队列的入队,elserear=rear1;System.out.p
7、rint(nnQueue is full!n);else System.out.print(nPlease enter item to insert:);System.out.flush();try cqrear=in.readLine();catch(IOException e),16,3.3.4 循环队列的出队,Java程序片断：循环队列的出队函数。public void dequeue_f()/出队函数if(front=rear)/当队列中没有元素存在时，则显示错误System.out.print(nQueue is empty!nn);else front=(front+1)%MAX;
8、System.out.print(nnItem+cqfront+deleted!n);,17,3.4 栈与队列的应用,3.4.1 中缀表达式转为后缀表达式（前锥表达式）3.4.2 计算后缀表达式,18,3.4.1 中缀表达式转为后缀表达式（前缀）,栈还有一些很好的用途，就是如何将算术表达式由中缀表达式变为后缀表达式。一般的算术表达式都是以中缀法来表示，即运算符（operator）置于操作数（operand）的中间（假如只有一个操作数，则运算符置于操作数的前面）。而后缀法表示运算符在操作数后面，如：A*B/C，这是中缀表达式，其后缀表达式是 AB*C/。,19,将中缀表达式转换为后缀表达式的算法
9、思想：(从左往右读）1、如果遇到数字，直接放到后缀表达式尾；2、如果遇到遇到运算符 a:若此时站空，则直接入栈；b:循环：若栈不空且栈顶运算符的优先级大于等于当前的运算符，则栈顶运算符出栈，置于后缀表达式尾；直到栈顶运算符的优先级小于当前运算符，把当前运算符入栈置于栈顶。3、反复执行1，2，直到整个中缀表达式扫描完毕，若此时栈不空，则将栈顶的运算符依次出栈，依次置于后缀表达式尾。读到左括号时总是将它压入栈中 读到右括号时，将靠近栈顶的第一个左括号上面的运算符全部依次弹出，送至输出队列后，再丢弃左括号。,20,将中缀表达式转换为后缀表达式的算法思想：(从左往右读）（从右向左）1、如果遇到数字，直
10、接放到后缀表达式尾；（前端）2、如果遇到遇到运算符 a:若此时站空，则直接入栈；b:循环：若栈不空且栈顶运算符的优先级大于等于当前的运算符，则栈顶运算符出栈，置于后缀表达式尾（前端）；直到栈顶运算符的优先级小于当前运算符，把当前运算符入栈置于栈顶。3、反复执行1，2，直到整个中缀表达式扫描完毕，若此时栈不空，则将栈顶的运算符依次出栈，依次置于后缀表达式尾（前端）。读到左（右）括号时总是将它压入栈中 读到右（左）括号时，将靠近栈顶的第一个左（右）括号上面的运算符全部依次弹出，送至输出队列后，再丢弃左（右）括号。,3.4.1 中缀表达式转为前缀表达式,21,其他能做出正确结果的方法,a+b*c-(
11、d+e)第一步：按照运算符的优先级对所有的运算单位加括号式子变成拉：(a+(b*c)-(d+e)第二步：转换前缀与后缀表达式前缀：把运算符号移动到对应的括号前面则变成拉：-(+(a*(bc)+(de)把括号去掉：-+a*bc+de前缀式子出现后缀：把运算符号移动到对应的括号后面则变成拉：(a(bc)*)+(de)+)-把括号去掉：abc*+de+-后缀式子出现,22,3.4.2 计算后缀表达式,当将中缀表达式转换为后缀表达式后，就可以很容易将此表达式的值计算出来，其步骤如下：1.将后缀表达式用字符串表示。2.从左往右取，每次取一个token，若此token为一操作数则将它push到栈，若此to
12、ken为一运算符，则自栈pop出两个操作数并做适当的运算，若此token为 0 则goto步骤4。3.将步骤2的结果再push到栈，goto步骤2。4.将栈中的数据出栈，这个数即为后缀表达式计算的结果。,23,3.4.2 计算后缀表达式,举例说明，如果有一个中缀表达式为10+86*5转换为后缀表达式为10 8+6 5*，利用上述的规则执行。（1）因为10为一操作数故将它push到栈，同理8也是，故栈有2个数据分别为10和8，如图（a）所示。（2）之后的token为+，故pop栈的8和10做加法运算，结果为18，再次将18 push到栈，如图（b）所示。,24,3.4.2 计算后缀表达式,（3）
13、接下来将6和5 push到栈，如图（c）所示。（4）之后的token为*，故pop 5和6做乘法运算为30，并将它push到栈，如图（d）所示。（5）之后的token为，故pop 30和18，此时要注意的是18减去30，答案为12（是下面的数据减去上面的数据）。对于+和*，此顺序并不影响，但对和/就非常重要。,25,3.4.2 计算前缀表达式,当将中缀表达式转换为前缀表达式后，就可以很容易将此表达式的值计算出来，其步骤如下：1.将后缀表达式用字符串表示。2.从左往右取（从右往左取），每次取一个token，若此token为一操作数则将它push到栈，若此token为一运算符，则自栈pop出两个操
14、作数并做适当的运算，若此token为 0 则goto步骤4。3.将步骤2的结果再push到栈，goto步骤2。4.将栈中的数据出栈，这个数即为后缀表达式计算的结果。,26,练习题,1.将下列中缀表达式转换为后缀表达式：（1）a b&C d&e f（2）(a+b)*c/d+e 82.有一个中缀表达式如下：5/3*(14)+3 8请将它转换为后缀表达式，再求出其结果是多少。,27,3.5 程序集锦,1栈的入栈与出栈的程序实例2队列的入队与出队的程序实例（使用循环队列处理数据）3将表达式由中缀表达式转换为后缀表达式的程序实例,28,3.6 思考题,1.将下列中缀表达式转换为前缀与后缀表达式。（1）A
15、*B%C（2）A+BCD（3）A/B+C（4）(A+B)*D+E/(F+A*D)+C（5）A/(B*C)+D*EA*C（6）A&B|C|!(E F)（7）A/B*C+D%EA/C*F（8）(A*B)*(C*D)%E*(FG)/HIJ*K/L（9）A*(B+C)*D提示：前缀与后缀的操作二者正好相反。,29,3.6 思考题,有一个铁路交换网络（switching network）如下图所示。火车厢置于右边，各节都有编号如1，2，3，n，每节车厢可以从右边开进栈，然后再开到左边，如n=3，若将1，2，3按顺序入栈，再驶到左边，此时可得到3，2，1的顺序。请问：,30,3.6 思考题,（1）当n=3
16、及n=4时，分别有哪几种排列的方式？哪几种排序方式不可能发生？（2）当n=6时，325641这样的排列是否可能发生？那154623的排列又是如何？（3）找出一公式，当有n节车厢时，共有几种排列方式？,31,32,33,卡特兰数 Catalan Number,对于每一个数来说，必须进栈一次、出栈一次。我们把进栈设为状态1，出栈设为状态0。n个数的所有状态对应n个1和n个0组成的2n位二进制数。由于等待入栈的操作数按照1n的顺序排列、入栈的操作数b大于等于出栈的操作数a(ab)，因此输出序列的总数目=由左而右扫描由n个1和n个0组成的2n位二进制数，1的累计数不小于0的累计数的方案种数。在2n位二
17、进制数中填入n个1的方案数为c(2n,n),不填1的其余n位自动填0。从中减去不符合要求（由左而右扫描，0的累计数大于1的累计数）的方案数即为所求。不符合要求的数的特征是由左而右扫描时，必然在某一奇数位2m+1位上首先出现m+1个0的累计数和m个1的累计数，此后的2(n-m)-1位上有n-m个 1和n-m-1个0。如若把后面这2(n-m)-1位上的0和1互换，使之成为n-m个0和n-m-1个1，结果得1个由n+1个0和n-1个1组成的2n位数，即一个不合要求的数对应于一个由n+1个0和n-1个1组成的排列。反过来，任何一个由n+1个0和n-1个1组成的2n位二进制数，由于0的个数多2个，2n为偶数，故必在某一个奇数位上出现0的累计数超过1的累计数。同样在后面部分0和1互换，使之成为由n个0和n个1组成的2n位数，即n+1个0和n-1个1组成的2n位数必对应一个不符合要求的数。因而不合要求的2n位数与n1个0，n1个1组成的排列一一对应。显然，不符合要求的方案数为c(2n,n+1)。由此得出 输出序列的总数目=c(2n,n)-c(2n,n+1)=1/(n+1)*c(2n,n),
