数据结构java版第3章.ppt

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 栈和队列基本概念,加入一个元素到栈的操作称为入栈（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 Stack 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 “ + stacktop + “ 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.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 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 循环队列的入队,else rear=rear1; System.out.print(“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; 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,将中缀表达式转换为后缀表达式的算法思想：(从左往右读） 1、如果遇到数字，直接放到后缀表达式尾； 2、如果遇到遇到运算符 a:若此时站空，则直接入栈； b:循环：若栈不空且栈顶运算符的优先级大于等于当前的运算符，则栈顶运算符出栈，置于后缀表达式尾；直到栈顶运算符的优先级小于当前运算符，把当前运算符入栈置于栈顶。 3、反复执行1，2，直到整个中缀表达式扫描完毕，若此时栈不空，则将栈顶的运算符依次出栈，依次置于后缀表达式尾。 读到左括号时总是将它压入栈中 读到右括号时，将靠近栈顶的第一个左括号上面的运算符全部依次弹出，送至输出队列后，再丢弃左括号。,20,将中缀表达式转换为后缀表达式的算法思想：(从左往右读） （从右向左） 1、如果遇到数字，直接放到后缀表达式尾；（前端） 2、如果遇到遇到运算符 a:若此时站空，则直接入栈； b:循环：若栈不空且栈顶运算符的优先级大于等于当前的运算符，则栈顶运算符出栈，置于后缀表达式尾（前端）；直到栈顶运算符的优先级小于当前运算符，把当前运算符入栈置于栈顶。 3、反复执行1，2，直到整个中缀表达式扫描完毕，若此时栈不空，则将栈顶的运算符依次出栈，依次置于后缀表达式尾（前端）。 读到左（右）括号时总是将它压入栈中 读到右（左）括号时，将靠近栈顶的第一个左（右）括号上面的运算符全部依次弹出，送至输出队列后，再丢弃左（右）括号。,3.4.1 中缀表达式转为前缀表达式,21,其他能做出正确结果的方法,a+b*c-(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到栈，若此token为一运算符，则自栈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）接下来将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出两个操作数并做适当的运算，若此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 8 2. 有一个中缀表达式如下： 5/3 * (14) + 3 8 请将它转换为后缀表达式，再求出其结果是多少。,27,3.5 程序集锦,1栈的入栈与出栈的程序实例 2队列的入队与出队的程序实例（使用循环队列处理数据） 3将表达式由中缀表达式转换为后缀表达式的程序实例,28,3.6 思考题,1. 将下列中缀表达式转换为前缀与后缀表达式。 （1）A * 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及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位二进制数中填入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个