第04章--栈和队列(Java版).ppt

《第04章--栈和队列(Java版).ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第4章栈和队列4.1栈4.2队列4.3优先队列4.4递归算法《数据结构（Java版）（第3版）》目的和要求目的：使用栈或队列作为求解复杂应用问题的有效手段和措施。内容：栈和队列抽象数据类型及它们的实现和应用；优先队列；递归算法设计。要求：掌握栈和队列抽象数据类型，以及顺序和链式存储结构实现；理解对于怎样的应用问题，需要使用栈或队列，以及怎样使用。重点：栈和队列的设计和实现；理解递归定义，设计递归算法。难点：使用栈或队列求解复杂应用问题；递归算法设计。实验：栈和队列及其应用；递归算法。《数据结构（Java版）（第3版）》4.1栈4.1.1栈抽象数据

2、类型4.1.2顺序栈4.1.3链式栈4.1.4栈的应用《数据结构（Java版）（第3版）》4.1.1栈抽象数据类型栈（stack）是一种特殊的线性表，其插入和删除操作只允许在线性表的一端进行。publicinterfaceSStack{//栈接口，栈抽象数据类型booleanisEmpty();//判断是否空栈voidpush(Tx);//元素x入栈Tpop();//出栈，返回当前栈顶元素Tget();//取栈顶元素，未出栈}《数据结构（Java版）（第3版）》4.1.2顺序栈publicclassSeqStackimplements

3、SStack//顺序栈类，实现栈接口{Objectelement[];//存储栈数据元素的数组inttop;//栈顶元素下标}《数据结构（Java版）（第3版）》4.1.3链式栈publicclassLinkedStackimplementsSStack{privateNodetop;}《数据结构（Java版）（第3版）》4.1.4栈的应用栈是嵌套调用机制的实现基础使用栈以非递归方式实现递归算法《数据结构（Java版）（第3版）》例4.1判断表达式中圆括号是否匹配《数据结构（Java版）（第3版）》例4.2使用栈计算表达式

4、的值。中缀表达式1+2*(3-4)+5《数据结构（Java版）（第3版）》（1）将中缀表达式转换为后缀表达式《数据结构（Java版）（第3版）》（2）后缀表达式求值《数据结构（Java版）（第3版）》4.2队列4.2.1队列抽象数据类型4.2.2顺序队列4.2.3链式队列4.2.4队列的应用《数据结构（Java版）（第3版）》4.2.1队列抽象数据类型队列（queue）是一种特殊的线性表，其插入和删除操作分别在线性表的两端进行。publicinterfaceQQueue//队列接口{booleanisEmpty();//判断队列是否为空vo

5、idenqueue(Tx);//入队Tdequeue();//出队}《数据结构（Java版）（第3版）》4.2.2顺序队列顺序队列，假溢出《数据结构（Java版）（第3版）》2.顺序循环队列front=(front+1)%length;rear=(rear+1)%length;《数据结构（Java版）（第3版）》3.顺序循环队列类publicclassSeqQueueimplementsQQueue{privateObjectvalue[];privateintfront,rear;//队列头尾下标}《数据结构（Java版）（第3版）

6、》4.2.3链式队列publicclassLinkedQueueimplementsQQueue//链式队列类{privateNodefront,rear;}《数据结构（Java版）（第3版）》4.2.4队列的应用例4.3求解素数环问题。《数据结构（Java版）（第3版）》4.3优先队列优先队列及其存储结构优先队列类publicclassPriorityQueue>implementsQQueue例4.4进程按优先级调度管理。《数据结构（Java版）（第3版）》递归定义递归算法f

7、(n)=n×f(n-1)【例4.5】求n！。4.4递归算法《数据结构（Java版）（第3版）》【例4.6】求Fibonacci序列。《数据结构（Java版）（第3版）》例4.7打印数字塔publicstaticvoidline(inti){if(i<10)line(i+1);System.out.print(String.format("%3d",i));}执行line(1)输出10987654321《数据结构（Java版）（第3版）》3.单链表的递归算法publicStringtoString(){return"("+this.toString

8、(this.head)+")";}publicStringtoString(Nodep)//递归算法{if(p==null)ret