队列和栈试讲20分钟教案

数据结构中的栈和队列学员十队五班付彦丽武警工程大学教学目的：通过本堂课的学习，使学员能够了解栈和队列的定义、基本思想；熟知栈和队列的结构设计、操作过程；掌握栈和队列的算法设计技巧。教学内容及时间安排：1.导课1分钟2.栈和队列的相关概念5分钟3.栈和队列的对比3分钟4.顺序栈的实现10分钟顺序栈的基本操作及判空判满5.顺序栈的应用举例4分钟6.小结合布置作业1分钟教学重难点：顺序栈的实现、相关操作以及判空判满教学方法：讲授法；演示法；讨论法；上机实验法教学媒体：多媒体，黑板课型：理论课课时：1课时教学设计及教学内容备注一．课程概述这门课的名称叫做数据结构，所选用的教材为清华大学出版社，熊岳山编著的《数据结构与算法》一书。这本书的理论讲解淑芬详细易懂，但应用实例相对较少。所以在教学过程中要添加相应的实例讲解。目前，计算机与其他学科交叉融合的越来越深，各个学科对数据类型都提出了不同的要求。数据结构这门课就是为了设计满足要求的数据结构。所以这门课不仅是一门必修课，还是计算机类各专业的核心课程。本堂课所要讲授的栈与队列，是数据结构中最基础的线性结构。通过本堂课学习，学员们可以更直观的了解到了什么是数据结构，为后期数据结构设计打下基础。二．教学目的本课程的教学目标划分为理解、熟知、掌握三个层次首先要让学员理解栈和队列的定义，以及其基本思想；在理解的基础上，将栈和队列的结构设计、操作过程了熟于心；最终目的是掌握栈和队列的算法设计技巧。三．教学内容栈和队列的相关概念栈和队列的对比顺序栈的实现顺序栈的基本操作及判空判满习题举例其中重难点部分在顺序栈的实现及基本操作四．教学重难点本课程的重难点，在顺序栈的实现、基本操作以及判空判满。这部分的内容相对抽象，学生需要在脑海中勾勒出顺序栈的模型，才能更好的进行理解。教学过程中借助PPT动画效果演示帮助学生理解并编程。五．教学对象分析本课的教学对象为学历教育，计算机专业的大三学员，课程主要开设在大三的上学期。学员在大一大二学习过《计算机基础》《程序语言设计》《C语言》等课程。所以其能够熟练使用计算机，具有一定的编程基础，并掌握了简单的C语言编程。但由于刚开始系统的学习计算机，所以其理论学习相对较多，实践应用较少，具有较好的模仿编程能力，但是独立编程能力较弱。六．教学方法手段由于数据结构是一门很抽象的课程，单纯的讲授难以达到教学目的，故教学方法采用讲授和演示相结合的方法。学员学习方法采用讨论法、上机实验法。学员能在讨论中加深对栈和队列的理解，在课后的上机实验中对课程内容进行实现。七．教学过程及时间安排首先，回顾前面学习的线性表，作为导课，计算用时2min；利用生活实例对栈和队列的基本概念进行讲授计划用时5分钟；将学员划分小组，对栈和队列进行对比，计划用时3分钟；结合演示讲解顺序栈的实现、基本操作、判空判满，计划用时10分钟；顺序栈应用精讲，计划用时4分钟；最后，用一分钟的时间进行课堂总结并布置作业。数据结构的栈和队列导课：首先，回顾一下前面我们学习过的线性表线性表的定义：是n个数据元素的有限序列线性表是最基本、最简单、也是最常用的一种数据结构线性表中的数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其他数据元素都是收尾相接的。线性表可以分为一般线性表和受限线性表。其中队列和栈就是受限线性表，受限表示对节点的操作受限制。线性表的逻辑结构简单，便于实现和操作，是一种广泛使用的数据结构。一．栈和队列（一）什么是栈栈是限定仅在表尾进行插入或删除操作的线性表，是一种后进先出（LastInFirstOut,LIFO）的数据结构。我们把允许插入和删除的一端称为栈顶（top），另一端称为栈底（bottom），不含任何数据元素的栈称为空栈。第一个进栈的元素在栈底，最后一个进栈的元素在栈给出M1911A1半自动手枪的示例，子弹进出弹夹就是一个生活中的栈顶；第一个出栈的元素为栈顶元素，最后一个出栈的元素为栈底元素。栈的插入操作通常称为进栈或入栈，栈的删除操作通常称为退栈或出栈。（二）什么是队列队列是一种先进先出（FirstInFirstOut，FIFO）的数据结构，队列有两个指针一个指向队尾，一个指向队首。它是只允许在一端删除，在另一端插入的线性表，允许删除的一端叫做队头(front)，允许插入的一端叫做队尾(rear)，也就是说数据从队尾进，从队首出。二．栈和队列的对比队列先进先出，栈先进后出。栈是限定只能在表的一端进行插入删除操作的线性表。队列是限定只能在表的一端进行插入和在另一端进行删除的操作的线性表。它们都是在程序设计中被广泛使用的线性数据结构，即数据元素之间的关系相同，限定性的线性表结构。三．顺序栈栈的表示和实现有两种结构——顺序栈和链栈，本节课我们只讲顺序栈。顺序栈：利用一组地址连续的存储单元依次自栈底到栈顶存放栈的数据元素。栈顶top随着插入和删除而变化的，数据入栈或出栈时使整形变量top分别加1或减1。思考：top的初值是多少？栈满时top是多少？top表示的是栈顶数据的位置，还是栈顶数据的上一个位置？（一）顺序栈的类型定义#defineStackSize10typedefchardatatype;typedefstructSeqStack{datatypedata[StackSize];inttop;}SeqStack；SeqStacks;//s即为一个栈SeqStack*sq=&s;//sq即为一个栈的指针（二）顺序栈的基本操作计算机中用到的栈。给出春运示例。如果队列突然变成栈，示例。习题。top初值为-1，栈满时为StackSize-1.top表示的栈顶数据的位置讲解为什么要这么定义顺序栈（1）构造一个空栈假设s已指向某个栈voidinitstack(seqstack*s){s-top=-1;}（2）判栈空假设s已指向某个栈intStackEmpty(seqstack*s){if(s-top==-1)return1;elsereturn0;}（3）判栈满假设s已指向某个栈intStackFull(seqstack*s){if(s-top==StackSize-1)return1;elsereturn0;}（4）入栈intpush(seqstack*s,charx){if(s-top==StackSize-1){error(“栈满”);return0;}else{s-top++;s-data[s-top]=x;return1;}}（5）出栈datatypepop(seqstack*s){if(s-top==-1){error(“栈空”);return0;}else{x=s-data[s-top];为什么top的初值为-1。数组的特性如何判断一个栈空？判断其top值是否为-1如何判断一个栈满？判断其top值是否为StackSize-1为什么是StackSize-1？数组特性入栈首先要判断是否栈满。插入数据和top值改变哪个先？top值代码举例出栈首先要判断是否栈空。删除数据和top值改哪个先？代码举例s-top--;returnx;}}（6）取栈顶元素intGetTop(seqstack*s，DataType*x){if(s-top==0)return0;*x=s-data[s-top];return1;}四．小结总结本堂课的内容，引出顺序队列，下节课学习顺序队列。和出栈的区别：不改变栈的状态。