堆栈和队列教案范文

堆栈和队列教案范文 数据结构课程教案第3章堆栈队列课型讲授3.1堆栈3.2堆栈的应用教学理解堆栈的基本概念；掌握顺序堆栈类及链式堆栈类的设计方法；目标掌握堆栈的应用课题教材分析重点难点顺序堆栈类及链式堆栈类堆栈的应用讲授法、案例法、演示法多媒体教法教学方法分析教学手段教学过程回顾前课，导入新课3.1堆栈3.1.1堆栈的基本概念堆栈（也简称作栈）是一种特殊的线性表，堆栈的数据元素以及数据元素间的逻辑关系和线性表完全相同，其差别是线性表允许在任意位置进行插入和删除操作，而堆栈只允许在固定一端进行插入和删除操作。 堆栈中允许进行插入和删除操作的一端称为栈顶，另一端称为栈底。 堆栈的插入和删除操作通常称为进栈或入栈，堆栈的删除操作通常称为出栈或退栈。 从输入和输出数据元素的位置关系看，堆栈的功能和一种火车调度装置的功能类同。 3.1.2堆栈抽象数据类型.数据集合堆栈的数据集合可以表示为a0,a1,a n-1，每个数据元素的数据类型可以是任意的类类型。 数据结构教案符策锐第26页教学过程.操作集合 （1）入栈push(obj)把数据元素obj插入堆栈。 （2）出栈pop()出栈,删除的数据元素由函数返回。 （3）取栈顶数据元素getTop()取堆栈当前栈顶的数据元素并由函数返回。 （4）非空否notEmpty()若堆栈非空则函数返回true，否则函数返回false。 3.1.3顺序堆栈1顺序堆栈的存储结构顺序存储结构的堆栈称作顺序堆栈。 顺序堆栈的存储结构示意图如图所示。 a0a1a2a3a42.顺序堆栈类的设计public classSeqStack implementsStackfinal int defaultSize=10;int top;/栈顶位置Objectstack;/数组对象int maxStackSize;/最大数据元素个数public SeqStack()/无参构造函数（方法）initiate(defaultSize);public SeqStack(int sz)/有参构造函数（方法）initiate(sz);private voidinitiate(int sz)/初始化maxStackSize=sz;top=0;stack=new Objectsz;public voidpush(Object obj)throws Exception/入栈if(top=maxStackSize)throw newException(堆栈已满！);stacktop=obj;/保存元素top+;/产生新栈顶位置数据结构教案符策锐第27页教学过程public Objectpop()throws Exception/出栈if(top=0)throw newException(堆栈已空！);top-;/产生原栈顶元素return stacktop;/返回原栈顶元素public ObjectgetTop()throws Exception/取栈顶元素if(top=0)throw newException(堆栈已空！);return stacktop-1;/返回原栈顶元素public booleannotEmpty()/非空否return(top0);3.顺序堆栈类的测试public classSeqStackTestpublic staticvoid main(Stringargs)SeqStack myStack=new SeqStack();int test=1,3,5,7,9;int n=5;tryfor(int i=0;i 数据结构教案符策锐第28页教学过程1.链式堆栈的存储结构和单链表相同，链式堆栈也是由一个个结点组成的，每个结点由两个域组成，一个是存放数据元素的数据元素域element，另一个是存放指向下一个结点的对象引用（即指针）域next。 堆栈有两端，插入数据元素和删除数据元素的一端为栈顶，另一端为栈底。 链式堆栈都设计成把靠近堆栈头head的一端定义为栈顶。 依次向链式堆栈入栈数据元素a0,a1,a2,.,an-1后，链式堆栈的示意图如图所示。 a n-1a n-2a0public classLinStack implementsStackNode head;/堆栈头int size;/结点个数public voidLinStack()/构造方法head=null;size=0;public voidpush(Object obj)/入栈head=new Node(obj,head);/新结点作为新栈顶size+;public Objectpop()throws Exception/出栈if(size=0)throw newException(堆栈已空！);Object obj=head.element;/原栈顶数据元素head=head.next;/原栈顶结点脱链size-;return obj;public booleannotEmpty()/非空否return head!=null;public ObjectgetTop()/获取栈顶数据元素return head.element;数据结构教案符策锐第29页教学过程3.2堆栈的应用堆栈是各种软件系统中应用最广泛的数据结构之一。 括号匹配和表达式计算是编译软件中的基本问题，其软件设计中都需要使用堆栈。 3.2.1括号匹配问题例3-2假设一个算术表达式中包含圆括号、方括号和花括号三种类型的括号，编写一个判别表达式中括号是否正确匹配的函数，并设计一个测试主函数。 设计分析算术表达式中右括号和左括号匹配的次序，正好符合后到的括号要最先被匹配的“后进先出”的操作特点，因此可以借助一个堆栈来进行判断。 括号匹配共有四种情况 （1）左右括号配对次序不正确； （2）右括号多于左括号； （3）左括号多于右括号； （4）括号匹配不正确。 具体方法是顺序扫描算术表达式（表现为一个字符串），当遇到三种类型的左括号时让这些括号进栈；当扫描到某一种类型的右括号时，比较当前栈顶括号是否与之匹配，右匹配则退栈继续进行判断；若当前栈顶括号与当前扫描的括号类型不相同，则左右括号配对次序不正确；若字符串当前为某种类型的右括号而堆栈已空，则右括号多于左括号；字符串循环扫描结束时，若堆栈非空（即堆栈中尚有某种类型左括号），则说明左括号多于右括号；否则，左右括号配对匹配正确。 程序代码设计如下public classExam3_2public staticvoid expIsCorrect(Stringexp,int n)throws ExceptionSeqStack myStack=new SeqStack();for(int i=0;i 队列中允许进行插入操作的一端称为队尾，允许进行删除操作的一端称为队头。 队列的插入操作通常称作入队列，队列的删除操作通常称作出队列。 下图是一个依次向队列中插入数据元素a0,a1,.,a n-1后的示意图，其中，a0是当前队头数据元素，a n-1是当前队尾数据元素。 队头出队尾.3.3.2队列的抽象数据类型a0a1a2a n-1入1数据集合队列的数据集合可以表示为a0,a1,an-1，每个数据元素的数据类型可以是任意的类类型。 2操作集合 （1）入队列append(obj)把数据元素obj插入队尾。 （2）出队列delete()把队头数据元素删除并由函数返回。 数据结构教案符策锐第33页教学过程 （3）取队头数据元素getFront()取队头数据元素并由函数返回。 （4）非空否notEmpty()非空否。 若队列非空，则函数返回true，否则函数返回false。 队列抽象数据类型的Java接口定义如下public interfaceQueuepublic voidappend(Object obj)throws Exception;public Objectdelete()throws Exception;public ObjectgetFront()throws Exception;public booleannotEmpty();3.3.3顺序队列1顺序队列的存储结构下图是一个有6个存储空间的顺序队列的动态示意图，图中front指示队头，rear指示队尾。 555rear=54E4443rear=32C rear=3front=21C3D2front=21C11B frontrear=0(a)front=0A00(b)(c)(d)空队列入队A、B、C后的状态出队A、B后的状态入队D、E后的状态2顺序队列的“假溢出”问题顺序队列因多次入队列和出队列操作后出现的有存储空间但不能进行入队列操作的溢出称作假溢出。 （见下页图示）3顺序循环队列的基本原理假溢出是由于队尾rear的值和队头front的值不能由所定义数组下界值自动转为数组上界值而产生的。 因此，解决的方法是把顺序队列所使用的存储空间构造成一个逻辑上首尾相连的循环队列。 数据结构教案符策锐第34页教学过程当rear和front达到maxSize-1后，再加1就自动到0。 这样，就不会出现顺序队列数组的头部已空出许多存储空间，但队尾却因数组下标越界而引起溢出的假溢出问题。 4顺序循环队列的队空和队满判断问题顺序循环队列的队列满和队列空状态r ea r=65F4E3D fr on t=2C1（a）初始化状态；（b）队列满状态；（c）队列空状态front=0rear=0front=0rear=0front=0rear=0F501E501B A0顺序队列的“假溢出”43250143432D2C(a)(b)(c)解决顺序循环队列的队列满和队列空状态判断问题通常有三种方法 （1）少用一个存储空间当少用一个存储空间时，以队尾rear加1等于队头front为队列满的判断条件，即队列满的判断条件此时为(rear+1)%maxSize=front队列空的判断条件仍然为rear=front （2）设置一个标志位添加一个标志位。 设标志位为tag，初始时置tag=0；每当入队列操作成功就置tag=1；每当出队列操作成功就置tag=0。 则队列空的判断条件为rear=front&tag=0队列满的判断条件为rear=front&tag=1 （3）设置一个计数器添加一个计数器。 设计数器为count，初始时置count=0；每当入队列操作成功就使count加1；每当出队列操作成功就使count减1。 这样，该计数器不仅具有计数功能，而且还具有像标志位一样的标志作用，则此时队列空的判断条件数据结构教案符策锐第35页教学过程为count=0队列满的判断条件为count0&rear=front3.3.4顺序循环队列类public classSeqQueue implementsQueuefinal intdefaultSize=10;int front;/队头int rear;/队尾int count;/元素个数计数器int maxSize;/最大数据元素个数Objectdata;/保存队列元素的数组public SeqQueue()/无参数构造方法this.initiate(defaultSize);public SeqQueue(int sz)/带参数构造方法this.initiate(sz);private voidinitiate(int sz)/初始化maxSize=sz;front=rear=0;count=0;data=new Objectsz;public voidappend(Object obj)throws Exception/入队if(count0&front=rear)throw newException(队列已满！);datarear=obj;rear=(rear+1)%maxSize;/加1后求模count+;public Objectdelete()throws Exception/出队if(count=0)throw newException(队列已空！);Object temp=datafront;front=(front+1)%maxSize;/加1后求模count-;return temp;public ObjectgetFront()throws Exception/取队头数据元素if(count=0)throw newException(队列已空！);return datafront;数据结构教案符策锐第36页教学过程public booleannotEmpty()/非空否return count!=0;3.3.5链式队列链式存储结构的队列称作链式队列。 1链式队列的存储结构a0a1a n-2a n-12链式队列类设计链式队列类要用到前面讨论过的Node类和Queue接口。 public classLinQueue implementsQueueNode front;/队头Node rear;/队尾int count;/计数器public LinQueue()/无参数构造方法initiate();public LinQueue(int sz)/带参数构造方法initiate();private voidinitiate()/初始化front=rear=null;count=0;public voidappend(Object obj)/插入Node newNode=new Node(obj,null);/创建新结点if(rear!=null)rear.next=newNode;/链入新结点rear=newNode;/置队尾if(front=null)front=newNode;/置队头count+;public Objectdelete()throws Exceptionif(count=0)throw newException(队列已空！);Node temp=front;front=front.next;/原队头结点脱链count-;数据结构教案符策锐第37页教学过程return temp.getElement();public ObjectgetFront()throws Exception/取队头数据元素if(count=0)throw newException(队列已空！);return front.getElement();public booleannotEmpty()/非空否return count!=0;3.3.6队列的应用回文是指一个字符序列以中间字符为基准两边字符完全相同。 例3-3编写判断一个字符序列是否回文的方法，并设计一个主方法进行测试。 算法思想设字符数组str中存放了要判断的字符串。 把字符数组中的字符逐个分别存入一个队列和一个堆栈，然后逐个出队和退栈并比较出队的字符和退栈的字符是否相等，若全部相等则该字符序列是回文，否则就不是回文。 程序代码如下public classExam3_3public staticvoid huiWen(String str)throws Exceptionint n=str.length();SeqStack myStack=new SeqStack(n);SeqQueue myQueue=new SeqQueue(n);for(int i=0;i 小结作业预习3.4优先级队列实验准备实验三利用堆栈实现数据元素逆置（P893-15）数据结构教案符策锐第39页数据结构课程教案第3章堆栈队列课型讲授3.4优先级队列教学理解优先级队列的基本概念；掌握顺序优先级队列类的设计；掌握目标优先级队列的应用课题教材分析重点难点顺序优先级队列类及其应用优先级队列的应用讲授法、案例法、演示法多媒体教法教学方法分析教学手段教学过程回顾前课，导入新课3.4优先级队列优先级队列是带有优先级的队列。 用顺序存储结构实现的优先级队列称作顺序优先级队列。 用链式存储结构存储的优先级队列称作链式优先级队列。 在此仅讨论顺序优先级队列类的设计方法。 3.4.1顺序优先级队列类顺序优先级队列和顺序循环队列相比主要有两点不同 （1）对于顺序优先级队列来说，出队列操作不是把队头数据元素出队列，而是把队列中优先级最高的数据元素出队列。 （2）对于顺序优先级队列来说，数据元素由两部分组成，一部分是原先意义上的数据元素，另一部分是优先级。 通常设计优先级为int类型的数值，并规定数值越小优先级越高。 由两部分组成的数据元素类设计如下public classElementprivate Objectelem;private intpriority;Element(Object obj,int i)elem=obj;priority=i;/原先意义上的数据元素/优先级/构造函数数据结构教案符策锐第40页教学过程public ObjectgetElem()/取数据元素return elem;public voidsetElem(Object obj)/设置数据元素elem=obj;public intgetPriority()/取优先级return priority;public voidsetPriority(int i)/设置优先级priority=i;顺序优先级队列类设计如下public classSequeuestatic finalintdefaultSize=10;int front;/队头int rear;/队尾int count;/计数器int maxSize;/元素最大个数Elementdata;/数据元素public Sequeue()/无参构造函数this.initiate (10);public Sequeue(int sz)/带参构造函数this.initiate(sz);private voidinitiate(int sz)/初始化maxSize=sz;front=rear=0;count=0;data=new Elementsz;public voidappend(Object obj)throws Exception/插入if(count=maxSize)throw newException(队列已满！);datarear=(Element)obj;/插在队尾rear=rear+1;count+;public Elementdelete()throws Exceptionif(count=0)数据结构教案符策锐/删除第41页教学过程throw newException(队列已空！)