《第04章栈和队列(java版)概要》由会员分享，可在线阅读，更多相关《第04章栈和队列(java版)概要（51页珍藏版）》请在金锄头文库上搜索。
1、数据结构（Java版）（第4版）第4章 1,第4章 栈和队列,4.1 栈 4.2 队列 4.3 递归 目的：使用栈或队列求解应用问题。 要求：栈和队列的顺序和链式存储结构实现。 重点：栈和队列的设计和应用。 难点：栈或队列的使用场合，以及如何使用 栈和队列求解应用问题。,数据结构（Java版）（第4版）第4章 2,4.1 栈,4.1.1 栈抽象数据类型 栈（stack）是一种线性表，插入和删除操作只允许在线性表的一端进行。先进后出。,数据结构（Java版）（第4版）第4章 3,图4.1 栈（顺序栈）及其状态变化,A, B, C, D 入栈, 入栈, 出栈, 入栈, 入栈, 出栈, 出栈, 出栈
2、,【思考题4-1】 入栈A, B, C, D，出栈A, B, C, D、D, C, B, A？还有哪些？有哪些不可能的出栈序列？为什么？,数据结构（Java版）（第4版）第4章 4,栈抽象数据类型ADT，栈接口,public interface Stack public abstract boolean isEmpty(); /判空 public abstract void push(T x); /x入栈 public abstract T peek(); /返回栈顶，未出栈 public abstract T pop(); /出栈，返回栈顶 ,数据结构（Java版）（第4版）第4章 5,习题
3、4-3,习4-3 能否使用一个线性表对象作为栈，或将栈声明为继承线性表？入栈调用insert(0,x)函数，出栈调用remove(0)函数？为什么？ 【习题解答】都不能。,数据结构（Java版）（第4版）第4章 6,4.1.2 顺序栈,/顺序栈类，最终类，实现栈接口，T表示元素类型 public final class SeqStack implements Stack private SeqList list; /顺序表 public SeqStack(int capacity) /构造空栈 public SeqStack() /构造空栈 public boolean isEmpty() /
4、判空 public void push(T x) /x入栈 public T peek() /返回栈顶（未出栈） public T pop() /出栈，返回栈顶元素 ,数据结构（Java版）（第4版）第4章 7,习题解答4-4 使用顺序表对象作为栈成员变量的操作效率分析,数据结构（Java版）（第4版）第4章 8,4.1.3 链式栈,图4.3 链式栈的入栈和出栈操作,数据结构（Java版）（第4版）第4章 9,链式栈类LinkedStack,/链式栈类，最终类，实现栈接口，T表示元素类型 public final class LinkedStack implements Stack priva
5、te 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章 1
6、2,【例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版）第
7、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 队列抽象数据类型,/队列接口，描述队列抽象数据类型
8、，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)函数？为什么？,【习题解答】都不能。,数据结构（
9、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 el
10、ement; /数组 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）单链表设计
11、，增加尾指针,数据结构（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(); /出队，返回队头 ,数据结
12、构（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、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版）第
14、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
15、指定升序（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 Proces
