栈与队列教学设计

ch2 栈和队列及其应用仅仅认识到栈和队列是两种特殊的线性表是远远不够的，本次实习的目的在于使读者深入了解钱和队列的特性，以便在实际问题背景下灵活运用他们；同时还将巩固对这两种结构的构造方法的理解。

编程技术训练要点有：基本的“任务书“观点及其典型用法(见本实习2。

2)；问题求解的状态表示及其递归算法(2.3，2.4和2.9)；利用栈实现表达式求值的技术(2.5)；事件驱动的模拟方法(2.6 3.8)；以及动态数据结构的实现(2.6，2.7和2.8)。

1. 停车场管理【问题描述】设停车场是一个可停放n 辆汽车的狭长通道，且只有一个大门可供汽车进出。

汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列(大门在最南端，最先到达的第一辆车停放在车场的最北端)，若车场内己停满n 辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开人；当停车场内某辆车要离开时，在它之后进入的车辆必须先退出车场为它让路，待该辆车开出大门外，其他车辆再按原次序进入车场，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。

试为停车场编制按上述要求进行管理的模拟程序。

【基本要求】以桟模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。

每一组输入数据包括三个数据项：汽车“到达“或“离去“信息、汽车牌照号码以及到达或离去的时刻。

对每一组输入数据进行操作后的输出信息为：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车辆离去，则输出汽车在停车场内停留的时间和应交纳的费用(在便道上停留的时间不收费)。

钱以顺序结构实现，队列以链表结构实现。

2. 魔王语言解释【问题描述】有一个魔王总是使用自己的一种非常精练而抽象的语言讲话，没有人能昕得懂，但他的语言是可以逐步解释成人能听懂的语言，因为他的语言是由以下两种形式的规则由人的语言逐步抽象上去的：(1) m βββα 21→(2) θθδθδθδδδθδ1121)( -→n n n在这两种形式中，从左到右均表示解释。

数据结构（C语言版）栈的基本操作及特点说课文稿各位老师、同学们好，现在开始我的说课。

今天我的说课的内容是栈，根据新课标的理念，对于本节课，我将以教什么，怎么教，为什么这样教为思路，从教材分析、教学目标、教学方法、教学过程等几个方面加以说明。

一、教材分析首先谈一谈我对教材的理解，本节课选用的教材是由清华大学出版社出版的高职高专精品课程规划教材《数据结构（C语言版）》，该教材为严蔚敏、吴伟名编著、第三章第一节的内容-栈。

本教材适应了高等职业教育发展的趋势，满足职业院校计算机技术专业的实际需求。

数据结构是高职高专院校各计算机专业学生必修的专业基础课之一，是计算机网络技术、计算机信息管理的核心课程。

通过数据结构的整个教学过程，逐步培养学生分析研究非数值计算问题的数学模型及其操作在计算机中表示和实现的能力，以便为应用涉及的数据选择适当的逻辑结构、存储结构和相应的算法，并初步掌握算法的时间分析和空间分析的技术。

本课程培养学生的数据抽象能力和复杂程序设计的能力，从而为学生以后的学习和工作打下基础。

本课的主要内容是栈的基本操作和及其特点，本课是在学习了线性表之后的进一步学习，是学生将来学习编程的基础，在课程中处于承上启下的地位。

本课对学生了解区分栈和队列的入栈出栈、入队出队起着非常重要的作用。

二、教学目标基于以上对教材的分析，我拟确定如下三个层次的教学目标：1.知识与技能目标：能应用栈的知识解决实际问题；学会多种学习方法，提高抽象思维和举一反三能力。

2.过程与方法目标：将以内容为主线，以教师为主导，学生为主体，职业能力为目标，社会需求为背景，3.情感态度与价值观目标：培养学生热爱科学、勇于探索、勇于创新、团结合作的精神。

三、说重点难点根据教学目标，重点是掌握栈的特点，栈的基本操作的实现算法，我将通过讲授法生动形象的描述栈顶和栈底，使学生形成鲜明的表象和概念，通过演示简单有趣的汉诺塔游戏来提高学生对学习的兴趣，发展观察能力和抽象思维能力来加以突出。

课程设计2 栈和队列课程设计一、1、停车场管理问题描述：停车场是一个能放n辆车的狭长通道，只有一个大门，汽车按到达的先后次序停放。

若车场满了，车要停在门外的便道上等候，一旦有车走，则便道上第一辆车进入。

当停车场中的车离开时，由于通道窄，在它后面的车要先退出，待它走后在依次进入。

汽车离开时按停放时间收费。

基本功能要求：（1）建立三个数据结构分别是：停放、让路、等候。

（2）输入数据模拟管理过程，数据（入或出，车号）。

停车场管理#include<iostream>using namespace std;#define Maxsize 10//停车场共停10辆车#define maxsize 10//等待区共停10辆车typedef int datatype;typedef struct ////////////用栈表示汽车停放和让路{datatype data[Maxsize+1];int top;}Seqstack;void Initstack(Seqstack *&s){s=(Seqstack *)malloc(sizeof(Seqstack));s->top=0;}int push(Seqstack *&s,datatype e){if(s->top==Maxsize)return 0;s->top++;s->data[s->top]=e;return 1;}int pop(Seqstack *&s,datatype &e){if(s->top==0)return 0;e=s->data[s->top];s->top--;return e;}void Dispstack(Seqstack *s)int i;cout<<"车号";for(i=s->top;i>0;i--)cout<<i<<" ";cout<<endl;cout<<"停车时间";for(i=s->top;i>0;i--)cout<<s->data[i]<<" ";cout<<endl;}int Stacklength(Seqstack *s){return(s->top);}////////////////////////////////queue///////////////////////////////////// typedef struct ////////////////////用队列表示汽车等候{datatype data[maxsize+1];int front, rear;}sqqueue;void InitQueue(sqqueue *&q){q=(sqqueue *)malloc(sizeof(sqqueue));q->front=q->rear=0;}int enQueue(sqqueue *&q,datatype e){if((q->rear+1)%maxsize==q->front)return 0;q->rear=(q->rear+1)%maxsize;q->data[q->rear]=e;return 1;}int deQueue(sqqueue *&q,datatype &e){if(q->front==q->rear)return 0;q->front=(q->front+1)%maxsize;e=q->data[q->front];return 1;}int lenqueue(sqqueue *&q)return(q->rear-q->front);}void Disqqueue(sqqueue *q)//输出队列元素{if(q->front==q->rear)cout<<"No element!"<<endl;cout<<"The elemnt in this Sqqueue is:"<<endl;while(q->front!=q->rear){cout<<q->data[q->front+1]<<" ";q->front++;}q->front=0;cout<<endl;}void menu(){cout<<"------------Welcome to our Car Parking-----------------"<<endl;cout<<"1-----------停车"<<endl;cout<<"2-----------离开"<<endl;cout<<"3-----------查看停车场停车情况"<<endl;cout<<"4-----------退出"<<endl;}void current(Seqstack *&s1,sqqueue *&q){cout<<"* * * * * * * * 目前停车场状况* * * * * * * * *"<<endl;cout<<"停车场共"<<Maxsize<<"个车位,"<<"当前停车场共有"<<s1->top<<"辆车.";cout<<"等待区共有"<<lenqueue(q)<<"辆车."<<endl;cout<<"* * * * * * * * * * * * * * * * * * * * * * * "<<endl;}void chargemoney(Seqstack *s)//收费系统，按每小时2元钱{cout<<"收取车号为"<<s->top<<"的车,停车费"<<(s->data[s->top])*2<<"元."<<endl;}int main(){Seqstack *s1,*s2;sqqueue *q;Initstack(s1);Initstack(s2);InitQueue(q);int a[8]={10,20,30,40,50,60,70,80};for(int i=0;i<8;i++)push(s1,a[i]);int In;datatype x,e;current(s1,q);do{menu();cin>>In;switch(In){case 1:int time;cout<<"请输入停放时间(/小时，每小时2元):"<<endl;cin>>time;if(push(s1,time)!=0)cout<<"您的车号是:"<<s1->top<<endl;else{enQueue(q,time);cout<<"停车场已满,请稍等..."<<endl;cout<<"等待车号为"<<q->rear<<endl;}current(s1,q);break;case 2:cout<<"请输入车号:"<<endl;int num;cin>>num;for( i=Stacklength(s1);i>num;i--){pop(s1,x);push(s2,x);} chargemoney(s1);pop(s1,x);for(i=Maxsize;i>num;i--){pop(s2,x);push(s1,x);}if(q->front!=q->rear){deQueue(q,e);push(s1,e);cout<<"等待车号为"<<q->front<<"的车,进入停车场,停车车号为"<<s1->top<<endl;}current(s1,q);break;case 3:Dispstack(s1);break;case 4:break;default:cout<<"error input!"<<endl;}}while(In!=4);return 0;}实验结果截图：。

栈和队列的应用一、问题描述栈和队列是一种常见的数据结构，是两种非常重要的线性结构，也都是线性表，它们是操作受限的的线性表，有顺序栈、链式栈、链式队列和循环队列等形式。

它们广泛应用在各种软件系统中。

本题就是要用这些线性结构先完成基本的应用，如回文，逆置。

再编写一个简易的停车场管理系统，完成对车辆出入库的管理、停车时间的记录和管理费用的结算。

二、基本要求1、选择顺序栈和链队列，完成回文判断、字符串的逆置；2、选择链栈和循环队列，完成回文判断、字符串的逆置；3、运用栈和队列，完成简易停车场管理系统，要求：（1）车辆入库管理及时间记录；（2）车辆出库管理、时间的记录及管理费用的结算；（3）若停车场已满则车辆进入便车道等候。

三、测试数据1、回文判断的测试数据：abcbc@；2、字符串逆置的测试数据：abcdef；3、停车场管理系统测试数据：（1）输入A1、A2、A3实现车辆的入库及对便车道进行测试；（2）输入D1对车辆出库及管理费用结算进行测试。

四、算法思想1、（1）定义顺序栈和链队列及关于它们的基本操作，如定义栈和队列、求栈和队列的长度、入栈出栈、入队列出队列等。

方便后面函数的调用，是实现程序的基石。

（链栈和循环队列也是如此）2、（1）编写函数Palindrome_Test来实现字符串的回文判断，回文是利用了栈的反序输出原则而队列则是顺序输出这个思想来实现的。

往栈和队列输入同一组字符，再将它们一起输出，这样栈输出的字符就与原来的顺序相反了，而队列输出的字符与原来的顺序仍然是一样的，这样比较它们输出的字符是否相等就可以判断是否是回文了。

是则输出1，不是则输出。

(2)编写函数nzhi来实现一段字符串的逆置。

逆置是通过栈的反序输出来实现的。

通过它将队列的一组字符串进行逆置。

将队列的字符串顺序入栈然后出栈。

这样得到的字符串与原来的字符串就逆置过来了。

3、（1）定义车节点的类型及栈和队列的相关操作。

（2）用栈的操作编写一个停车场，队列的操作编写一个便车道。

第3章栈和队列本章教学提要教学重点：栈的定义及其基本运算栈的顺序存储结构队列的定义及基本运算队列的顺序存储结构教学难点：栈的链式存储结构队列的链式存储结构——链队列本章教学内容本章将介绍两种特殊的线性表——栈和队列。

从逻辑结构上看，栈和队列仍是线性表，其特殊性主要是其基本运算有着严格的规定。

由于栈和队列在程序设计中应用广泛，因此对它们单独进行讨论。

3．1 栈栈是规定仅在表尾进行插入和删除运算的线性表，采用的是后进先出的访问方法。

表头叫做栈底，表尾叫做栈顶。

栈的基本运算：1．inistack(s)：初始化操作，设定一个空栈s。

2．push(s,x)：在栈s的顶部插入元素x，简称为入栈。

3．pop(s,*x)：删除并返回栈s的栈顶数据元素，简称为出栈，其中x是返回的栈顶数据元素。

相当于线性表中删除一个数据元素，该运算与push (s,x)为互逆运算。

4．top(s,*x)：取出栈s的栈顶元素x，但不删除栈顶元素。

5．setnull(s)：置s为一个空栈。

6．empty(s)：判定s是否为空栈，若是则返回值为真，否则返回值为假。

3．2 队列队列是一种访问次序是先进先出的线性表队列的基本运算如下：1．addqueue(q,x)：在队列q的队尾插入元素x，称为入队列。

2．delqueue(q,*x)：删除并返回队列q的队头元素，x为返回的队头元素，称为出队列。

3．frontque(q,*x)：取得队列q的队头元素，x为返回的队头元素。

4．setnull(q)：置q为一个空队列。

5．empty(q)：判断q是否为空队列，当q为空时，返回“true”，否则“false”。

队列也是一种操作受限的线性表，它具有线性表的两种存储结构——顺序存储结构和链式存储结构。

教案课程名称：数据结构（C语言版）授课班级：技校二年级学生授课学时：1学时授课章节：第三章栈和队列课型：理论课任课教师：***一下，地铁到终点站后想要再原路返回，向另一个方向出发，地铁是怎样调整方向的呢大家可以先在心里想一下，看是否与我们这节课所介绍的方法一致。

图1 地铁站入站出站再比如我们餐厅中一叠一叠的盘子，如果它们是按1,2,3，……，n的次序往上叠的话，那么使用的次序应该是什么样的必然是依从上往下的次序，，即n，......，3,2,1。

它们遵循的是规律正是本节课要讨论的“栈”的结构特点。

对图1 进行抽象，用地铁的每节车厢表示栈中每个元素这样就得到一个栈的示意图，如图2所示图2 栈的示意图从图2中可以看出第一个进栈的a1为栈底元素，最后一个进栈的an为栈顶元素，进栈和出栈也是同一个方向。

这也是最基本的栈的示意图。

需要同学们熟知。

其实，要解决这个出站问题就离不开我们今天将要学习的进约定a n端为栈顶，a1 端为栈底。

基本操作：InitStack(&S)操作结果：构造一个空栈 S。

DestroyStack(&S)初始条件：栈 S 已存在。

操作结果：栈 S 被销毁。

StackEmpty(S)初始条件：栈 S 已存在。

操作结果：若栈 S 为空栈，则返回TRUE，否则 FALE。

GetTop(S, &e)初始条件：栈 S 已存在且非空。

操作结果：用 e 返回 S 的栈顶元素。

StackLength(S)初始条件：栈 S 已存在。

操作结果：返回 S 的元素个数，即栈的长度。

ClearStack(&S)初始条件：栈 S 已存在。

操作结果：将 S 清为空栈。

Push(&S, e)初始条件：栈 S 已存在。

操作结果：插入元素 e 为新的栈顶元素。

Pop(&S, &e)初始条件：栈 S 已存在且非空。

操作结果：删除 S 的栈顶元素，并用 e 返回其值。