数据结构第六次课-栈和队列B.ppt

《数据结构第六次课-栈和队列B.ppt》由会员分享，可在线阅读，更多相关《数据结构第六次课-栈和队列B.ppt（34页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、电气信息学院 计算机系数据结构每课一贴：原来很简单 有一个人去应征工作，随手将走廊上的纸屑捡起来，放进了垃圾桶，被路过的口试官看到了，因此他得到了这份工作。原来获得赏识很简单，养成好习惯就可以了。住在田边的青蛙对住在路边的青蛙说：你这里太危险，搬来跟我住吧！路边的青蛙说：我已经习惯了，懒得搬了。几天后，田边的青蛙去探望路边的青蛙，却发现他已被车子压死，暴尸在马路。原来掌握命运的方法很简单，远离懒惰就可以了。1电气信息学院 计算机系数据结构2.逻辑结构逻辑结构 与同线性表相同，仍为一对一关系与同线性表相同，仍为一对一关系。3.运算规则运算规则 只能在只能在栈顶栈顶运算，且访问结点时依照运算，且访

2、问结点时依照后进先出后进先出 （LIFOLIFO）或先进后出或先进后出（FILOFILO）的原则。的原则。4.出栈顺序：出栈顺序：1.定义定义 限定只能在限定只能在表的一端表的一端进行插入和删除运算的进行插入和删除运算的2.线性表线性表（只能在（只能在栈顶栈顶操作）操作）上次课内容回顾上次课内容回顾2电气信息学院 计算机系数据结构讨论：有无通用的判别原则？讨论：有无通用的判别原则？有。在可能的输出序列中，不存在这样的输入序列有。在可能的输出序列中，不存在这样的输入序列i i，j j，k k，能同时满足能同时满足入栈入栈顺序顺序i i，j j，k k 和和 出栈出栈顺序顺序k k，i i，j j

3、。例例4 4 一个栈的输入序列为一个栈的输入序列为1234512345，若在入栈的过，若在入栈的过程中允许出栈，则可能得到的出栈序列程中允许出栈，则可能得到的出栈序列有多少种，有多少种，分别是什么分别是什么？3电气信息学院 计算机系数据结构例例1：回文游戏回文游戏 设计思路：用栈暂存回文设计思路：用栈暂存回文例例2：数制转换数制转换（十转（十转N）设计思路：用栈暂存低位值设计思路：用栈暂存低位值例例3：括号匹配的检验：括号匹配的检验 设计思路：用栈暂存左括号设计思路：用栈暂存左括号例例4：表达式求值表达式求值 设计思路：用栈暂存运算符设计思路：用栈暂存运算符 简化程序设计问题简化程序设计问题4

4、电气信息学院 计算机系数据结构v回文游戏：顺读与逆读字符串一样（不含空格）dadtop1.读入字符串2.压入栈3.原串字符与出栈字符依次比较 若不等，非回文 若直到栈空都相等，则是回文有没有更简洁的办法呢？(读入字符串，压入n/2个字符,n为字符个数)v多进制输出：字符串：“madam I madam”“上海自来水来自海上”例 把十进制数159转换成八进制数(159)10=(237)815981982802 3 7 余 7余 3余 2toptop7top73top7325电气信息学院 计算机系数据结构v多进制输出：例 把十进制数159转换成八进制数(159)10=(237)8159819828

5、02 3 7 余 7余 3余 2toptop7top73top732public class Test public static void main(String args)int i=159;String binStr=Integer.toBinaryString(i);String otcStr=Integer.toOctalString(i);String hexStr=Integer.toHexString(i);System.out.println(binStr);6电气信息学院 计算机系数据结构v多进制输出：import java.util.*;class T public st

6、atic void main(String args)System.out.println(toOctal(159);public static String toOctal(int a)String str=;Stack s=new Stack();while(a!=0)s.push(a%8);a=a/8;while(!s.empty()str+=s.pop();return str;例 把十进制数159转换成八进制数7电气信息学院 计算机系数据结构例如：例如：3*（7 2）(1)要正确求值，首先了解算术四则运算的规则：要正确求值，首先了解算术四则运算的规则：a.从左算到右从左算到右 b.先

7、乘除，后加减先乘除，后加减 c.先括号内，后括号外先括号内，后括号外 由此，由此，通常通常此表达式的计算顺序为：此表达式的计算顺序为：3*（7 2）=3*5=15v 表达式求值(这是栈应用的典型例子)这里，这里，表达式求值的算法是表达式求值的算法是 “算符优先法算符优先法”。8电气信息学院 计算机系数据结构表达式表示法表达式表示法 算术表达式中最常见的表示法形式有 中缀、前缀和 后缀表示法。中缀表示法是书写表达式的常见方式，而前缀和后缀表示法主要用于计算机科学领域。中缀表示法中缀表示法 Syntax:operand1 operator operand2Example:(A+B)*C-D/(E+

8、F)前缀表示法前缀表示法-波兰表示法（波兰表示法（Polish notation，PN）Syntax :operator operand1 operand2Example:-*+ABC/D+EF后缀表示法后缀表示法-逆波兰表示法（逆波兰表示法（Reverse Polish Notation，RPN）Syntax :operand1 operand2 operatorExample:AB+C*DEF+/-无操作符优先级问题，求值简单无操作符优先级问题，求值简单9电气信息学院 计算机系数据结构1.中缀表达式到后缀表达式的转换 要把表达式从中缀表达式的形式转换成用后缀表示法表示的等价表达式，必须了解

9、操作符的优先级和结合性。优先级或者说操作符的强度决定求值顺序；优先级高的操作符比优先级低的操作符先求值。如果所有操作符优先级一样，那么求值顺序就取决于它们的 结合性。操作符的结合性定义了相同优先级操作符组合的顺序（从右至左或从左至右）。Left associativity :A+B+C=(A+B)+CRight associativity:ABC=A(BC)常用表达式求值方法常用表达式求值方法1.中缀表达式转换成后缀表达式2.计算后缀表达式10电气信息学院 计算机系数据结构转换算法：1.读入运算对象（数据），直接输出2.遇到(运算符进栈3.遇到)运算符，则栈内的最上一个(以上的所有运算符退栈，

10、(也退栈4.读入运算符，进入运算栈 4.1 后进栈的运算符 先进栈的运算符，运算符进栈 (优先级比较)4.2 后进栈的运算符=先进栈的运算符，将栈内的运算符退栈输出，再进栈11电气信息学院 计算机系数据结构31*(5-22)+7012电气信息学院 计算机系数据结构后缀表达式求值后缀表达式求值 对后缀表达式求值比直接对中缀表达式求值简单。在后缀表对后缀表达式求值比直接对中缀表达式求值简单。在后缀表达式中，达式中，不需要括号，而且操作符的优先级也不再起作用了不需要括号，而且操作符的优先级也不再起作用了。可以用如下算法对后缀表达式求值：初始化一个空堆栈 从左到右读入后缀表达式 如果字符是一个操作数，

11、把它压入堆栈。如果字符是个操作符，弹出两个操作数，执行操作，然后把结果压入堆栈。到后缀表达式末尾，从堆栈中弹出结果。若后缀表达式格式正确，那么堆栈应该为空。13电气信息学院 计算机系数据结构31*(5-22)+70参看Class1.java代码14电气信息学院 计算机系数据结构1.顺序栈的一般定义/堆栈接口public interface Stack public int getSize();public boolean isEmpty();public void push(Object e);public Object pop()throws StackEmptyException;publ

12、ic Object peek()throws StackEmptyException;二.基本操作的程序实现基本操作的程序实现15电气信息学院 计算机系数据结构1.顺序栈的一般定义public class StackArray implements Stack private final int LEN=8;/private Object elements;/private int top;public StackArray()top=-1;elements=new ObjectLEN;public int getSize()return top+1;public boolean isEmpt

13、y()return top=elements.length)expandSpace();elements+top=e;二.基本操作的程序实现基本操作的程序实现16电气信息学院 计算机系数据结构 private void expandSpace()Object a=new Objectelements.length*2;for(int i=0;ielements.length;i+)ai=elementsi;elements=a;public Object pop()throws StackEmptyException if(getSize()1)throw new StackEmptyExce

14、ption(“错误，堆栈空”);Object obj=elementstop;elementstop-=null;return obj;public Object peek()throws StackEmptyException if(getSize()1)throw new StackEmptyException(“错误，堆栈空”);return elementstop;17电气信息学院 计算机系数据结构l入栈算法l 出栈算法 .栈底toptopxptop .栈底topq链栈基本操作P67 Stack的链式存储实现初始化、判断栈空、栈满、初始化、判断栈空、栈满、入栈、出栈入栈、出栈、取栈顶元

15、素、销毁、取栈顶元素、销毁。SLNode p=new SLNode(x,top);top=p;size+;栈非空，则Object obj=top.getData();top=top.getNext();size-;18电气信息学院 计算机系数据结构补充补充1：若入栈动作使地址若入栈动作使地址向高端向高端增长，称为增长，称为“向上生成向上生成”的栈；的栈；若入栈动作使地址若入栈动作使地址向低端向低端增长，称为增长，称为“向下生成向下生成”的栈；的栈；top=0123450栈空 对于向上生成的栈对于向上生成的栈入栈入栈口诀：堆栈指针口诀：堆栈指针top先压后加先压后加（vtop+=xvtop+=x

16、）；）；出栈出栈口诀：堆栈指针口诀：堆栈指针top先减后弹先减后弹（y=v-topy=v-top)。对于向下生成的栈对于向下生成的栈若约定若约定top指向栈顶元素的后一个位置指向栈顶元素的后一个位置入栈入栈口诀：堆栈指针口诀：堆栈指针top先压后减先压后减（vvtoptop-=x=x）；）；出栈出栈口诀：堆栈指针口诀：堆栈指针top先加后弹先加后弹（y=vy=v+toptop)。top=6123450栈空19电气信息学院 计算机系数据结构第三章 栈和队列3.2 队队（Queue）1.队的基本理论队的基本理论2.定义、逻辑结构、存储结构、基本运定义、逻辑结构、存储结构、基本运算规则、队的应用算规

17、则、队的应用3.2.基本操作的程序实现方法基本操作的程序实现方法20电气信息学院 计算机系数据结构3.2 队列队列的定义及特点v定义：队列是限定只能在表的一端进行插入，在表的另一端进行删除的线性表l队尾(rear)允许插入的一端l队头(front)允许删除的一端v队列特点：先进先出(FIFO)a1 a2 a3.an 入队出队队头front队尾rear队列Q=(a1,a2,an)21电气信息学院 计算机系数据结构ADT Queue 数据对象数据对象：D=ai|aiElemSet,i=1,2,n,n0 数据关系数据关系：R1=|ai-1,ai D,i=2,n 基本操作基本操作：getSize();

18、/返回队列大小，即元素个数 isEmpty();/对为空返回true,否则返回false enqueue(e);/数据元素e入对 dequeue();/对头元素出对 peek();/获取对头元素，但不出对/ADT Queue队的抽象数据类型定义队的抽象数据类型定义22电气信息学院 计算机系数据结构队列的顺序存储结构v实现：用一维数组实现sqMfront=-1rear=-1123450队空123450frontJ1,J1,J3入队J1J2J3rearrear123450J4,J5,J6入队J4J5J6front设两个指针front,rear,约定：rear指示队尾元素；front指示队头元素前一

19、位置初值front=rear=-1 空队列条件：front=rear入队列：sq+rear=x;出队列：x=sq+front;rearrearfrontrear123450J1,J2,J3出队J1J2J3frontfrontfront队列会满吗？队列会满吗？这样操作有这样操作有没有问题？没有问题？23电气信息学院 计算机系数据结构v存在问题设数组容量为M，则：l当front=-1,rear=M-1时，再有元素入队发生溢出真溢出l当front-1,rear=M-1时，再有元素入队发生溢出假溢出0M-11frontrear.v解决方案l队首固定，每次出队剩余元素向下移动浪费时间l循环队列u基本思想

20、：把队列设想成环形，让sq0接在sqM-1之后，若rear+1=M,则令rear=0;在顺序队中，当尾指针已经到了数组的上界，不能再有入队在顺序队中，当尾指针已经到了数组的上界，不能再有入队操作，但其实数组中还有空位置，这就叫操作，但其实数组中还有空位置，这就叫“假溢出假溢出”。u实现：利用“求模”运算u入队：rear=(rear+1)%M;sqrear=x;u出队：front=(front+1)%M;x=sqfront;u队满、队空判定条件？24电气信息学院 计算机系数据结构012345rearfrontJ4J5J6012345rearfrontJ9J8J7J4J5J6012345rearf

21、ront初始状态J4,J5,J6出队J7,J8,J9入队队空：front=rear队满：front=rear真溢出假溢出25电气信息学院 计算机系数据结构解决方案有三：解决方案有三：加设加设标志位标志位，让删除动作使其为，让删除动作使其为1,插入动作使其为插入动作使其为0,则可识别当前则可识别当前front=rear人为人为浪费一个单元浪费一个单元，令，令队满特征为队满特征为front=(rear+1)%N；使用一个使用一个计数器计数器记录队列中元素个数（即队列长度）；记录队列中元素个数（即队列长度）；选用选用空闲单元法：空闲单元法：即即front和和rear之一指向实元素，另一指向之一指向实

22、元素，另一指向空闲元素。空闲元素。队空条件队空条件:front=rear (初始化时：初始化时：front=rear)队满条件队满条件：front=(rear+1)%N (N=maxsize)队列长度：队列长度：L=（Nrearfront）%N rearJ2 J3J1 J4 J5front问问2：在具有在具有n个单元的循环队列个单元的循环队列中，队满时共有多少个元素？中，队满时共有多少个元素？问问1：左图中队列长度左图中队列长度L=？左图中队列左图中队列容量容量maxsize N=？n-15626电气信息学院 计算机系数据结构J2 J3J1 J4 J5rearfrontfrontfrontfr

23、ontJ6 J5J7J8 J9例例1：一循环队列如下图所示，若先删除一循环队列如下图所示，若先删除4个元素，接着再个元素，接着再插入插入4个元素，请问队头和队尾指针分别指向哪个位置个元素，请问队头和队尾指针分别指向哪个位置?front解：解：由图可知，队头和队尾指针的初态分别为由图可知，队头和队尾指针的初态分别为front=1和和rear=6。frontrear删除删除4个元素后个元素后front=5；再插入再插入4个元素后，个元素后，r=(6+4)%6=4 frontu入队：rear=(rear+1)%M;u出队：front=(front+1)%M;27电气信息学院 计算机系数据结构例例2

24、2：数组数组nn用来表示一个循环队列，用来表示一个循环队列，f f 为当前队列头为当前队列头元素的元素的前一前一位置，位置，r r 为队尾元素的位置。假定队列中元素的为队尾元素的位置。假定队列中元素的个数小于个数小于n n，计算队列中元素的公式为计算队列中元素的公式为:（）（）rf （）（）（nfr）%n （）nrf （）（nrf）%n4种公式哪种合理？种公式哪种合理？当当 r f 时（时（A）合理；合理；当当 r f 时（时（C）合理；合理；分析分析：综合综合2种情况，以种情况，以（D）的表达最为合理的表达最为合理例例3：在一个循环队列中，若约定队首指针指向队首元素在一个循环队列中，若约定队

25、首指针指向队首元素的的前一个前一个位置。那么，从循环队列中删除一个元素时，其位置。那么，从循环队列中删除一个元素时，其操作是操作是 先先 ，后，后 。移动队首指针移动队首指针取出元素取出元素rear123450J4,J5,J6入队J4J5J6front28电气信息学院 计算机系数据结构基本运算如下：置空队 分配空间，头尾指针赋值，计数赋0 入队 顺序表插入，调整头尾指针 计数赋 出队 顺序表删除，调整头尾指针 计数赋 判队空 队列中数据数目为0。使用计数器的循环队列的类型定义：Java实现使用计数器的循环队列.txt29电气信息学院 计算机系数据结构结点接口结点接口Public interfa

26、ce Nodepublic Object getData();/获取结点数据域获取结点数据域Public void setData(Object object);/设置结点数据域设置结点数据域Public class SLNode implements Node private Object element;private SLNode next;public SLNode this(null,null);public SLNode(Object ele,SLnode next)this.element=ele;this.next=next;public SLNode getNext()ret

27、urn next;public void setNext(SLNode next)this.next=next;public Object getData()return element;public void setData(Object obj)element=obj;链队列v结点定义同SLNode的定义30电气信息学院 计算机系数据结构链队列头结点 .front队头队尾rear设队首、队尾指针front和rear,front指向头结点，rear指向队尾31电气信息学院 计算机系数据结构frontrearx入队xfrontreary入队xyfrontrearx出队xyfront rear空

28、队front reary出队32电气信息学院 计算机系数据结构讨论：讨论：空队列的特征？空队列的特征？Q(队尾队尾)(队首队首)fronta1a2a3rearpfrontrear 怎样实现入队和出队操作？怎样实现入队和出队操作？入队（入队（尾部插入尾部插入）：）：出队（出队（头部删除头部删除）：）：P74入队、出队入队、出队Java实现实现 队列会满吗？队列会满吗？front=rear一般不会，因为删除时有一般不会，因为删除时有free动作。除非内存不足！动作。除非内存不足！33电气信息学院 计算机系数据结构问：为什么要设计队列？它有什么独特用途？问：为什么要设计队列？它有什么独特用途？1.离散事件的模拟离散事件的模拟（模拟事件发生的先后顺序）（模拟事件发生的先后顺序）;2.实时监控系统实时监控系统（循环队列循环队列）3.操作系统中多道作业的处理操作系统中多道作业的处理（一个（一个CPU执行多个执行多个作业）；作业）；4.4.简化程序设计。简化程序设计。舞伴问题舞伴问题，迷宫的最短路径问迷宫的最短路径问题题答：只要是答：只要是存储和使用顺序相同存储和使用顺序相同，两端受限操作两端受限操作就就应该想到用队列这种数据结构。应该想到用队列这种数据结构。34