栈与队列(java版).ppt

《栈与队列(java版).ppt》由会员分享，可在线阅读，更多相关《栈与队列(java版).ppt（115页珍藏版）》请在三一办公上搜索。

1、第三章 栈与队列,教学内容,3.2 队列,3.1 栈,3.4 栈与队列的综合应用举例,3.3 栈与队列的比较,教学重点与难点,重点：,栈、队列的特点；栈、队列基本操作的实现算法,难点：,栈、队列的应用,通常称，栈和队列是限定插入和删除只能在表的“端点”进行的线性表。,线性表 栈 队列 Insert(i,x)Insert(n,x)Insert(n,x)0in Delete(i)Delete(n-1)Delete(0)0in-1,栈和队列是两种操作受限的线性表，是两种常用的数据类型。,3.1.1 栈的概念,(1)栈是仅限制在表尾进行插入和删除操作的特 殊线性表，限制操作的表尾端称为“栈顶”,另一

2、端称为“栈底”,(2)栈是“后进先出”的线性表（LIFO）或“先 进后出”的线性表（FILO）,3.1.1 栈的概念,如下图所示的是铁路调度站形象地表示栈的“后进先出”特点。,3.1.1 栈的概念,思考题：,设有编号为1，2，3，4的四辆列车，顺序进一个栈式结构的站台，具体写出这四辆列车开出车站的所有可能的顺序。,3.1.1 栈的概念,解答：,四辆车出站的所有可能顺序为：,6）2、1、3、4；7）2、1、4、3；8）2、3、4、1；9）2、3、1、4；10）2、4、3、1；,14）4、3、2、1。,1）1、2、3、4；2）1、2、4、3；3）1、3、2、4；4）1、3、4、2；5）1、4、3、

3、2；,11）3、2、1、4；12）3、2、4、1；13）3、4、2、1；,3.1.2 栈的抽象数据类型描述,clear(),1）栈的置空操作：,isEmpty(),2）栈的判空操作：,length(),3）求栈的长度：,4）取栈顶元素操作：,5）入栈操作：,peek(),push(x),6）出栈操作：,pop(),1.基本操作,3.1.2 栈的抽象数据类型描述,2.栈的抽象数据类型的Java接口描述,public interface IStack,public void clear();public boolean isEmpty();public int length();public Ob

4、ject peek();public void push(Object x)throws Exception;public Object pop();,实现此接口的方法有两种:,顺序栈,链栈,3.1.3 顺序栈及其基本操作的实现,1.顺序栈,非空栈,空栈,3.1.3 顺序栈及其基本操作的实现,1.顺序栈,思考,栈空条件?,栈满条件?,栈的长度?,栈顶元素?,如下问题如何描述?,top=0,top=stackElem.length,top,stackElemtop-1,3.1.3 顺序栈及其基本操作的实现,2.顺序栈类的描述(书P71-与P33顺序表类对照学习),public class SqS

5、tack implements IStack private Object stackElem;private int top;,/构造一个容量为maxSize的空栈 public SqStack(int maxSize),/栈置空 public void clear(),stackElem=new ObjectmaxSize;,top=0;,top=0;,2.顺序栈类的描述(见教材P71),public class SqStack implements IStack,/栈判空public boolean isEmpty(),/求栈数据元素个数函数 public int length(),/取

6、栈顶元素的函数 public Object peek(),return top=0;,return top;,if(!isEmpty()/栈非空return stackElemtop-1;/栈顶元素 elsereturn null;,2.顺序栈类的描述(见教材P71),public class SqStack implements IStack,/入栈操作的函数public void push(Object x),/出栈操作的函数public void pop(),/输出函数(从栈顶到栈底)public void display(),for(int i=top-1;i=0;i-),System

7、.out.print(stackElemi.toString()+);,3.顺序栈基本操作的实现,1)顺序栈的入栈操作 push(x)的实现（算法 3.1),(1)操作要求：插入元素x使其成为顺序栈中新的栈顶元素。,x,a.判断顺序栈是否为满，若满则抛出异常 b.若栈不满，则将新元素x 压入栈顶，并修正栈顶指针,(2)算法步骤：,if(top=stackElem.length)throw new Exception(栈已满),1)顺序栈的入栈操作 push(x)的实现（算法 3.1),(3)算法,public void push(Object x)throws Exception/算法3.1结

8、束,if(top=stackElem.length)throw new Exception(栈已满);else stackElemtop+=x;,1)顺序栈的入栈操作 push(x)的实现（算法 3.1),时间复杂度为：O(1),3.顺序栈基本操作的实现,2)顺序栈的出栈操作 pop()的实现（算法 3.2),(1)操作要求：将栈顶元素从栈中移去，并返回被移去的栈顶元素值。,a0,a1,an-1,an-2,(2)算法步骤：,2)顺序栈的出栈操作 pop()的实现（算法 3.2),a）若栈空，则返回空值,b)若栈不空，则移去栈顶元素并返回其值,if(top=0)return null;,a1,a

9、2,an,an-1,或 if(isEmpty()return null;,return stackElemtop;,return stackElem-top;,top=top-1;,(3)算法,public Object pop()throws Exception/算法3.2结束,if(isEmpty()return null;elsereturn stackElem-top;,2)顺序栈的出栈操作 pop()的实现（算法 3.2),时间复杂度为：O(1),3.1.4 链栈及其基本操作的实现,1.链栈,栈的链式存储结构称为链栈，是运算受限的单链表，其插入和删除操作仅限制在链表的表头位置上进行，

10、故链栈没有必要象单链表一样附加头结点，栈顶指针即为链表的头指针。,3.1.4 链栈及其基本操作的实现,1.链栈,思考,栈空条件?,栈的长度?,栈顶元素?,如下问题如何描述?,top=null,需从栈顶开始沿着next指针依次对结点逐个进行点数才能确定。,top.getData(),3.1.4 链栈及其基本操作的实现,2.链栈类的描述(书中P73-74),Import cho2.Node;public class LinkStack implements IStack private Node top;,/栈置空函数 public void clear(),/判空函数public boolean

11、 isEmpty(),top=null;,return top=null;,2.链栈类的描述(书中P73-74),public class LinkStack implements IStack,/求栈数据元素个数函数 public int length(),/取栈顶元素的函数 public Object peek(),if(!isEmpty()/栈非空 return top.getData();/栈顶元素else return null;,2.链栈类的描述(书中P73-74),public class LinkStack implements IStack,/入栈操作的函数public vo

12、id push(Object x),/出栈操作的函数public void pop(),/输出函数(从栈顶到栈底)public void display(),Node p=top;,System.out.print(p.getData().tostring()+),p=p.getNext();,while(p!=null),0,3.链栈基本操作的实现,1)求链栈的长度操作 length()的实现,(1)操作要求：计算出链栈中所包含的数据元素的个数并返回其值。,(2)方法 与求单链表长度的方法相同。,length,1,2,3,4,5,6,(3)算法,public int length()/算法3

13、.3结束,Node p=top;int length=0;,时间复杂度为：O(n),1)求链栈的长度操作 length()的实现(算法 3.3),while(p!=null)p=p.getNext();+length;,3.链栈基本操作的实现,2)链栈的入栈操作 push(x)的实现（算法 3.4),(1)操作要求：将数据域值为x的新结点插入到链栈的栈顶，使其成为新的栈顶元素。,top,Node p=new Node(x);,p.setNext(top);,top=p;,(2)算法,public void push(object x)/算法3.4结束,Node p=new Node(x);,2

14、)链栈的入栈操作 push(x)的实现（算法 3.4),时间复杂度为：O(1),p.setNext(top);,top=p;,3.链栈基本操作的实现,3)链栈的出栈操作 pop()的实现（算法 3.5),(1)操作要求：将首结点（或栈顶结点）从链栈中移去，并返回该结点的数据域的值。,Node p=top;,top=top.getNext(),return(p.getData();,top,(2)算法,public Object pop()/算法3.5结束,3)链栈的出栈操作 pop()的实现（算法 3.5),时间复杂度为：O(1),Node p=top;,top=top.getNext(),r

15、eturn(p.getData();,if(isEmpty()return null;else,3.1.5 栈的应用,例1.分隔符匹配问题,例2.大数加法问题,例3.表达式求值问题,例4.栈与递归问题,【例1】分隔符匹配问题-问题分析,假设在表达式中（）或（/*/）等为正确的格式，（）或（）)或（）均为不正确的格式。,则 检验分隔符是否匹配的方法可用“期待的急迫程度”这个概念来描述。,Java程序中分隔符有圆、方、花括号和注释符“/*”和“*/”。,分析可能出现的不匹配的情况:,到来的右分隔符并非是所“期待”的；,例如：考虑下列括号序列：（）或（）)或（）1 2 3 4 1 2 3 4 5 6

16、 1 2 3 4 5,到来的是“不速之客”；,直到结束，也没有到来所“期待”的括弧。,【例1】分隔符匹配问题-问题分析,【例1】分隔符匹配问题-问题分析,这三种情况对应到栈的操作即为：1和栈顶的左分隔符不相匹配；2栈中并没有左分隔符等在那里；3栈中还有左分隔符没有等到和它相匹配的右括弧。,算法的设计思想：,1）凡出现左括弧，则进栈；,2）凡出现右括弧，首先检查栈是否空 若栈空，则表明该“右括弧”多余，否则和栈顶元素比较，若相匹配，则“左括弧出栈”，否则表明不匹配。,3）表达式检验结束时，若栈空，则表明表达式中匹配正确，否则表明“左括弧”有余。,【例1】分隔符匹配问题-问题分析,【例1】分隔符匹

17、配问题-程序代码（P77-78）,public class Example3_1,private final int LEFT=0;/记录左分隔符private final int RIGHT=1;/记录右分隔符private final int OTHER=2;/记录其他字符,Import;,public int verifyFlag(String str)if(.equals(str)|.equals(str)|.equals(str)|/*.equals(str)/左分隔符 return LEFT;else if().equals(str)|.equals(str)|.equals(st

18、r)|*/.equals(str)/右分隔符 return RIGHT;else/其它的字符 return OTHER;,public class Example3_1,/检验左分隔符str1和右分隔符str2是否匹配public boolean matches(String str1,String str2)if(.equals(str1),【例1】分隔符匹配问题-程序代码（P77-78）,public class Example3_1,/检验串中分隔符是否匹配private boolean isLegal(String str)throws Exception,if(!.equals(st

19、r)if(i!=length)if(/=c&*=str.charAt(i+1)|(*=c&/=str.charAt(i+1),t=t.concat(String.valueOf(str.charAt(i+1);+i;/跳过一个字符,【例1】分隔符匹配问题-程序代码（P77-78）,public class Example3_1,/检验串中分隔符是否匹配private boolean isLegal(String str)throws Exception,if(LEFT=verifyFlag(t)S.push(t);/压栈else if(RIGHT=verifyFlag(t)if(S.isEmp

20、ty()|!matches(S.pop().toString(),t)throw new Exception(错误：Java语句不合法！);,if(!S.isEmpty）throw new Exception(错误：Java语句不合法！);/抛出异常return true;,else throw new Exception(错误：Java语句为空！);/抛出异常,【例1】分隔符匹配问题-程序代码（P77-78）,public class Example3_1,/主函数public static void main(String args)throws Exception,Example3_1

21、e=new Example3_1();(请输入分Java语句：);Scanner sc=new Scanner(System.in);if(e.isLegal(sc.nextLine()System.out.println(Java语句合法!);else(“错误：Java语句不合法！);,【例1】分隔符匹配问题-程序代码（P77-78）,【例2】大数加法问题问题分析,何谓大数:,所谓大数是指超过整数最大上限的数,处理方法,将两个加数看成是数字字符串，将这些数的相应数字存储在两个堆栈中，并从两个栈中弹出对应位的数字依次执行加法却可得到结果。,【例2】大数加法问题操作步骤,2.若两个加数栈都非空，

22、则依次从栈中弹出栈顶数字相加，和存入变量partialSum中；若和有进位，则将和的个位数压入结果栈sum中，并将进位数加到下一位数字相加的和中；若和没有进位，则直接将和压入结果栈sum中；,1.将两个加数的相应位从高位到低位依次压入栈sA和sB中。,4.若两个加数栈都为空，则栈sum中保存的就是计算结果。注意栈顶是结果中的最高位数字。,【例2】大数加法问题操作步骤,3.若某个加数堆栈为空，则将非空加数栈中的栈顶数字依次弹出与进位相加，和的个位数压入结果栈sum中，直到此该栈为空为止。若最高位有进位，则最后将1压入栈sum中。,【例2】大数加法问题-（书P79图3.10),【例2】大数加法问题

23、程序代码,Example3_2.java,(书P79-80),【例3】表达式求值问题分析,限于二元运算符的表达式定义:表达式:=(操作数)+(运算符)+(操作数)操作数:=简单变量|表达式 简单变量:=标识符|无符号整数,【例3】表达式求值问题分析,在计算机中,表达式的3种标识方法：,设 Exp=S1+OP+S2,则称 OP+S1+S2 为前缀表示法,S1+OP+S2 为中缀表示法,S1+S2+OP 为后缀表示法,【例3】表达式求值问题分析,例如:Exp=a b+(c d/e)f前缀式:+a b c/d e f中缀式:a b+c d/e f后缀式:a b c d e/f+,结论:,1）操作数之

24、间的相对次序不变;,2）运算符的相对次序不同;,3）中缀式丢失了括弧信息，致使运算的次序不确定;,4)前缀式的运算规则为:连续出现的两个操作数和在它们之前且紧靠它们的运算符构成一个最小表达式;,5)后缀式的运算规则为:运算符在式中出现的顺序恰为 达式的运算顺序;每个运算符和在它之前出现 且紧靠它的两个操作数构成一个最小表达式。,【例3】表达式求值问题分析,每个运算符的运算次序要由它之后的一个运算符来定;在后缀式中，优先数高的运算符领先于优先数低的运算符。,分析:“原表达式”和“后缀式”中的 运算符:原表达式:a+b c d/e f 后缀式:a b c+d e/f,1.如何从原表达式求得后缀式？

25、,【例3】表达式求值问题分析,为此我们先引进一个运算符的“优先级”的概念。给每个运算符赋以一个优先级的数值，如下表所示：,【例3】表达式求值问题分析,1)设立一个运算符栈；,2)若当前字符是操作数，则直接发送给后缀 式;,3)若当前字符为运算符时，若运算符 栈为空或运算符栈非空且其优先数高于栈顶运算符，则进栈；否则，退出栈顶运算符发送给后缀式；,从原表达式求得后缀式的操作步骤为：,4)若当前字符是左括号“（”时，将其压进 运算符栈;,【例3】表达式求值问题分析,5)若当前字符是右括号“）”时，反复 将 栈顶符号弹出，并送往后缀表达式，直到栈顶符号是左括号为止，再将左 括号出栈并丢弃。,6)若读

26、取完毕，则将栈中剩余的所有运 算符弹出并送往后缀表达式。,【例3】表达式求值问题分析,如：3*（7-2）转换成后缀表达式372-*的过程为：,步骤 后缀表达式 运算符栈 原表达式 说明 1 3*（7-2）2 3*(7-2*#3*(7-2)4*(7-2)5 37*(-2)-(6 37*(-2)7 372*(-)遇）8 372-*()遇(9 372-*10 372-*结束,动画3-3-7,【例3】表达式求值问题分析,2.如何从后缀式求值？,先找运算符，再找操作数,例如：a b c d e/f+,ab,d/e,c-d/e,(c-d/e)f,动画3-3-6,a b+(c-d/e)f,【例3】表达式求值

27、问题分析,1)设立一个操作数栈；,2)从左到右依次读入后缀表达式中的字符:,若当前字符是操作数，则压入操作数栈。,后缀式求值的操作步骤为：,若当前字符是运算符，则从栈顶弹出两个操作数参与运算，并将运算结果压入操作数栈内。,动画3-3-6,【例3】表达式求值程序代码,Example3_3.java,(书P84-85),【例4】栈与递归问题,在程序设计中，经常会碰到多个函数的嵌套调用。和汇编程序设计中主程序和子程序之间的链接和信息交换相类似，在高级语言编制的程序中，调用函数和被调用函数之间的链接和信息交换也是由编译程序通过栈来实施的。,【例4】栈与递归问题,1.将所有的实在参数、返回地址等信息传递

28、给被调用函数保存；2.为被调用函数的局部变量分配存储区；3.将控制转移到被调用函数的入口。,当在一个函数的运行期间调用另一个函数时，在运行该被调用函数之前，需先完成三项任务：,【例4】栈与递归问题,1.保存被调函数的计算结果；2.释放被调函数的数据区；3.依照被调函数保存的返回地址将控制转移到调用函数。,从被调用函数返回调用函数之前，应该完成下列三项任务：,【例4】栈与递归问题,多个函数嵌套调用的规则是：,此时的内存管理实行“栈式管理”,后调用先返回！,例如：void main()void a()void b()a();b();/main/a/b,函数a的数据区,函数b的数据区,Main的数据

29、区,【例4】栈与递归问题,递归工作栈：递归过程执行过程中占用的 数据区。递归工作记录：每一层的递归参数合成 一个记录。当前活动记录：栈顶记录指示当前层的 执行情况。当前环境指针：递归工作栈的栈顶指针。,递归函数执行的过程可视为同一函数进行嵌套调用，例如：,【例4】栈与递归问题汉诺塔问题描述,n阶汉诺塔问题：假设有三个分别命名为X，Y和Z的塔座，在塔座X上插有n个直径大小各不相同，且从小到大编号为1、2、n的圆盘。现要求将塔座X上的n个圆盘借助塔座Y移至塔座Z上，并仍按同样顺序叠排。圆盘移动时必须遵循下列规则：每次只能移动一个圆盘；圆盘可以插在X，Y和Z中的任何一个塔座上；任何时刻都不能将一个较

30、大的圆盘压在较小的圆盘之上。,【例4】栈与递归问题汉诺塔问题,public void hanoi(int n,char x,char y,char z)/将塔座x上按直径由小到大且至上而下编号为1至n的n个圆盘按规则搬到塔座z上，y可用作辅助塔座。1 2 if(n=1)3 move(x,1,z);/将编号为的圆盘从x移到z4 else 5 hanoi(n-1,x,z,y);/将x上编号为至n-1的/圆盘移到y,z作辅助塔6 move(x,n,z);/将编号为n的圆盘从x移到z7 hanoi(n-1,y,x,z);/将y上编号为至n-1的/圆盘移到z,x作辅助塔8 9,【例4】栈与递归问题汉诺塔

31、问题,public void hanoi(int n,char x,char y,char z)1 2 if(n=1)3 move(x,1,z);4 else 5 hanoi(n-1,x,z,y);6 move(x,n,z);7 hanoi(n-1,y,x,z);8 9,【例4】汉诺塔问题程序代码,Example3_4.java,(书P86-87),3.2.1 队列的概念,(1)队列是只允许在表的一端进行插入，而在表 的另一端进行删除操作的一种特殊线性表。允许插入的一端称为“队尾”，允许删除的一 端称为“队首”。,(2)栈是“先进先出”的线性表（FIFO）或“后进后出”的线性表（LILO）,a

32、0 a1 a2 an-1,队首,队尾,入队,出队,3.2.2 队列的抽象数据类型描述,clear(),1）队列的置空操作：,isEmpty(),2）队列的判空操作：,length(),3）求队列的长度：,4）取队首元素操作：,5）入队操作：,peek(),offer(x),6）出队操作：,poll(),1.基本操作,3.1.2 栈的抽象数据类型描述,2.队列的抽象数据类型的Java接口描述,public interface IQueue,public void clear();public boolean isEmpty();public int length();public Object

33、peek();public void offer(Object x)throws Exception;public Object popll();,实现此接口的方法有两种:,顺序队列,链式队列,3.2.3 顺序队列及其基本操作的实现,1.顺序队列,非空队列,空队列,3.1.3 顺序栈及其基本操作的实现,1.顺序队列,思考,队空条件?,队列满条件?,如下问题如何描述?,front=rear,rear=queueElem.length,入队offer(x):queueElemrear+=x;出队poll():return queueElem front+;,队首元素?,queueElemfront

34、,队尾元素?,queueElemrear-1,3.2.3 顺序栈及其基本操作的实现,1.顺序队列,序号值：0 1 2 3 4 5,a0,a1,a3,a3,a4,假溢出现象,maxSize=6,a5,front,front,front,front,front,rear,rear,3.2.3 顺序栈及其基本操作的实现,2.循环顺序队列,将顺序队列看成是首尾相联的队列。,动画3-3-13,3.2.3 顺序栈及其基本操作的实现,2.循环顺序队列,假设：maxSize=6,循环队空条件：循环队满条件：,front=rear,front=rear,队空与队满的条件相同,无法判断,怎么办？,0,5,4,3,

35、2,1,a0,a1,a2,a3,a4,a5,3.2.3 顺序栈及其基本操作的实现,2.循环顺序队列,1.设一个标志变量flag并置初值为0,每当入队操作成功后就置flag=1；每当出队操作成功后就置flag=0。,解决方法有3种：,循环队空条件：循环队满条件：,front=rear&flag=0,front=rear&flag=1,3.2.3 顺序栈及其基本操作的实现,2.循环顺序队列,2.设置一个计数变量num并置初值为0,每当入队操作成功后num加1；每当出队操作成功后num减1。,解决方法有3种：,循环队空条件：循环队满条件：,num=0或front=rear&num=0,num=que

36、ueElem.length或front=rear&num0,3.2.3 顺序栈及其基本操作的实现,2.循环顺序队列,3.少用一个元素空间：如下图,循环队空条件：循环队满条件：,front=rear,（rear+1）%queueElem.length=front,0,5,4,3,2,1,a1,a2,a3,a4,a5,空,解决方法有3种：,3.2.3 顺序栈及其基本操作的实现,3.循环顺序队列类的描述(书中P91),public class CircleSqQueue implements IQueue private Object queueElem;private int front;priv

37、ate int rear;,/构造一个容量为maxSize的空循环队列函数 public CircleSqQueue(int maxSize),/队列置空函数 public void clear(),queueElem=new ObjectmaxSize;,front=rear=0;,front=rear=0;,3.循环顺序队列类的描述(见书P91),public class CircleSqQueue implements IQueue,public boolean isEmpty()/判空函数,public int length()/求队列当前长度函数,public Object peek

38、()/读取队首元素的函数,return front=rear;,return(rear-front+queueElem.length)%queueElem.length);,if(front=rear)/队列为空else,return null;,return queueElemfront;/返回队首元素,public class CircleSqQueue implements IQueue/循环顺序队列类的描述结束,/入队操作的函数public void offer(Object x),/出队操作的函数public void poll(),/输出函数(从队首到队尾)public void

39、display(),3.循环顺序队列类的描述(见书P91),if(!isEmpty()else,for(int i=front;i!=rear;i=(i+1)%queueElem.length)System.out.print(queueElemi.toString()+);,(此队列为空);,4.循环顺序队列基本操作的实现,1)循环顺序队列的入队操作 offer(x)的实现（算法 3.6),将新元素x插入到一个循环队列的队尾。,操作思路：,基本要求：,x,1）若队满，则抛出异常后结束操作；,2）若队非满，则将x进队，尾指针加1,queueElemrear=x;/x入队,操作步骤：,if(re

40、ar+1)%queueElem.length=front)throw new Exception(队列已满);,4.循环顺序队列基本操作的实现,1)循环顺序队列的入队操作 offer(x)的实现（算法 3.6),rear=(rear+1)%queueElem.length;,public void offer(Object x)throws Exception/算法3.6结束,if(rear+1)%queueElem.length=front)throw new Exception(“队列已满);else queueElemrear=x;rear=(rear+1)%queueElem.leng

41、th;,时间复杂度为：O(1),算法：,4.循环顺序队列基本操作的实现,1)循环顺序队列的入队操作 offer(x)的实现（算法 3.6),2)循环顺序队列的出队操作poll()的实现（算法 3.7),4.循环顺序队列基本操作的实现,基本要求：,操作思路：,将队首元素删除，并返回其值。,a5,1）若队空，则返回空值；,2）若队非空，则返回队首元素且首指针加1,Object t=queueElemfront/读取队首元素,操作步骤：,if(front=rear)return null;,4.循环顺序队列基本操作的实现,front=(front+1)%queueElem.length;,2)循环顺

42、序队列的出队操作poll()的实现（算法 3.7),return t;,public Object poll()/算法3.7结束,if(front=rear)return null;else Object t=queueElemfront;front=(front+1)%queueElem.length;return t;,时间复杂度为：O(1),算法：,4.循环顺序队列基本操作的实现,2)循环顺序队列的出队操作poll()的实现（算法 3.7),3.2.4 链队列及其基本操作的实现,1.链队列,队列的链式存储结构称为链队列，其链式存储结构在此用不带头结点的单链表来实现.,front,3.2.

43、4 链队列及其基本操作的实现,1.链队列,思考,队列空的条件?,队列的长度?,队首元素?,如下问题如何描述?,front=null,需从队首开始沿着next指针依次对结点逐个进行点数才能确定。,front.getData(),队尾元素?,rear.getData(),3.2.4 链队列及其基本操作的实现,2.链队列类的描述(书中P93-94),import cho2.Node;public class LinkQueue implements IQueue private Node front;private Node rear;,/队列置空函数 public void clear(),/判空

44、函数public boolean isEmpty(),front=rear=null;,return front=null;,public class LinkQueue implements IQueue,/求队列长度函数public int length(),2.链队列类的描述(书中P93-94),Node p=front;int length=0;,while(p!=null)p=p.getNext();/指针下移+length;/计数器加1,return length;,public class LinkQueue implements IQueue,/取队首元素的函数 public

45、Object peek(),2.链队列类的描述(书中P93-94),if(!isEmpty()/队列非空 else,return front.getData();/返回队首元素,return null;,public class LinkQueue implements IQueue,/入队操作的函数public void push(Object x),/出队操作的函数public void pop(),/输出函数(从队首到队尾)public void display(),2.链队列类的描述(书中P93-94),Node p=front;while(p!=null),System.out.pr

46、int(p.getData().tostring()+),p=p.getNext();,3.链队列基本操作的实现,1)链队列的入队操作 offer(x)的实现（算法 3.8),操作要求：插入新元素x使其成为新的队尾元素。,18,56,front,Node p=new Node(x);,rear.setNext(p);,rear=p;,(2)操作步骤：,a）产生新的结点p,b）将新结点插入链队的尾部（修改链）,队非空时:,队空时:,front=rear=p;,(3)算法,public void offer(object x)/算法3.8结束,Node p=new Node(x);if(front

47、!=null)/队列非空 rear.setNext(p);rear=p;else front=rear=p;,时间复杂度为：O(1),3.链队列基本操作的实现,1)链队列的入队操作 offer(x)的实现（算法 3.8),3.链队列基本操作的实现,2)链队列的出队操作 poll()的实现,操作要求：移去队首元素并返回其值,18,56,front,if(front=null)return null;,Node p=front;,front=front.getNext();,(2)操作步骤：,a）若队列为空,则返回空值,b）若队列非空,则移去队首元素,3.链队列基本操作的实现,2)链队列的出队操作

48、 poll()的实现,操作要求：移去队首元素并返回其值,18,56,front,(2)操作步骤：,c)若删除的是队尾元素，则修改队尾指针,if(rear=p)rear=null;,d)返回队尾元素值,return p.getData();,(3)算法,public Objext poll(),Node p=new Node(x);if(front!=null)/队列非空 Node p=front;front=front.getNext();if(rear=p)rear=null;return p.getData();else return null;,时间复杂度为：O(1),3.链队列基本操作

49、的实现,2)链队列的出队操作 poll()的实现,【例】编程实现求解的素数环问题,3.2.5 队列的应用,【问题描述】将1n的 n个自然数排列成环形，使得每相邻两数之和为素数，从而构成一个素数环。,【方法】,先引入顺序表类Sqlist和链队列类LinkQueue，再创建Sqlist类的一个对象L作为顺序表，用于存放素数环的数据元素；创建LinkQueue类的一个对象Q，作为队列用于存放还未加入到素数环中的自然数。,【例】编程实现求解的素数环问题,3.2.5 队列的应用,【问题描述】将1n的 n个自然数排列成环形，使得每相邻两数之和为素数，从而构成一个素数环。,【方法】,(2)初始化顺序表L和队

50、列Q:将1加入到顺序表L中，将2n的自然数全部加入到Q队列中。,【例】编程实现求解的素数环问题,3.2.5 队列的应用,【问题描述】将1n的 n个自然数排列成环形，使得每相邻两数之和为素数，从而构成一个素数环。,【方法】,(3)将出队的队首元素p与素数环最后一个数据元素q相加。,(a)若两数之和是素数并且p 不是队列中的最后一个数据元素（或队尾元素），则将p加入到素数环中；否则说明p暂时无法处理，必须再次入队等待，再重复此过程。,【例】编程实现求解的素数环问题,3.2.5 队列的应用,【问题描述】将1n的 n个自然数排列成环形，使得每相邻两数之和为素数，从而构成一个素数环。,【方法】,(3)将