栈和队列(Java版).ppt

第4章 栈和队列,4.1 栈4.2 队列4.3 递归目的：使用栈或队列求解应用问题。要求：栈和队列的顺序和链式存储结构实现。重点：栈和队列的设计和应用。难点：栈或队列的使用场合，以及如何使用 栈和队列求解应用问题。,4.1 栈,4.1.1 栈抽象数据类型 栈（stack）是一种线性表，插入和删除操作只允许在线性表的一端进行。先进后出。,图4.1 栈（顺序栈）及其状态变化,A,B,C,D 入栈,入栈,出栈,入栈,入栈,出栈,出栈,出栈,【思考题4-1】入栈A,B,C,D，出栈A,B,C,D、D,C,B,A？还有哪些？有哪些不可能的出栈序列？为什么？,栈抽象数据类型ADT，栈接口,public interface Stack public abstract boolean isEmpty();/判空 public abstract void push(T x);/x入栈 public abstract T peek();/返回栈顶，未出栈 public abstract T pop();/出栈，返回栈顶,习题4-3,习4-3 能否使用一个线性表对象作为栈，或将栈声明为继承线性表？入栈调用insert(0,x)函数，出栈调用remove(0)函数？为什么？【习题解答】都不能。,4.1.2 顺序栈,/顺序栈类，最终类，实现栈接口，T表示元素类型public final class SeqStack implements Stack private SeqList list;/顺序表 public SeqStack(int capacity)/构造空栈 public SeqStack()/构造空栈 public boolean isEmpty()/判空 public void push(T x)/x入栈 public T peek()/返回栈顶（未出栈）public T pop()/出栈，返回栈顶元素,习题解答4-4 使用顺序表对象作为栈成员变量的操作效率分析,数据结构（Java版）（第4版）第4章 8,4.1.3 链式栈,图4.3 链式栈的入栈和出栈操作,数据结构（Java版）（第4版）第4章 9,链式栈类LinkedStack,/链式栈类，最终类，实现栈接口，T表示元素类型public final class LinkedStack implements Stack private SinglyList list;/单链表 public LinkedStack()/构造空栈 public boolean isEmpty()/判空 public void push(T x)/x入栈 public T peek()/返回栈顶（未出栈）public T pop()/出栈，返回栈顶元素,数据结构（Java版）（第4版）第4章 10,习题解答4-4 使用单链表对象作为栈成员变量的操作效率分析,数据结构（Java版）（第4版）第4章 11,4.1.4 栈的应用,栈是嵌套调用机制的实现基础 使用栈以非递归方式实现递归算法,数据结构（Java版）（第4版）第4章 12,【例4.1】括号匹配的语法检查。,图4.5 表达式中圆括号匹配的语法检查,数据结构（Java版）（第4版）第4章 13,【例4.2】使用栈计算算术表达式值,中缀表达式：1+2*(3-4)+5,数据结构（Java版）（第4版）第4章 14,习题4-5,【习题解答】ABCDEF+*G/-H+*+IJ+K*-,习4-5 中缀表达式如下，写出后缀表达式。A+B*(C-D*(E+F)/G+H)-(I+J)*K,数据结构（Java版）（第4版）第4章 15,（1）将中缀表达式转换为后缀表达式,数据结构（Java版）（第4版）第4章 16,（2）后缀表达式求值,数据结构（Java版）（第4版）第4章 17,Expression,public class Expression StringBuffer toPostfix(String infix)/返回将infix中缀表达式转换成的后缀表达式 int toValue(StringBuffer postfix)/计算后缀表达式的值【思考题4-2】,数据结构（Java版）（第4版）第4章 18,4.2 队列,4.2.1 队列抽象数据类型队列（queue）是一种特殊的线性表，其插入和删除操作分别在线性表的两端进行。先进先出。,数据结构（Java版）（第4版）第4章 19,4.2.1 队列抽象数据类型,/队列接口，描述队列抽象数据类型，T表示元素类型public interface Queue public abstract boolean isEmpty();/判空 public abstract boolean add(T x);/x入队 public abstract T peek();/返回队头，没有删除 public abstract T poll();/出队，返回队头,数据结构（Java版）（第4版）第4章 20,习题4-8,习4-8 能否使用一个线性表对象作为队列，或将队列声明为继承线性表，入栈调用insert(x)函数，出栈调用remove(0)函数？为什么？,【习题解答】都不能。,数据结构（Java版）（第4版）第4章 21,4.2.2 顺序队列,顺序队列（1）使用顺序表，出队效率低,数据结构（Java版）（第4版）第4章 22,（2）使用数组，存在假溢出,不移动数据元素,数据结构（Java版）（第4版）第4章 23,2.顺序循环队列,front=(front+1)%length;rear=(rear+1)%length;,数据结构（Java版）（第4版）第4章 24,3.顺序循环队列类,/顺序循环队列类，最终类，实现队列接口，T元素类型public final class SeqQueue implements Queue private Object element;/数组 private int front,rear;/队列头尾下标 public SeqQueue(int capacity)/构造空队列 public SeqQueue()/构造空队列 public boolean isEmpty();/判空 public boolean add(T x);/x入队 public T peek();/返回队头，没有删除 public T poll();/出队，返回队头,数据结构（Java版）（第4版）第4章 25,4.2.3 链式队列,（1）使用单链表，入队效率低,数据结构（Java版）（第4版）第4章 26,（2）单链表设计，增加尾指针,数据结构（Java版）（第4版）第4章 27,链式队列类LinkedQueue,/链式队列类，最终类，实现队列接口，T元素类型public final class LinkedQueue implements Queue private Node front,rear;/队头和队尾结点 public LinkedQueue()/构造空队列 public boolean isEmpty();/判空 public boolean add(T x);/x入队 public T peek();/返回队头，没有删除 public T poll();/出队，返回队头,数据结构（Java版）（第4版）第4章 28,4.2.4 队列的应用,【例4.3】求解素数环问题。,数据结构（Java版）（第4版）第4章 29,【例4.3】求解素数环问题。,public class PrimeRing public PrimeRing(int max)public SortedSeqList createPrime(int max)【思考题4-3】使用循环双链表存储素数集合和素数环。使用栈？,数据结构（Java版）（第4版）第4章 30,实验4-13 走迷宫,(a)栈存储经过的点，出栈返回上一个点，再寻找其他路径,数据结构（Java版）（第4版）第4章 31,实验4-13 走迷宫,数据结构（Java版）（第4版）第4章 32,实验4-14 骑士游历,数据结构（Java版）（第4版）第4章 33,实验4-14 骑士游历,88棋盘，从(0,0)开始的一次游历路径,55棋盘，一次不成功游历路径,数据结构（Java版）（第4版）第4章 34,4.2.5 优先队列,优先队列（Priority Queue），队列中的每个元素都有一个优先级，每次出队的是具有最高优先级的元素。优先队列的存储结构。分别使用一个顺序表、排序顺序表、单链表、排序单链表、循环双链表、排序循环双链表作为优先队列的成员变量，分析优先队列的入队和出队操作的效率。,数据结构（Java版）（第4版）第4章 35,习题4-13 优先队列,优先队列，分别使用各种线性表。(E,4),(D,3),(A,1),(F,3),(B,2),(C,1),习题解答,数据结构（Java版）（第4版）第4章 36,习题4-13,数据结构（Java版）（第4版）第4章 37,优先队列类PriorityQueue,/优先队列类（升或降），最终类，实现队列接口，T是元素类型public final class PriorityQueue implements Queue private SortedCirDoublyList list;/排序循环双链表 private boolean asc;/asc指定升序（true）或降序 public PriorityQueue(boolean asc)/构造空队列 public PriorityQueue()/构造空队列，默认升序 public boolean isEmpty();/判空 public boolean add(T x);/x入队 public T peek();/返回队头，没有删除 public T poll();/出队，返回队头,数据结构（Java版）（第4版）第4章 38,【例4.4】进程按优先级调度管理,/进程类public class Process implements Comparable private String name;/进程名 private int priority;/优先级 public Process(String name,int priority)public Process(String name)public String toString()public int compareTo(Process p),数据结构（Java版）（第4版）第4章 39,递归定义递归算法 f(n)=nf(n-1)【思考题4-4】public static int factorial(int n)/求阶乘n!，递归方法,4.3 递归,数据结构（Java版）（第4版）第4章 40,【思考题4-4】求阶乘n!,public static int factorial(int n)/递归方法 if(n0)/抛出无效参数异常 throw new IllegalArgumentException(n=+n);if(n=0|n=1)/边界条件，递归结束条件 return 1;return n*factorial(n-1);/递归调用，递推通式,数据结构（Java版）（第4版）第4章 41,【例4.5】求Fibonacci序列。,数据结构（Java版）（第4版）第4章 42,打印数字塔,public static void line(int i)if(i10)line(i+1);System.out.print(String.format(%3d,i);执行line(1)结果？,输出10 9 8 7 6 5 4 3 2 1,数据结构（Java版）（第4版）第4章 43,习题解答例4.1 打印数字塔,1 1 2 1 1 2 3 2 1 1 2 3 4 3 2 1 1 2 3 4 5 4 3 2 1 1 2 3 4 5 6 5 4 3 2 1 1 2 3 4 5 6 7 6 5 4 3 2 1 1 2 3 4 5 6 7 8 7 6 5 4 3 2 1 1 2 3 4 5 6 7 8 9 8 7 6 5 4 3 2 1,数据结构（Java版）（第4版）第4章 44,【例4.6】计算算术表达式的值，递归算法。,算术表达式项项项项项项因子因子因子因子因子 因子%因子因子常数（算术表达式）整数数字数字数字整数数字数字0123456789,数据结构（Java版）（第4版）第4章 45,算术表达式语法图,数据结构（Java版）（第4版）第4章 46,算术表达式类ArithmeticExpression,/算术表达式（整数、不包括位运算）public class ArithmeticExpression private String infix;/中缀算术表达式 private int index;/当前字符序号 public ArithmeticExpression(String infix)public int intValue()/计算表达式，返回整数 private int term()/计算项 private int factor()/计算因子 private int constant()/计算常数,数据结构（Java版）（第4版）第4章 47,3.单链表的递归算法,（1）遍历单链表的递归算法 public String toString()return(+)+);private String toString(Node p)/递归算法 if(p=null)return;/递归结束条件 String str=();if(p.next!=null)str+=,;return str+toString(p.next);/递归调用,数据结构（Java版）（第4版）第4章 48,（2）构造单链表的递归算法,public SinglyList(T values)this();/创建空单链表=create(values,0);private Node create(T values,int i)/递归算法 Node p=null;if(i(valuesi,null);p.next=create(values,i+1);/递归调用 return p;,数据结构（Java版）（第4版）第4章 49,（2）构造单链表的递归算法,数据结构（Java版）（第4版）第4章 50,【思考题4-6】单链表，递归算法,遍历单链表的递归算法int size()/求长度Node search(T key)/查找void replaceAll(T key,T y)/替换boolean equals(Object obj)/比较相等 构造单链表的递归算法SinglyList(SinglyList list)/深拷贝,数据结构（Java版）（第4版）第4章 51,SinglyList深拷贝,public SinglyList(SinglyList list)this();=);private Node copy(Node p)/复制从p开始的子表，递归 Node q=null;if(p!=null)/递归执行条件 q=new Node(p.data,null);q.next=copy(p.next);/递归调用 return q;,