数据结构Java版第4章栈与队列

1、数据结构（数据结构（Java版）版）叶核亚叶核亚数据结构（数据结构（Java版）版） 第1章 绪论 第2章 线性表 第3章 排序第4章 栈与队列 第5章 数组和广义表 第6章 树和二叉树 第7章 查找 第8章 图 第9章 综合应用设计第4章 栈与队列 栈和队列是两种特殊的线性表。与线性表一样，栈和队列的数据元素之间具有顺序的逻辑关系，都可以采用顺序存储结构和链式存储结构；与线性表不同的是，线性表的插入和删除操作不受限制，可以在任意位置进行，而栈和队列的插入和删除操作受到限制，栈的插入和删除操作只允许在线性表的一端进行，而队列的插入和删除操作则分别在线性表的两端进行。 栈的特点是后进先出，队列的

2、特点是先进先出，两者在实际问题中有着广泛的应用。 4.1 栈 4.2 队列 4.3 递归数据结构（Java版）叶核亚4.1 栈n4.1.1 栈的定义n4.1.2 栈的抽象数据类型n4.1.3 栈的存储结构及实现n4.1.4 栈的应用举例数据结构（Java版）叶核亚4.1.1 栈的定义n栈（stack）是一种特殊的线性表，其插入和删除操作只允许在线性表的一端进行。n允许操作一端称为栈顶（top），不允许操作的一端称为栈底（bottom）。n栈顶的当前位置是动态的，标识栈顶当前位置的变量称为栈顶指针。n栈中插入数据元素的过程称为入栈（push），删除数据元素的过程称为出栈（pop）。n当栈中没有数

3、据元素时称之为空栈。图4.1 栈结构数据结构（Java版）叶核亚4.1.2 栈的抽象数据类型1栈的数据元素 2栈的基本操作n栈的初始化，设置栈状态为空。n判断栈的状态是否为空。n判断栈的状态是否已满。n入栈：将数据元素插入栈中作为新的栈顶数据元素的过程。在入栈之前必须判断栈的状态是否已满，如果栈不满，则接收新数据元素入栈，否则产生上溢错误（overflow）。n出栈：取出当前栈顶数据元素，下一个数据元素成为新的栈顶数据元素的过程。在出栈之前，必须判断栈的状态是否为空。如果栈的状态为空，产生下溢错误（underflow）。n获得栈顶数据元素，此时该数据元素未出栈。数据结构（Java版）叶核亚栈的

4、接口StackInterfacepackage ds_java;public interface StackInterface /栈的接口 public boolean isEmpty(); /判断栈的状态是否为空 public boolean isFull(); /判断栈的状态是否已满 public boolean push(Object k); /k对象入栈 public Object pop(); /出栈 public Object get(); /获得栈顶元素，未出栈数据结构（Java版）叶核亚4.1.3 栈的存储结构及实现1栈的顺序存储结构及操作实现package ds_java;i

5、mport ds_java.StackInterface;public class Stack1 implements StackInterface /栈的顺序存储结构 private Object table; private final int empty=-1; /声明整数常量 private int top=empty; /top为栈顶元素下标数据结构（Java版）叶核亚顺序栈的操作实现 （1）栈的初始化构造方法申请table数组的存储空间准备存放栈的数据元素，设置栈初始状态为空。算法如下： public Stack1(int n) /带参数时，构造具有n个存储单元的空栈 table=

6、new Objectn; top=empty; /设置栈初始状态为空 public Stack1() /不带参数时，构造具有10个存储单元的空栈 this(10); （2）判断栈状态是否为空 public boolean isEmpty() /判断栈的状态是否为空 数据结构（Java版）叶核亚【例4.1】 使用顺序栈的基本操作import ds_java.Stack1;class Stack1_ex public static void main(String args) int i=0,n=4; Stack1 s1=new Stack1(20); System.out.print(Push:

7、 ); while(i0) /有参数时， expstr1=args0; /获得表达式字符串 System.out.println(expstr1+ isValid +isValid(expstr1); public static String isValid(String expstr) Stack1 s1=new Stack1(30); /创建空栈 char ch; int i=0;数据结构（Java版）叶核亚判断表达式中括号是否匹配的算法描述 数据结构（Java版）叶核亚4.2 队列n4.2.1 队列的定义n4.2.2 队列的抽象数据类型n4.2.3 队列的存储结构及实现n4.2.4 队列

8、的应用举例数据结构（Java版）叶核亚4.2.1 队列的定义n队列（queue）是一种特殊的线性表，其插入和删除操作分别在线性表的两端进行。n向队列中插入元素的过程称为入队（enqueue），删除元素的过程称为出队（dequeue）。n允许入队的一端为队尾（rear），允许出队的一端为队头（front）。标识队头和队尾当前位置的变量称为队头指针和队尾指针。n当队列中没有数据元素时称作空队列。数据结构（Java版）叶核亚4.2.2 队列的抽象数据类型1队列的数据元素2队列的基本操作n队列的初始化，设置队列状态为空。n判断队列的状态是否为空。n判断队列的状态是否已满。n入队：将数据元素从队尾处加入

9、队列的过程。在入队之前必须判断队列的状态是否已满，如果队列不满，则接收新数据元素入队，队列满时数据元素不能入队，产生上溢错误（overflow）。n出队：从队头处取出数据元素的过程。在出队之前，必须判断队列的状态是否为空。队列空时，取不到元素，产生下溢错误（underflow）。数据结构（Java版）叶核亚队列的接口QueueInterfacepackage ds_java;public interface QueueInterface /队列的接口 public boolean isEmpty(); /判断队列状态是否为空 public boolean isFull(); /判断队列状态是否

10、已满 public boolean enqueue(Object k); /k对象入队 public Object dequeue(); /出队 数据结构（Java版）叶核亚4.2.3 队列的存储结构及实现1队列的顺序存储结构10203001234frontrear304001234frontrear(b) 队列的“假溢出”(a) 以数组存储队列的数据元素50数据结构（Java版）叶核亚2顺序循环队列及操作实现数据结构（Java版）叶核亚顺序循环队列的操作实现 package ds_java;import ds_java.QueueInterface;public class Queue1 i

11、mplements QueueInterface/顺序循环队列 private Object table; private int front,rear; /front和rear为队列头尾下标Queue1类的一个对象就是一个队列。队列数据元素的类型是Object。顺序循环队列的操作实现如下，这些算法写在Queue1类中，作为Queue1类的方法。（1）队列的初始化构造方法申请table数组的存储空间准备存放队列数据元素，设置队列初始状态为空，即front =0且rear=0。算法如下： public Queue1(int n) /构造长度为n的空队列 数据结构（Java版）叶核亚【例4.4】

12、使用顺序循环队列的基本操作。import ds_java.Queue1;class Queue1_ex public static void main(String args) int i=0,n=2; Queue1 q1=new Queue1(20); while(iargs.length) q1.enqueue(argsi); /入队 System.out.print(Enqueue: +argsi+t); q1.output(); i+; for(i=0;in;i+)数据结构（Java版）叶核亚3队列的链式存储结构及操作实现n队列的链式存储结构以单向链表实现，设front和rear分别指

13、向队头和队尾结点。 1 2 1 frontrear(c) 一个元素入队(a) 设置队列为空front=nullrear=null(b) 第一个元素入队data nextfrontrearrear 1 2 front(d) 一个元素出队rear(e) 最后一个元素出队后，队列状态为空front=null rear=nullfront数据结构（Java版）叶核亚链式队列的基本操作实现 package ds_java;import ds_java.OnelinkNode;import ds_java.Onelink1;public class Queue2 extends Onelink1/队列的链

14、式存储结构 private OnelinkNode front,rear;Queue2类的一个对象就是一个队列。其中，成员变量front和rear分别指向队头和队尾结点，结点类型为单向链表的结点类OnelinkNode，结点数据域的类型为int。链式队列的基本操作实现如下，这些算法写在Queue2类中，作为Queue2类的方法。（1）队列的初始化构造方法创建一条单向链表用做队列，设置队列状态为空链表。算法如下： public Queue2() /构造空队列 数据结构（Java版）叶核亚4.2.4 队列的应用举例n1处理等待问题时系统设立队列n队列具有“先进先出”的特性，当需要按一定次序等待时，

15、系统需设立一个队列。2实现广度遍历算法时使用队列n实现广度遍历算法，如按层次遍历二叉树、以广度优先算法遍历图，都需要使用队列。详细算法将在以后的章节中介绍。数据结构（Java版）叶核亚【例4.5】 解素数环问题。将n个数（1n）排列成环形，使得每相邻两数之和为素数，构成一个素数环。import ds_java.Queue2; /引用链式存储结构的队列，元素为int型import ds_java.LinearList1; /引用顺序存储结构的线性表public class Primering /求素数环 public static boolean isPrime(int k) /判断k是否为素数

16、 int j=2; if(k=2) return true; if(k2 & k%2=0) return false; else 数据结构（Java版）叶核亚4.3 递归1问题的定义是递归的2算法是递归的n如果能够分解成几个相对简单且解法相同或类似的子问题时，只要解决了子问题，那么原问题就迎刃而解，这就是递归求解。例如，5！=54！。n当分解后的子问题可以直接解决时，就停止分解。这些可以直接求解的问题称为递归结束条件。例如，1！=1。n根据递归定义，编写能够直接反映递归定义的递归函数来求解。2)!1(1 , 01!nnnnn2)2() 1(10)(nnfnfnnnf，数据结构（Java版）叶核

17、亚【例4.6】 求n！。public class Factorial static int f(int n) /递归方法 if(n=0 | n=1) return 1; else System.out.println(n+!=+n+*+(n-1)+!); return n*f(n-1); public static void main(String args) int i=5;数据结构（Java版）叶核亚【例4.7】 打印数字塔。打印如下形式的数字塔： 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

18、 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 题目本身虽不是递归定义的，但可以用递归算法求解。程序如下：public class Dig9_r static void count(int i,int n) /递归方法 if(in)数据结构（Java版）叶核亚3数据结构是递归的n将单向链表结点类的next链与指向链表第1个结点的head递归定义为：指向一个单向链表非指向一个空链表及nullnullheadnext data nexthead(b) 单向链表head=null(a) 空链表数据结构（Java版）