实验三栈和队列
一、目的和要求
1. 掌握栈和队列的逻辑结构定义和各种存储结构的实现。
2. 熟练运用栈和队列的各种存储结构以及各种基本操作。
3. 根据实际问题的需要，选择栈和队列适合的存储结构解决问题。
二、实验环境
1.WindowsXP操作系统；
2.DEV C++、Visual C++6.0语言环境；
三、实验内容
（一）验证性实验（第1、4题为一组；第2、3题为另一组，每个同学选择一组完成。每个小题一个文件夹，所有文件夹打在一个包中，文件名：“学号”+“姓名”，例如: 13131000张三.rar 。提交码为2014DS3，截止时间：2014年12月14日12：00时。）
1．顺序栈的验证
（1）定义一个结构体，描述停车场中车辆的信息。车辆信息包括：车牌号（8个字符）、进场时间（年、月、日、时、分、秒）。用描述车辆信息的结构体作为栈的数据元素类型测试顺序栈的实现。
（2）修改顺序栈的入栈成员函数push(x)，要求当栈满时，执行私有成员函数stackfull( )进行栈满处理。其功能是：动态创建一个比原来的栈数组大一倍的新数组，代替原来的栈数组，原来栈数组中的元素占据新数组的前半部分的位置。
2．链式栈的验证
（1）定义一个结构体，描述停车场中车辆的信息。车辆信息包括：车牌号（8个字符）、进场时间（年、月、日、时、分、秒）。用描述车辆信息的结构体作为栈的数据元素类型测试链式栈的实现。
（2）修改链式栈模板类，用带头结点的单链表作为栈的存储结构。
3．循环队列的验证
（1）定义一个结构体，描述银行排队系统中的客户信息。客户信息包括：客户号、客户类型（企业客户、VIP客户、普通客户）、到达时间（年、月、日、时、分、秒）等。用描述客户信息的结构体作为队列的数据元素类型测试循环队列的实现。
（3）修改教材中循环队列模板类，把成员数据rear改为length表示队列长度，完成修改后各成员函数的实现，并进行测试验证。
4．链队列的验证
（1）定义一个结构体，描述航空订票系统中的航班信息。航班信息包括：航班号、起飞时间（年、月、日、时、分、秒）、起飞地点（8个字符）、抵达时间（年、月、日、时、分、秒）、抵达地点（8个字符）、座位数、空位数、票价等。用描述航班信息的结构体作为队列的数据元素类型测试链队列的实现。
（2）修改教材中的链队列模板类，用一个不带头结点的单循环链表来表示队列（也称为循环链队列），其中只设一个队尾指针rear，不设队头指针，队尾指针rear指向队尾元素结点。
（二）设计性实验（小组完成，每个小组从5-8题中任选一题）
5．设计2个顺序栈共享存储空间的类模板
仿照教材中顺序栈的类模板，实现2个顺序栈存储空间的共享（即一个数组存储2个栈的数据元素，2个栈顶分别设在数组的2端，入栈时栈顶指针向数组中间移动），并进行测试验证。入栈操作push(k,e)有两个参数，其中k（取1或2）表示入栈的编号，e表示入栈的元素；出栈操作pop(k,e)有两个参数，其中k（取1或2）表示出栈的编号，e表示出栈的元素；其它成员函数也作相应修改，需要用参数指明所操作栈的编号。
6．改造循环队列模板类
修改教材中循环队列模板类，增加成员数据tag，原有成员数据不变，改变队空和队满的判断条件，当front == rear && tag == 0表示队空，front == rear && tag == 1表示队满，完成修改后各成员函数的实现，并进行测试验证。
7．设计团队队列模板类
设计一个团队队列的类模板。在团队队列中每个元素属于一个团队，同一团队中的元素在队列中的位置是连续排列的。当一个元素入队时，如果队列中已经有它同团队的元素，则该元素入队并排在它所在团队的最后；否则把该元素排在整个队列的最后。出队操作同一般队列一样，把整个队列的队头元素出队列。
构造团体队列时需要指出团队的数目n，团队编号从0到n-1。入队时需要两个参数，其一表示入队元素值，其二表示所在团队编号。
8．设计双栈队列模板类
设计用2个栈实现1个队列的类模板。入队时，直接把入队元素入1号栈；出队时，先把1号栈中的元素全部倒入2号栈，再从2号栈弹出栈顶元素进行出队，最后把2号栈中剩余元素倒回1号栈。
（三）综合性实验（小组完成，每个小组从9-12中任选一题）
9．停车场管理
[问题描述]
设停车场内只有一个可停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北端），若车场内已停满n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它之后开入的车辆必须先退出车场为它让路，待该辆车开出大门外，其它车辆再按原次序进入车场，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。试为该停车场编制模拟程序进行管理。
[基本要求]
以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码及到达或离去的时刻，对每一组输入数据执行如下操作：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车离去，则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费）。栈以顺序结构实现，队列以链表实现。
[测试数据]
例如：设n=2,输入数据为：（‘A’，1，5），（‘A’，2，10），（‘D’，1，15），（‘A’，3，20），（‘A’，4，25），（‘A’，5，30），（‘D’，2，35），（‘D’，
4，40），（‘E’，0，0）。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码及到达或离去的时刻，其中，‘A’表示到达；‘D’表示离去，‘E’表示输入结束。
[实现提示]
为了给离去的汽车让路需另设一个栈，临时停放为给要离去的汽车让路而从停车场退出来的汽车，也用顺序存储结构实现。输入数据按到达或离去的时刻有序。栈中每个元素表示一辆汽车，包含两个数据项：汽车的牌照号码和进入停车场的时刻。
[选作内容]
（1）两个栈共享空间，思考应开辟数组的空间是多少？
（2）汽车可以有不同种类，则它们的占地面积不同，收费标准也不同，如1辆客车和
1.5辆小汽车的占地面积相同，1辆十轮卡车占地面积相当于3辆小汽车的占地面积。
（3）汽车可以直接从便道上开走，此时排在它前面的汽车要先开走让路，然后再依次排到队尾。
（4）停放在便道上的汽车也收费，收费标准比停放在停车场的车低，请思考如何修改结构以满足这种要求。
10．车厢调度
[问题描述]
有一个“丁”字型铁路调度系统如右图
所示，它由相互垂直的2条铁轨组成，水平
方向的为主铁轨，竖直方向的为辅助铁轨。
辅助铁轨用于对车厢次序进行调整，它在主
铁轨中间，把主铁轨分成左、右两部分。主
铁轨左边的车厢只能从左边开到右边；或者
从主铁轨左边进入辅助铁轨；辅助铁轨上的
车厢只可以进入主铁轨右边。
现在有n 节火车车厢，编号为1、2、…、n ，在主铁轨的左边以任意的顺序排列，要求
通过这个调度系统，在主铁轨的右以1、2、…、n 的次序开出（例如：有5节车厢以5、3、1、2、4的次序进入，要求以1、2、3、4、5的顺序出站）。请编程求解调度过程。
[输入数据]
输入共2行，第1行一个正整数n 表示车厢数目；第2行是1-n 的任意排列表示n 节车厢在主铁轨左边的排列顺序。
[输出数据]
如果能完成调度的话输出调度过程，否则输出调度失败信息。
11．银行排队系统
[问题描述]
随着银行业务量的快速发展，银行柜台业务承受的压力越来越大，排队等待现象屡见不鲜，银行排长队现象成为困扰银行和用户的难题。为了解决这一难题，目前大部分银行的营业厅都使用了取号系统来改善银行窗口排长队的现象，提高银行的服务效率。本题目要求实现银行排队模拟系统，模拟银行取号排队的整个过程，系统功能包括：取号、排队、服务、及管理等。
“丁”字型铁路调度系统
取号：客户进入银行首先从系统的取号机获取客户编号，包括：客户编号、客户类型（企业客户、VIP客户、普通客户）、到达时间（年、月、日、时、分、秒）等。
排队：客户获取客户编号后，如果服务窗口空闲就直接去办理业务，否则进入大厅等待。
服务：当服务窗口完成一笔业务后，如果有客户在大厅等待就根据其到达时间的先后顺序让最先到的客户办理业务。
管理：能根据需要统计服务窗口办理的业务数、统计客户的等待时间、业务办理时间等。[基本要求]
系统中设一个服务窗口、不分区分客户类型，完成银行排队模拟系统的实现，能进行取号、排队、服务、管理等操作。
[测试数据]
系统提供一个菜单，让操作员选择不同的功能，进行不同的操作，能显示在大厅等待的客户信息、已经在服务窗口办完业务的客户信息。
[实现提示]
利用队列分别表示在大厅等待的客户信息和已经办完业务的客户信息。
[选作内容]
（1）在系统中设置多个服务窗口进行工作。
（2）设置服务窗口的类型（企业客户窗口、VIP客户窗口、普通客户窗口），分别为不同的客户人群服务。
（3）设置大厅座位数，当大厅坐满时,再进来的客户只能在过道里等待，大厅有空位时先到过道里等待的客户再进大厅等待。
12．航空订票系统
[问题描述]
随着计算机的普及，计算机的应用已经深入到人们生活的方方面面，航空订票系统就是其中之一。航空订票系统主要包括：航班查询、旅客订票、旅客退票、航班管理等功能。
航班查询：根据旅客提供的出发时间、出发地点和目的地、舱位等要求，查询满足旅客要求的航班信息(航班号、起飞时间、起飞地点、抵达时间、抵达地点、座位数、空位数、票价等)。
旅客订票：旅客提交订票的相关信息（航班号、订票数量，相应人员的姓名和身份证），系统将查询相应航班的已定票情况，若尚有余票，则为客户办理订票手续,为旅客安排座位等，否则询问旅客是否愿意等待退票，如果旅客愿意等待则记录相关信息，否则就退出订票。
航班管理：航空公司可以新增航班，显示航班详细信息{航班号、起飞时间、起飞地点、抵达时间、抵达地点、票价、所有座位安排情况、等待退票的旅客信息（身份证号、姓名、性别、出生日期等）}。
退票处理：旅客若需退票，可提出退票处理。输入退票信息（航班号、身份证号），系统将修改相应的座位安排情况，并判断该航班是否有等待退票的旅客，如果有则安排最早等待的旅客订票。
[基本要求]
系统能进行航班查询、旅客订票、旅客退票、航班管理。
[测试数据]
系统提供一个菜单，让操作员选择不同的功能，进行不同的操作，能显示各航班详细信息、已经完成订票的客户信息、等待退票的客户信息。
[实现提示]
航班信息、航班中已订票的旅客信息可以用线性表表示，各航班的等待退票旅客信息可以用队列实现，一个航班一个已订票的旅客信息表，另一个等待退票旅客信息队列。
[选作内容]
（1）设置旅客等级。当有旅客退票时，则先安排优先级别高（优先级别一样，则安排等待时间长）的旅客订票。
（2）设置航班中座位等级，分别设：头等舱(First class)、商务舱(Business class)和经济舱(Economy class)，完成相应的功能，允许旅客订票后能进行座位等级调换。
实验编号：3四川师大《数据结构》实验报告2016年10月29日 实验三栈和队列及其应用_ 一．实验目的及要求 （1）掌握栈和队列这两种特殊的线性表，熟悉它们的特性，在实际问题背景下灵活运用它们； （2）本实验训练的要点是“栈”的观点及其典型用法； （3）掌握问题求解的状态表示及其递归算法，以及由递归程序到非递归程序的转化方法。 二．实验内容 （1）编程实现栈在两种存储结构中的基本操作（栈的初始化、判栈空、入栈、出栈等）； （2）应用栈的基本操作，实现数制转换（任意进制）； （3）编程实现队列在两种存储结构中的基本操作（队列的初始化、判队列空、入队列、出队列）； （4）利用栈实现任一个表达式中的语法检查（括号的匹配）。 （5）利用栈实现表达式的求值。 注：（1）～（3）必做，（4）～（5）选做。 三．主要仪器设备及软件 （1）PC机 （2）Dev C++ ,Visual C++, VS2010等 四．实验主要流程、基本操作或核心代码、算法片段（该部分如不够填写，请另加附页）（1）编程实现栈在两种存储结构中的基本操作（栈的初始化、判栈空、入栈、出栈等）； A.顺序储存： 代码部分： 栈" << endl; cout << " 2.出栈" << endl; cout << " 3.判栈空" << endl; cout << " 4.返回栈顶部数据" << endl; cout << " 5.栈长" << endl; cout << " 0.退出系统" << endl;
cout << "你的选择是：" ; } 链式储存： 代码部分： 栈"<
第3章栈和队列 一、选择题 1.栈结构通常采用的两种存储结构是（A ）。 A、顺序存储结构和链表存储结构 B、散列和索引方式 C、链表存储结构和数组 D、线性链表结构和非线性存储结构 2.设栈ST 用顺序存储结构表示，则栈ST 为空的条件是（ B ） A、ST.top-ST.base<>0 B、ST.top-ST.base==0 C、ST.top-ST.base<>n D、ST.top-ST.base==n 3.向一个栈顶指针为HS 的链栈中插入一个s 结点时，则执行（ C ） A、HS->next=s; B、s->next=HS->next；HS->next=s; C、s->next=HS；HS=s; D、s->next=HS；HS=HS->next; 4.从一个栈顶指针为HS 的链栈中删除一个结点，用x 保存被删除结点的值，则执行（ C） A 、x=HS；HS=HS->next; B 、HS=HS->next；x=HS->data; C 、x=HS->data；HS=HS->next; D 、s->next=Hs；Hs=HS->next; 5.表达式a*(b+c)-d 的后缀表达式为（ B ） A、abcdd+- B、abc+*d- C、abc*+d- D、-+*abcd 6.中缀表达式A-（B+C/D）*E 的后缀形式是（ D ） A、AB-C+D/E* B、ABC+D/E* C、ABCD/E*+- D、ABCD/+E*- 7.一个队列的入列序列是1，2，3，4，则队列的输出序列是（ B ） A、4，3，2，1 B、1，2，3，4 C、1，4，3，2 D、3，2，4，1 8.循环队列SQ 采用数组空间SQ.base[0,n-1]存放其元素值，已知其头尾指针分别是front 和rear，则判定此循环队列为空的条件是（） A、Q.rear-Q.front==n B、Q.rear-Q.front-1==n C、Q.front==Q.rear D、Q.front==Q.rear+1 9.循环队列SQ 采用数组空间SQ.base[0,n-1]存放其元素值，已知其头尾指针分别是front 和rear，则判定此循环队列为满的条件是（） A、Q.front==Q.rear B、Q.front!=Q.rear C、Q.front==(Q.rear+1)%n D、Q.front!=(Q.rear+1)%n 10.若在一个大小为6 的数组上实现循环队列，且当前rear 和front 的值分别为0 和3，当从 队列中删除一个元素，再加入两个元素后，rear 和front 的值分别为（） A、1，5 B、2, 4 C、4，2 D、5，1 11.用单链表表示的链式队列的队头在链表的（）位置 A、链头 B、链尾 C、链中 12.判定一个链队列Q（最多元素为n 个）为空的条件是（） A、Q.front==Q.rear B、Q.front!=Q.rear C、Q.front==(Q.rear+1)%n D、Q.front!=(Q.rear+1)%n 13.在链队列Q 中，插入s 所指结点需顺序执行的指令是（） A 、Q.front->next=s；f=s; B 、Q.rear->next=s；Q.rear=s;
贵州大学实验报告 学院：计信学院专业：网络工程班级：091班姓名XXX 学号XXXXXXXXX 实验组 5 实验时间2011.12.02 指导教师XXXXX 成绩 实验项目名称 队列的实现 实 验目的1．掌握队列的思想及其存储实现。2．掌握队列的常见算法的程序实现。 实验原理1.根据实验内容编程，上机调试、得出正确的运行程序。 2. 编译运行程序，观察运行情况和输出结果。 3. 写出实验报告（包括源程序和运行结果）。 实验内容 1．采用链式存储实现队列的初始化、入队、出队操作。 2．采用顺序存储实现循环队列的初始化、入队、出队操作。 3．在主函数中设计一个简单的菜单，分别测试上述算法。
实验数据及其步骤链式存储队列： #include 实验报告 课程名称_______数据结构实验__________________ 实验项目___ 栈和队列的基本操作与应用____ 实验仪器_____________________________________ 系别 ___ 计算机学院_______________ 专业 __________________ 班级/学号______ _________ 学生姓名_____________________ __ 实验日期__________________ 成绩_______________________ 指导教师____ __________________ 一、实验内容： 本次实验主要内容是表达式求值，主要通过栈和队列来编写程序，需要实现整数运算其中需要实现的功能有加减乘除以及括号的 运用，其中包含优先级的判断。 二、设计思想 1.优先级中加减、乘除、小括号、以及其他可以分组讨论优先 级 2.优先级关系用“>”“<”“=”来表示三种关系 3.为实现运算符优先使用两个栈：OPTR 运算符栈与OPND操作 符栈 4.运用入栈出栈优先级比较等方式完成运算 三、主要算法框架 1.建立两个栈InitStack(&OPTR); InitStack(&OPND); 2.Push“#”到 OPTR 3.判断优先级做入栈出栈操作 If“<” Push(&OPTR, c); If“=” Pop(&OPTR, &x) If“>” Pop(&OPTR, &theta); Pop(&OPND, &b); Pop(&OPND, &a); Push(&OPND, Operate(a, theta, b)); 四、调试报告 遇到的问题与解决 1.C语言不支持取地址符，用*S代替&S来编写代码 2.一开始没有计算多位数的功能只能计算一位数，在几个中间 不含运算符的数字中间做p = p*10+c运算。代码如下：p = p * 10 + c - '0'; c = getchar(); if (In(c)) { Push(&OPND, p); p = 0; } 主要算法改进设想： 1.可以用数组储存优先级 2.可以用C++编写，C++支持取地址符&。 五、实验总结 实验二堆栈和队列 实验目的： 1.熟悉栈这种特殊线性结构的特性； 2.熟练并掌握栈在顺序存储结构和链表存储结构下的基本运算； 3.熟悉队列这种特殊线性结构的特性； 3.熟练掌握队列在链表存储结构下的基本运算。 实验原理： 堆栈顺序存储结构下的基本算法； 堆栈链式存储结构下的基本算法； 队列顺序存储结构下的基本算法； 队列链式存储结构下的基本算法； 实验内容： 第一题链式堆栈设计。要求 （1）用链式堆栈设计实现堆栈，堆栈的操作集合要求包括：初始化StackInitiate（S）,非空否StackNotEmpty(S)，入栈StackiPush(S,x),出栈StackPop（S,d）,取栈顶数据元素StackTop(S,d); （2）设计一个主函数对链式堆栈进行测试。测试方法为：依次把数据元素1，2，3，4，5入栈，然后出栈并在屏幕上显示出栈的数据元素； （3）定义数据元素的数据类型为如下形式的结构体， Typedef struct { char taskName[10]; int taskNo; }DataType; 首先设计一个包含5个数据元素的测试数据，然后设计一个主函数对链式堆栈进行测试，测试方法为：依次吧5个数据元素入栈，然后出栈并在屏幕上显示出栈的数据元素。 第二题对顺序循环队列，常规的设计方法是使用対尾指针和对头指针，对尾指针用于指示当前的対尾位置下标，对头指针用于指示当前的対头位置下标。现要求： （1）设计一个使用对头指针和计数器的顺序循环队列抽象数据类型，其中操作包括：初始化，入队列，出队列，取对头元素和判断队列是否为空； （2）编写主函数进行测试。 程序代码： 第一题： （1）源程序"LinStack.h"如下： #define NULL 0 typedef struct snode { DataType data; struct snode *next; } LSNode; /*（1）初始化StackInitiate(LSNode ** head) */ void StackInitiate(LSNode ** head) /*初始化带头结点链式堆栈*/ 实验二栈、队列的实现及应用 实验课程名：数据结构与算法 专业班级：学号：： /*构造空顺序栈*/ int InitStack(SqStack *S) //InitStack() sub-function { S->base = (SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if (!S->base) { printf("分配空间失败!\n"); return (ERROR); } S->top = S->base; S->stacksize = STACK_INIT_SIZE; printf("栈初始化成功！\n"); return (OK); } //InitStack() end /*取顺序栈顶元素*/ int GetTop(SqStack *S, SElemType *e) //GetTop() sub-function { if (S->top == S->base) { printf("栈为空!\n"); //if empty SqStack return (ERROR); } *e = *(S->top - 1); return (OK); } //GetTop() end /*将元素压入顺序栈*/ int Push(SqStack *S) //Push() sub-function { SElemType e; if (S->top - S->base>S->stacksize) { S->base = (SElemType *)realloc(S->base, (S->stacksize + STACKINCREMENT*sizeof(SElemType))); if (!S->base) { printf("存储空间分配失败!\n"); return (ERROR); } S->top = S->base + S->stacksize; S->stacksize += STACKINCREMENT; } fflush(stdin);//清除输入缓冲区，否则原来的输入会默认送给变量x 第三章栈和队列试题 一、单项选择题 1.栈的插入和删除操作在（）进行。 A. 栈顶 B. 栈底 C. 任意位置 D. 指定位置 2.当利用大小为n的数组顺序存储一个栈时，假定用top==n表示栈空，则向这个栈插入一个元素时， 首先应执行（）语句修改top指针。 A. top++; B. top--; C. top = 0; D. top; 3.若让元素1,2,3依次进栈，则出栈次序不可能出现（）种情况。 A. 3, 2, 1 B. 2, 1, 3 C. 3, 1, 2 D. 1, 3, 2 4.在一个顺序存储的循环队列中，队头指针指向队头元素的（）位置。 A. 前一个 B. 后一个 C. 当前 D. 后面 5.当利用大小为n的数组顺序存储一个队列时，该队列的最大长度为（）。 A. n-2 B. n-1 C. n D. n+1 6.从一个顺序存储的循环队列中删除一个元素时，需要（）。 A. 队头指针加一 B. 队头指针减一 C. 取出队头指针所指的元素 D. 取出队尾指针所指的元素 7.假定一个顺序存储的循环队列的队头和队尾指针分别为front和rear，则判断队空的条件为（）。 A. front+1 == rear B. rear+1 == front C. front == 0 D. front == rear 8.假定一个链式队列的队头和队尾指针分别为front和rear，则判断队空的条件为（）。 A. front == rear B. front != NULL C. rear != NULL D. front == NULL 9.设链式栈中结点的结构为（data, link），且top是指向栈顶的指针。若想在链式栈的栈顶插入一 个由指针s所指的结点，则应执行操作（）。 A. top->link = s; B.s->link = top->link; top->link = s; C. s->link = top; top = s; D. s->link = top; top = top->link; 10.设链式栈中结点的结构为（data, link），且top是指向栈顶的指针。若想摘除链式栈的栈顶结点， 并将被摘除结点的值保存到x中，则应执行操作（）。 A. x = top->data; top = top->link; B. top = top->link; x = top->data; C. x = top; top = top->link; D. x = top->data; 11.设循环队列的结构是 #define MaxSize 100 typedef int ElemType; 数据结构练习第三章栈和队列 一、选择题 1．栈和队列的共同特点是( )。 A.只允许在端点处插入和删除元素 B.都是先进后出 C.都是先进先出 D.没有共同点 2．向顺序栈中压入新元素时，应当（）。 A．先移动栈顶指针，再存入元素 B．先存入元素，再移动栈顶指针C．先后次序无关紧要 D．同时进行 3．允许对队列进行的操作有( )。 A. 对队列中的元素排序 B. 取出最近进队的元素 C. 在队头元素之前插入元素 D. 删除队头元素 4．用链接方式存储的队列，在进行插入运算时( ). A. 仅修改头指针 B. 头、尾指针都要修改 C. 仅修改尾指针 D.头、尾指针可能都要修改 5．设用链表作为栈的存储结构则退栈操作（）。 A. 必须判别栈是否为满 B. 必须判别栈是否为空 C. 判别栈元素的类型 D.对栈不作任何判别 6．设指针变量front表示链式队列的队头指针，指针变量rear表示链式队列的队尾指针，指针变量s指向将要入队列的结点X，则入队列的操作序列为（）。 A.front->next=s；front=s； B. s->next=rear；rear=s； C. rear->next=s；rear=s； D. s->next=front；front=s； 7．设指针变量top指向当前链式栈的栈顶，则删除栈顶元素的操作序列为（）。 A.top=top+1; B. top=top-1; C. top->next=top; D. top=top->next; 8．队列是一种（）的线性表。 A. 先进先出 B. 先进后出 C. 只能插入 D. 只能删除 9．设输入序列1、2、3、…、n经过栈作用后，输出序列中的第一个元素是n，则输出序列中的第i个输出元素是（）。 A. n-i B. n-1-i C. n+l -i D.不能确定 10．设输入序列为1、2、3、4、5、6，则通过栈的作用后可以得到的输出序列为（）。 A. 5，3，4，6，1，2 B. 3，2，5，6，4，1 C. 3，1，2，5，4，6 D. 1，5，4，6，2，3 11．队列的删除操作是在（）进行。 A．队首 B．队尾 C．队前 D．队后 12．当利用大小为N 的数组顺序存储一个栈时，假定用top = = N表示栈空，则退栈时，用（）语句修改top指针。 A．top++; B．top=0; C．top--; D．top=N; 13．队列的插入操作是在（）进行。 ?、实验目的 1. 了解队列的特性。 2. 掌握队列的顺序表示和实现。 3. 掌握队列的链式表示和实现。 1、实验内容 实验3. 3队列的顺序表示和实现 编写一个程序实现顺序队列的各种基本运算（采用循环队列）， 主程序，完成如下功能： ⑴ 初始化队列。 ⑵ 建立顺序队列。 ⑶ 入队。 ⑷ 岀队。 (5) 判断队列是否为空。 ⑹ 取队头元素。 (7) 遍历队列。 实验3.4队列的链式表示和实现 编写一个程序实现链队列的各种基本运算，并在此基础上设计 能： (1) 初始化并建立链队列 ⑵ 入链队列。 ⑶ 岀链队列。 ⑷ 遍历链队列。 #i nclude int Ini tQueue(SqQueue &Q) { Q.base=(i nt*)malloc(MAXQSIZE*sizeof(i nt)); if(!Q.base)exit(O); Q.fro nt=Q.rear=0; return 0; }//初始化顺序队列 int QueueLe ngth(SqQueue Q) { int i; i=(Q.rear-Q.fro nt+MAXQSIZE)%MAXQSIZE; printf(“队列长度％5d\n",i); if(i)printf(" 队列非空“)； else printf(" 队列为空"); return 0; }//判断队列是否为空 int En Queue(SqQueue &Q,i nt e) { if((Q.rea 叶1)%MAXQSIZE==Q.fro nt)return 0; Q.base[Q.rear]=e; Q.rear=(Q.rea r+1)%MAXQSIZE; return 0; }//将元素e入队 int DeQueue(SqQueue & Q,i nt e) { if(Q.fro nt==Q.rear)return 0; e=Q.base[Q.fro nt]; prin tf("%5d\n",e); Q.fron t=(Q.fr on t+1)%MAXQSIZE; return 0; }// 删除元素e并返回其值 南京信息工程大学实验（实习）报告 实验（实习）名称栈和队列日期2017.11.8 得分指导老师崔萌萌 系计算机系专业软件工程年级2016 班次(1) 姓名学号 一、实验目的 1、学习栈的顺序存储和实现，会进行栈的基本操作 2、掌握递归 3、学习队列的顺序存储、链式存储，会进行队列的基本操作 4、掌握循环队列的表示和基本操作 二、实验内容 1、用栈解决以下问题： （1）对于输入的任意一个非负十进制数，显示输出与其等值的八进制数，写出程序。（2）表达式求值，写出程序。 2、用递归写出以下程序： （1）求n！。 （2）汉诺塔程序，并截图显示3、4、5个盘子的移动步骤,写出移动6个盘子的移动次数。 3、编程实现：（1）创建队列，将asdfghjkl依次入队。（2）将队列asdfghjkl依次出队。 4、编程实现创建一个最多6个元素的循环队列、将ABCDEF依次入队，判断循环队列是否队满。 三、实验步骤 1.栈的使用 1.1 用栈实现进制的转换： 代码如下： #include printf("转换为%d进制： ",radix); while(n) { s.push(n%radix); n /= radix; } while(!s.empty()) { //非空 printf("%d",s.top()); s.pop(); } printf("\n"); return 0; } 运行结果如下： 2.2 求表达式的值 代码如下： #include 百度文库-让每个人平等地提升自我 实验二栈、队列的实现及应用 实验课程名：数据结构与算法 专业班级：_ 学号：__________ 姓名： _ 实验时间： ____ 实验地点：指导教师：冯珊__________ 一、实验目的 1掌握栈和队列的顺序存储结构和链式存储结构，以便在实际背景下灵活运用。 2、掌握栈和队列的特点，即先进后出与先进先出的原则。 3、掌握栈和队列的基本操作实现方法。 /*顺序栈的存储类型*/ typedef struct 1 2 3 4 5远 兀 1 一 7U- 元 谴 段 囑 :> o 1 2 3 R * 元 元 栈 書 t 出 一 ^ 零 遐 次 :± 谨 虚 1 2 3 ^ 5 I B D 认戯握结IVl 匚on&ol eAp pli cation!\[>ebu g\Con 5 o-leApp li cation 1 .exe :1 刖人操作谊睪代码(05):2 : h E s 选 的 操 一 兀 一 b 一 丁 一 丁 栈 ? 遐 次 嘆 區 1 2 3 4 5 5 ^ 元 元 栈 S 退 、 灵 岀 祓 S I ■ i 9 I I I i 主 至 ..T' 一 兀 元 栈 ￡ 1 2 3 4 5 \Z 百度文库 -让每个人平等地提升自我 P入操隹选择代码（0-5>:4 派元素的是 ; 栈 化 出 取 示 艮 i元一一 选 的 操 元 -> 入 中 >c 1- 苴翻（05）: 5 栈 化 亍 1 2 元 元 Is 务一（2）:完成下列程序，该程序实现栈的链式存储结构，构建链栈（栈中的元素依次为China , Japan, France，India ，Australia ），依次进行进栈和出栈操作，判断栈空和栈满操作，返回栈顶元素操作。 要求生成链栈时，从键盘上读取数据元素。 （1）源代码：#i nclude<> #in clude<> #in clude<> # define OK 1 # define ERROR 0 typedef char DataType; /*链式栈的存储类型*/ typedef struct SNode 《数据结构》课程实验报告 一、实验目的和要求 （1）熟悉C语言的上机环境，进一步掌握C语言的结构特点。 （2）掌握队列的顺序表示和实现。 二、实验环境 Windows7 ,VC 三、实验内容及实施 实验三：队列 【实验要求】 构建一个循环队列, 实现下列操作 1、初始化队列(清空)； 2、入队； 3、出队; 4、求队列长度； 5、判断队列是否为空； 【源程序】 #include Q.base=new int[MAXSIZE]; Q.front=Q.rear=0; return OK; }//队列的初始化 int EnQueue(SqQueue &Q,int e) { if((Q.rear+1)%MAXSIZE==Q.front) return ERROR; Q.base[Q.rear]=e; Q.rear=(Q.rear+1)%MAXSIZE; return OK; }//队列的入队 int DeQueue(SqQueue &Q,int &e) { if(Q.front==Q.rear) return ERROR; e=Q.base[Q.front]; Q.front=(Q.front+1)%MAXSIZE; return OK; }//队列的出队 int QueueLength(SqQueue &Q) { int i; i=(Q.rear-Q.front+MAXSIZE)%MAXSIZE; return i; }//求队列长度 void JuQueue(SqQueue &Q) { if(Q.rear==Q.front) printf("队列为空"); else printf("队列不为空"); }//判断队列是否为空 void QueueTraverse(SqQueue &Q) 实验二栈与队列操作 实验目的： (1)理解栈与队列的结构特征和运算特征，以便在实际问题背景下灵活运用。 (2)了解复杂问题的递归算法设计。 本次实验中，下列实验项目选做一。 1、顺序栈的基本操作 [问题描述] 设计算法，实现顺序栈的各种基本操作 [基本要求] （1）初始化栈s。 （2）从键盘输入10个字符以$结束，建立顺序栈。 （3）从键盘输入1个元素，执行入栈操作。 （4）将栈顶元素出栈。 （5）判断栈是否为空。 （6）输出从栈顶到栈底元素。 要求程序通过一个主菜单进行控制，在主菜单界面通过选择菜单项的序号来调用各功能函数。 2、链栈的基本操作 [问题描述] 设计算法，实现链栈的各种基本操作 [基本要求] （1）初始化栈s。 （2）从键盘输入10个字符以$结束，建立带头结点的链栈。 （3）从键盘输入1个元素，执行入栈操作。 （4）完成出栈操作。 （5）判断栈是否为空。 （6）输出从栈顶到栈底元素。 （7）输出链栈的长度。 要求程序通过一个主菜单进行控制，在主菜单界面通过选择菜单项的序号来调用各功能函数。 3、循环队列的基本操作 [问题描述] 设计算法，实现循环顺序队列的建立、入队、出队等操作。 [基本要求] （1）从键盘输入10个字符以$结束，建立循环队列，并显示结果。 （2）从键盘输入1个元素，执行入队操作，并显示结果。 （3）将队头元素出队，并显示结果。 （4）要求程序通过一个主菜单进行控制，在主菜单界面通过选择菜单项的序号来调用各功能函数。 4、只用尾指针表示的循环链表队列的综合操作 [问题描述] 假设以带头结点的的循环链表表示队列，并且只设一个指针指向队尾元素的结点（注意不设头指针），试编写队列初始化、入队、出队函数。 [基本要求及提示] （1）首先定义链表结点类型。 （2）编写带头结点的循环链表的初始化函数，只用尾指针表示。 （3）编写入队函数、出队函数。 （4）在主函数中编写菜单（1.初始化；2.入队；3.出队；4.退出），调用上述功能函数。 5、用标志域表示队空队满状态的循环队列的综合操作 [问题描述] 要求循环队列不损失一个空间全部都得到利用，设置一个标志域tag，以0和1来区分当队头与队尾指针相同时队列状态的空和满，试编写与此结构相对应的入队和出队操作。 [基本要求及提示] （1）教材中为区分当队头与队尾指针相同时队列状态的空和满，以牺牲一个空间的代价来实现的，空：Q->front==Q->rear,满：（Q->rear+1）%MAXSIZE==Q->front。 （2）本题不损失一个空间全部都得到利用，为此如下定义循环队列类型： Typedef struct { QueueElementType element[MAXSIZE]; int front; int rear; int tag; }SeqQueue; 此时，循环队列空和满的条件分别为： Q->front==Q->rear&&tag==0 和 Q->front==Q->rear&&tag==1 （3）编写入队函数、出队函数。 （4）在主函数中编写菜单（1.入队；2.出队；3.退出），调用上述功能函数。 6、利用辅助数组进行栈的逆置 [问题描述] 利用辅助栈将栈中的元素逆置。 [基本要求及提示] 在主函数中编写菜单（1.入栈；2.出栈；3.逆置；4.退出）调试运行程序。 7、利用辅助栈进行队列的逆置 [问题描述] 利用辅助栈进行队列元素逆置。 [基本要求及提示] 在主函数中编写菜单（1.入队；2.出队；3.逆置；4.退出）调试运行程序。 8、Hanoi塔问题 习题三栈和队列 一单项选择题 1. 在作进栈运算时,应先判别栈是否(① ),在作退栈运算时应先判别栈是否(② )。当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为(③ )。 ①, ②: A. 空 B. 满 C. 上溢 D. 下溢 ③: A. n-1 B. n C. n+1 D. n/2 2．若已知一个栈的进栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，...，pn，若p1＝3，则p2为( )。 A 可能是2 B 一定是2 C 可能是1 D 一定是1 3. 有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（） A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 6 4.设有一顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素出栈的顺序是s2,s3,s4, s6, s5,s1,则栈的容量至少应该是（） A.2 B. 3 C. 5 D.6 5. 若栈采用顺序存储方式存储，现两栈共享空间V[1..m]，top[i]代表第i个栈( i =1,2)栈顶，栈1的底在v[1]，栈2的底在V[m]，则栈满的条件是（）。 A. |top[2]-top[1]|=0 B. top[1]+1=top[2] C. top[1]+top[2]=m D. top[1]=top[2] 6. 执行完下列语句段后，i值为：（） int f(int x) { return ((x>0) ? x* f(x-1):2);} int i ; i =f(f(1)); A．2 B. 4 C. 8 D. 无限递归 7. 表达式3* 2^(4+2*2-6*3)-5求值过程中当扫描到6时，对象栈和算符栈为（），其中^为乘幂。 A. 3,2,4,1,1；(*^(+*- B. 3,2,8；(*^- C. 3,2,4,2,2；(*^(- D. 3,2,8；(*^(- 8. 用链接方式存储的队列，在进行删除运算时（）。 A. 仅修改头指针 B. 仅修改尾指针 C. 头、尾指针都要修改 D. 头、尾指针可能都要修改 9. 递归过程或函数调用时，处理参数及返回地址，要用一种称为（）的数据结构。 A．队列 B．多维数组 C．栈 D. 线性表 10．设C语言数组Data[m+1]作为循环队列SQ的存储空间， front为队头指针，rear为队尾指针，则执行出队操作的语句为（） A.front=front+1 B. front=（front+1）% m C.rear=(rear+1)%(m+1) D. front=(front+1)%(m+1) 11.循环队列的队满条件为 ( ) A. (sq.rear+1) % maxsize ==(sq.front+1) % maxsize; B. (sq.front+1) % maxsize ==sq.rear C. (sq.rear+1) % maxsize ==sq.front D.sq.rear ==sq.front 实验4 病人看病模拟程序 【问题描述】 编写一个程序，反映病人到医院看病，排队看医生的情况。在病人排队的过程中，主要重复两件事： （1）病人到达诊室，将病历本交给护士，排到等待队列中候诊。（2）护士从等待队列中取出下一位病人的病历，该病人进入诊室就诊。 要求模拟病人等待就诊这一过程。程序采用菜单方式，其选项及功能说明如下： （1）排队――输入排队病人的病历号，加入病人排队队列中。（2）就诊――病人排队队列中最前面的病人就诊，并将其从队列中删除； （3）查看排队――从对首到队尾列出所有的排队病人的病历号；（4）不再排队，余下一次就诊――从对首到队尾列出所有的排队病人的病历号，并退出运行； （5）下班――退出运行； #include typedef struct { QNode *front,*rear; }QuType; //链队类型 void seedoctor() //模拟病人看病的过程 { int sel,flag=1,find,no; QuType *qu; QNode *p; qu=(QuType *)malloc(sizeof(QuType)); //创建空队 qu->front=qu->rear=NULL; while(flag==1) { printf("1:排队 2：就诊 3：查看排队 4：不再排队，余下依次就诊 5：下班请选择："); scanf("%d",&sel); switch(sel) { case 1: printf(">>输入病历号："); do { scanf("%d",&no); find=0; 实验二栈和队列 一、实验目的 1. 掌握栈的顺序表示和实现 2. 掌握队列的链式表示和实现 二、实验内容 1. 编写一个程序实现顺序栈的各种基本运算。 2. 实现队列的链式表示和实现。 三、实验步骤 1. 初始化顺序栈 2. 插入元素 3. 删除栈顶元素 4. 取栈顶元素 5. 遍历顺序栈 6. 置空顺序栈 7. 初始化并建立链队列 8. 入链队列 9. 出链队列 10. 遍历链队列 四、实现提示 1. /*定义顺序栈的存储结构*/ typedef struct { ElemType stack[MAXNUM]; int top; }SqStack; /*初始化顺序栈函数*/ void InitStack(SqStack *p) {q=(SqStack*)malloc(sizeof(SqStack) /*申请空间*/) /*入栈函数*/ void Push(SqStack *p,ElemType x) {if(p->top 注意事项： 在磁盘上创建一个目录，专门用于存储数据结构实验的程序。因为机房机器有还原卡，请同学们将文件夹建立在最后一个盘中，以学号为文件夹名。 实验四队列的表示与操作 一、实验目的 1。掌握队列的掌握队列的类型定义,掌握循环队列的表示与实现方法 2．掌握队列的基本操作：判空、元素入队、出队，删除队头元素 基本操作： InitQueue()构造一个空队列Q QueueEmpty(Q) 判断队列是否为空 QueueLenght(Q)返回队列Q的元素个数，即队列的长度 GetHead(Q,&e)取队列Q的队头元素，并用e返回 InQueue(&Q,e) 将元素e入队列 OutQueue(&Q,&e)删除非空队列Q的队头元素，并用e返回其值 二、实验要求 1．认真阅读和掌握本实验的算法。 2．上机将本算法实现。 3．将程序补完整，打印出程序的运行结果，并结合程序进行分析。 三、实验内容 程序：设计一个循环队列的顺序表示和实现的演示程序 参考程序如下： #include 《数据结构》课程实验报告 实验名称栈和队列实验序号实验日期 姓名院系班级学号 专业指导教师成绩 教师评语 一、实验目的和要求 (1)理解栈和队列的特征以及它们之间的差异，知道在何时使用那种数据结构。 (2)重点掌握在顺序栈上和链栈上实现栈的基本运算算法，注意栈满和栈空的条件。 (3)重点掌握在顺序队上和链队上实现队列的基本运算算法，注意循环队队列满和队空的条件。 (4)灵活运用栈和队列这两种数据结构解决一些综合应用问题。 二、实验项目摘要 编写一个程序algo3-1.cpp，实现顺序栈的各种基本运算，并在此基础上设计一个主程序并完成如下功能：（1）初始化栈s； （2）判断栈s是否非空； （3）依次进栈元素a,b,c,d,e； （4）判断栈s是否非空； （5）输出栈长度； （6）输出从栈顶到栈底元素； （7）输出出栈序列； （8）判断栈s是否非空； （9）释放栈。 编写一个程序algo3-3.cpp，实现顺序环形队列的各种基本运算，并在此基础上设计一个主程序并完成如下功能： （1）初始化队列q； （2）判断队列q是否非空； （3）依次进队列a,b,c； （4）出队一个元素，输出该元素； （5）输出队列q的元素个数； （6）依次进队列元素d,e,f； （7）输出队列q的元素个数； （8）输出出队序列； （9）释放队列。 三、实验预习内容 栈的顺序存储结构及其基本运算实现（初始化栈，销毁栈，求栈的长度，判断栈是否为空，进栈，取栈顶元素，显示栈中元素） 队列的顺序存储结构及其基本运算实现（初始化队列，销毁队列，判断队列是否为空，入队列，出队列） 三、实验结果与分析 3-1 #define maxsize 100 #include 数据结构实验二-栈和队列的基本操作与应用
数据结构堆栈与队列实验报告
实验二_栈、队列地实现与应用
数据结构第三章栈和队列3习题
数据结构练习 第三章 栈和队列
数据结构实验——队列(附程序)
数据结构栈和队列实验报告.doc
实验二栈队列的实现及应用
数据结构-队列实验报告
实验二 栈与队列操作实验题目
数据结构栈和队列习题及答案
数据结构实验4队列
数据结构栈和队列
数据结构实验4 队列的表示与操作
数据结构栈和队列实验报告
相关主题
文本预览