第三章_栈和队列

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,数据结构（,Java,版）（第,2,版）,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,数据结构（,Java,版）（第,2,版）,*,数据结构与算法设计（,Java,版）,第,1,章 绪论,第,2,章 线性表,第,3,章 栈与队列,第,4,章 串,第,5,章 数组,第,6,章 树和二叉树,第,7,章 图,第,8,章 排序,第,3,章 栈和队列,3.1,栈,3.2,队列,目的：,使用栈或队列求解应用问题。,要求：,掌握栈和队列抽象数据类型，以及顺 序和链式存储结构实现；理解对于怎 样的应用问题，需要使用栈或队列，以及怎样使用。,重点：,栈和队列的设计和应用。,难点：,栈或队列的使用场合，以及如何使用 栈和队列求解应用问题。,3.1,栈,3.1.1,栈抽象数据类型,3.1.2,顺序栈,3.1.3,链式栈,3.1.4,栈的应用,3.1.1,栈抽象数据类型,栈（,stack,）是一种特殊的线性表，,其插入和删除操作只允许在线性表的一端进行。,public interface SStack,boolean isEmpty();/,判断是否空栈,boolean push(E element);/,入栈,E pop();/,出栈,E get();/,取栈顶元素值,3.1.2,顺序栈,public class SeqStack implements SStack,private Object value;,private int top;/,栈顶元素下标,3.1.3,链式栈,public class LinkedStack,implements SStack,private Node top;,3.1.4,栈的应用,栈是嵌套调用机制的实现基础,使用栈以非递归方式实现递归算法,例,3.1,判断表达式中圆括号是否匹配,例,3.2,使用栈计算表达式的值。,中缀表达式,1+2*(3-4)+5,1.,将中缀表达式转换为后缀表达式,2.,后缀表达式求值,3.2,队列,3.2.1,队列抽象数据类型,3.2.2,顺序队列,3.2.3,链式队列,3.2.4,队列的应用,3.2.1,队列抽象数据类型,队列（,queue,）是一种特殊的线性表，其插入和删除操作分别在线性表的两端进行。,public interface QQueue /,队列接口,boolean isEmpty();/,判断队列是否为空,boolean enqueue(E element);/,入队,E dequeue();/,出队,3.2.2,顺序队列,顺序队列，假溢出,2.,顺序循环队列,front=(front+1)%length;,rear=(rear+1)%length;,3.,顺序循环队列类,public class SeqQueue implements QQueue,private Object value;,private int front,rear;/,队列头尾下标,3.2.3,链式队列,public class LinkedQueue implements QQueue /,链式队列类,private Node front,rear;,3.2.4,队列的应用,例,3.3,求解素数环问题。,素数：质数（,prime number,）又称素数，有无限个。一个大于,1,的,自然数,，除了,1,和它本身外，不能被其他自然数,整除,（除,0,以外）的数称之为素数（质数）；否则称为,合数,。根据,算术基本定理,，每一个比,1,大的整数，要么本身是一个质数，要么可以写成一系列质数的乘积；而且如果不考虑这些质数在乘积中的顺序，那么写出来的形式是唯一的。最小的质数是,2,。,3.2.4,队列的应用,例,3.3,求解素数环问题。,素数环：,将从,1,到,n,这,n,个整数围成一个圆环，若其中任意,2,个相邻的数字相加，结果均为素数，那么这个环就成为素数环。,使用顺序表和顺序队列来解素数环问题：,栈和队列及其应用,走迷宫,（网络自学，课程设计题目）,骑士游历,（网络自学，课程设计题目）,