数据结构栈和队列B.pptx

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

1、第1页2.逻辑结构 与同线性表相同，仍为一对一关系。3.运算规则 只能在栈顶运算，且访问结点时依照后进先出后进先出 （LIFOLIFO）或先进后出或先进后出（FILOFILO）的原则。的原则。4.出栈顺序：1.定义 限定只能在表的一端进行插入和删除运算的 线性表（只能在栈顶操作）上次课内容回顾第1页/共34页第2页讨论：有无通用的判别原则？有。在可能的输出序列中，不存在这样的输入序列有。在可能的输出序列中，不存在这样的输入序列i i，j j，k k，能同时满足，能同时满足入栈入栈顺序顺序i i，j j，k k 和和 出栈出栈顺序顺序k k，i i，j j。例例4 4 一个栈的输入序列为一个栈的

2、输入序列为1234512345，若在入栈的过，若在入栈的过程中允许出栈，则可能得到的出栈序列程中允许出栈，则可能得到的出栈序列有多少种，有多少种，分别是什么分别是什么？第2页/共34页第3页例1：回文游戏 设计思路：用栈暂存回文例2：数制转换（十转N）设计思路：用栈暂存低位值例3：括号匹配的检验 设计思路：用栈暂存左括号例4：表达式求值 设计思路：用栈暂存运算符 简化程序设计问题简化程序设计问题第3页/共34页第4页v回文游戏：顺读与逆读字符串一样（不含空格）dadtop1.读入字符串2.压入栈3.原串字符与出栈字符依次比较 若不等，非回文 若直到栈空都相等，则是回文有没有更简洁的办法呢？(读

3、入字符串，压入n/2个字符,n为字符个数)v多进制输出：字符串：“madam I madam”“上海自来水来自海上”例 把十进制数159转换成八进制数(159)10=(237)815981982802 3 7 余 7余 3余 2toptop7top73top732第4页/共34页第5页v多进制输出：例 把十进制数159转换成八进制数(159)10=(237)815981982802 3 7 余 7余 3余 2toptop7top73top732public class Test public static void main(String args)int i=159;String binSt

4、r=Integer.toBinaryString(i);String otcStr=Integer.toOctalString(i);String hexStr=Integer.toHexString(i);System.out.println(binStr);第5页/共34页第6页v多进制输出：import java.util.*;class T public static void main(String args)System.out.println(toOctal(159);public static String toOctal(int a)String str=;Stack s=n

5、ew Stack();while(a!=0)s.push(a%8);a=a/8;while(!s.empty()str+=s.pop();return str;例 把十进制数159转换成八进制数第6页/共34页第7页例如：3*（7 2）(1)要正确求值，首先了解算术四则运算的规则：a.从左算到右 b.先乘除，后加减 c.先括号内，后括号外 由此，通常此表达式的计算顺序为：3*（7 2）=3*5=15v 表达式求值(这是栈应用的典型例子)这里，这里，表达式求值的算法是表达式求值的算法是 “算符优先法算符优先法”。第7页/共34页第8页表达式表示法 算术表达式中最常见的表示法形式有 中缀、前缀和

6、后缀表示法。中缀表示法是书写表达式的常见方式，而前缀和后缀表示法主要用于计算机科学领域。中缀表示法 Syntax:operand1 operator operand2Example:(A+B)*C-D/(E+F)前缀表示法-波兰表示法（Polish notation，PN）Syntax :operator operand1 operand2Example:-*+ABC/D+EF后缀表示法-逆波兰表示法（Reverse Polish Notation，RPN）Syntax :operand1 operand2 operatorExample:AB+C*DEF+/-无操作符优先级问题，求值简单第8

7、页/共34页第9页1.中缀表达式到后缀表达式的转换 要把表达式从中缀表达式的形式转换成用后缀表示法表示的等价表达式，必须了解操作符的优先级和结合性。优先级或者说操作符的强度决定求值顺序；优先级高的操作符比优先级低的操作符先求值。如果所有操作符优先级一样，那么求值顺序就取决于它们的 结合性。操作符的结合性定义了相同优先级操作符组合的顺序（从右至左或从左至右）。Left associativity :A+B+C=(A+B)+CRight associativity:ABC=A(BC)常用表达式求值方法1.中缀表达式转换成后缀表达式2.计算后缀表达式第9页/共34页第10页转换算法：1.读入运算对象

8、（数据），直接输出2.遇到(运算符进栈3.遇到)运算符，则栈内的最上一个(以上的所有运算符退栈，(也退栈4.读入运算符，进入运算栈 4.1 后进栈的运算符 先进栈的运算符，运算符进栈 (优先级比较)4.2 后进栈的运算符=先进栈的运算符，将栈内的运算符退栈输出，再进栈第10页/共34页第11页31*(5-22)+70第11页/共34页第12页后缀表达式求值 对后缀表达式求值比直接对中缀表达式求值简单。在后缀表达式中，不需要括号，而且操作符的优先级也不再起作用了。可以用如下算法对后缀表达式求值：初始化一个空堆栈 从左到右读入后缀表达式 如果字符是一个操作数，把它压入堆栈。如果字符是个操作符，弹出

9、两个操作数，执行操作，然后把结果压入堆栈。到后缀表达式末尾，从堆栈中弹出结果。若后缀表达式格式正确，那么堆栈应该为空。第12页/共34页第13页31*(5-22)+70参看Class1.java代码第13页/共34页第14页1.顺序栈的一般定义/堆栈接口public interface Stack public int getSize();public boolean isEmpty();public void push(Object e);public Object pop()throws StackEmptyException;public Object peek()throws Stac

10、kEmptyException;二.基本操作的程序实现第14页/共34页第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 isEmpty()return top=elements.length)expandSpac

11、e();elements+top=e;二.基本操作的程序实现第15页/共34页第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 StackEmptyException(“错误，堆栈空”);Object obj=elementstop;elementstop-=n

12、ull;return obj;public Object peek()throws StackEmptyException if(getSize()1)throw new StackEmptyException(“错误，堆栈空”);return elementstop;第16页/共34页第17页l入栈算法l 出栈算法 .栈底toptopxptop .栈底topq链栈基本操作P67 Stack的链式存储实现初始化、判断栈空、栈满、入栈、出栈、取栈顶元素、销毁。SLNode p=new SLNode(x,top);top=p;size+;栈非空，则Object obj=top.getData();

13、top=top.getNext();size-;第17页/共34页第18页补充1：若入栈动作使地址向高端增长，称为“向上生成”的栈；若入栈动作使地址向低端增长，称为“向下生成”的栈；top=0123450栈空 对于向上生成的栈对于向上生成的栈入栈入栈口诀：堆栈指针口诀：堆栈指针top先压后加先压后加（vtop+=xvtop+=x）；）；出栈出栈口诀：堆栈指针口诀：堆栈指针top先减后弹先减后弹（y=v-topy=v-top)。对于向下生成的栈对于向下生成的栈若约定若约定top指向栈顶元素的后一个位置指向栈顶元素的后一个位置入栈入栈口诀：堆栈指针口诀：堆栈指针top先压后减先压后减（vvtopt

14、op-=x=x）；）；出栈出栈口诀：堆栈指针口诀：堆栈指针top先加后弹先加后弹（y=vy=v+toptop)。top=6123450栈空第18页/共34页第19页第三章 栈和队列3.2 队（Queue）1.队的基本理论 定义、逻辑结构、存储结构、基本运算规则、队的应用2.基本操作的程序实现方法第19页/共34页第20页3.2 队列队列的定义及特点定义：队列是限定只能在表的一端进行插入，在表的另一端进行删除的线性表队尾(rear)允许插入的一端队头(front)允许删除的一端队列特点：先进先出(FIFO)a1 a2 a3.an 入队出队队头front队尾rear队列Q=(a1,a2,an)第2

15、0页/共34页第21页ADT Queue 数据对象数据对象：D=ai|aiElemSet,i=1,2,n,n0 数据关系数据关系：R1=|ai-1,ai D,i=2,n 基本操作基本操作：getSize();/返回队列大小，即元素个数 isEmpty();/对为空返回true,否则返回false enqueue(e);/数据元素e入对 dequeue();/对头元素出对 peek();/获取对头元素，但不出对/ADT Queue队的抽象数据类型定义第21页/共34页第22页队列的顺序存储结构实现：用一维数组实现sqMfront=-1rear=-1123450队空123450frontJ1,J1

16、,J3入队J1J2J3rearrear123450J4,J5,J6入队J4J5J6front设两个指针front,rear,约定：rear指示队尾元素；front指示队头元素前一位置初值front=rear=-1 空队列条件：front=rear入队列：sq+rear=x;出队列：x=sq+front;rearrearfrontrear123450J1,J2,J3出队J1J2J3frontfrontfront队列会满吗？这样操作有没有问题？第22页/共34页第23页存在问题设数组容量为M，则：当front=-1,rear=M-1时，再有元素入队发生溢出真溢出当front-1,rear=M-1时

17、，再有元素入队发生溢出假溢出0M-11frontrear.v解决方案l队首固定，每次出队剩余元素向下移动浪费时间l循环队列u基本思想：把队列设想成环形，让sq0接在sqM-1之后，若rear+1=M,则令rear=0;在顺序队中，当尾指针已经到了数组的上界，不能再有入队操作，在顺序队中，当尾指针已经到了数组的上界，不能再有入队操作，但其实数组中还有空位置，这就叫但其实数组中还有空位置，这就叫“假溢出假溢出”。u实现：利用“求模”运算u入队：rear=(rear+1)%M;sqrear=x;u出队：front=(front+1)%M;x=sqfront;u队满、队空判定条件？第23页/共34页第

18、24页012345rearfrontJ4J5J6012345rearfrontJ9J8J7J4J5J6012345rearfront初始状态J4,J5,J6出队J7,J8,J9入队队空：front=rear队满：front=rear真溢出假溢出第24页/共34页第25页解决方案有三：加设标志位，让删除动作使其为1,插入动作使其为0,则可识别当前front=rear人为浪费一个单元，令队满特征为队满特征为front=(rear+1)%N；使用一个计数器记录队列中元素个数（即队列长度）；选用空闲单元法：空闲单元法：即即front和和rear之一指向实元素，另一指向之一指向实元素，另一指向空闲元素。

19、空闲元素。队空条件:front=rear (初始化时：front=rear)队满条件：front=(rear+1)%N (N=maxsize)队列长度：L=（Nrearfront）%N rearJ2 J3J1 J4 J5front问2：在具有n个单元的循环队列中，队满时共有多少个元素？问1：左图中队列长度L=？左图中队列容量maxsize N=？n-156第25页/共34页第26页J2 J3J1 J4 J5rearfrontfrontfrontfrontJ6 J5J7J8 J9例1：一循环队列如下图所示，若先删除4个元素，接着再插入4个元素，请问队头和队尾指针分别指向哪个位置?front解：由

20、图可知，队头和队尾指针的初态分别为front=1和rear=6。frontrear删除4个元素后front=5；再插入4个元素后，r=(6+4)%6=4 frontu入队：rear=(rear+1)%M;u出队：front=(front+1)%M;第26页/共34页第27页例2：数组数组nn用来表示一个循环队列，用来表示一个循环队列，f f 为当前队为当前队列头元素的列头元素的前一前一位置，位置，r r 为队尾元素的位置。假定队列为队尾元素的位置。假定队列中元素的个数小于中元素的个数小于n n，计算队列中元素的公式为，计算队列中元素的公式为:（）rf （）（nfr）%n （）nrf （）（nr

21、f）%n4种公式哪种合理？当 r f 时（A）合理；当 r f 时（C）合理；分析：综合2种情况，以（D）的表达最为合理例3：在一个循环队列中，若约定队首指针指向队首元素的前一个位置。那么，从循环队列中删除一个元素时，其操作是 先 ，后 。移动队首指针取出元素rear123450J4,J5,J6入队J4J5J6front第27页/共34页第28页基本运算如下：置空队 分配空间，头尾指针赋值，计数赋0 入队 顺序表插入，调整头尾指针 计数赋 出队 顺序表删除，调整头尾指针 计数赋 判队空 队列中数据数目为0。使用计数器的循环队列的类型定义：Java实现使用计数器的循环队列.txt第28页/共34

22、页第29页结点接口Public interface 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 get

23、Next()return next;public void setNext(SLNode next)this.next=next;public Object getData()return element;public void setData(Object obj)element=obj;链队列结点定义同SLNode的定义第29页/共34页第30页链队列头结点 .front队头队尾rear设队首、队尾指针front和rear,front指向头结点，rear指向队尾第30页/共34页第31页frontrearx入队xfrontreary入队xyfrontrearx出队xyfront rear空

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