数据结构-实验3 栈和队列

第1页共6页实验（实训）报告项目名称实验3栈和队列所属课程名称数据结构项目类型验证性实验(实训)日期2013.10.班级学号姓名指导教师朱凌浙江财经学院教务处制一、实验（实训）概述：【实验目的】掌握栈的两种存储实现方法：顺序栈和链式栈；掌握STL栈的使用方法，能用栈求解问题。掌握队列的两种存储实现方法：顺序队列和链式队列；掌握STL队列的使用方法，能用队列求解问题。【实验要求】新建文件夹，并命名为“学号姓名实验1数据结构概论”，如“0901042001**×××实验1数据结构概论”（**和×××部分用自己的学号和姓名替换），该文件夹用于存放实验程序和实验报告。实验报告完成后，请将该文件夹压缩后提交，压缩前请删除各程序的debug目录。认真记录实验过程及结果，认真回答实验报告中的问题。及时提交实验报告。【实施环境】（使用的材料、设备、软件）VisualC++6.0注意：所有回答的内容用红色字体标明！！！二、实验（实训）内容：实验任务一栈第1题回答以下问题(1)在日常生活中，除课件中提到的例子（超市存放购物车的轨道、折反型的火车站）外，还有哪些事物“处理数据”的方式是按照栈的方式进行的。回答：(2)请根据你的理解，回答在什么情况下可以用栈来存储数据？回答：(3)栈具有后进先出（LIFO）的特性，是因为它使用的存储结构具有这样的特性吗？还是因为其他原因？原因又是什么？回答：第2题栈的应用－计算表达式的值(1)请将下列中缀表达式转换成等值的后缀表达式。(2+3)×(19-7)+(6–9)–66/375–23+(19–11)/(5–1)–15回答：(2)求解(1)中得到的后缀表达式，要求将求解过程列出来。回答：第3题顺序栈请写出顺序栈的实现的主要代码，分别粘贴在下方。回答：第4题链式栈请写出链式栈的实现的主要代码，分别粘贴在下方。回答：第5题掌握STL栈stack的使用。(1)请写出阶乘函数的递归实现。（主要代码粘贴在下方）回答：(2)请写出阶乘函数的迭代实现。（主要代码粘贴在下方）回答：(2)请写出阶乘函数的非递归实现，要求使用STL栈stack，及其成员函数（主要代码粘贴在下方）回答：第6题掌握STL栈stack的使用。请编写一个程序，测试STL栈stack的使用，要求用到stack的成员函数。编写一个代码段，弹出栈中所有结点，用STL中的栈实现。stack<int>S;//假设栈里已经有结点了请将代码粘贴在下方。回答：实验任务二队列第1题回答以下问题(1)请根据你的理解，回答在什么情况下可以用队列来存储数据？回答：(2)本章介绍了四种线性表，分别是顺序表、单链表、栈和队列，请总结这四种线性表的特点（包括优缺点、适用范围）。回答：第2题顺序队列请写出顺序队列的实现的主要代码，分别粘贴在下方。回答：第3题链式队列请写出链式队列的实现的主要代码，分别粘贴在下方。回答：第4题掌握STL队列queue的使用。请用STL的优先级队列模拟Windows操作系统的消息队列。每个消息用一个字符串表示，为“Keyboard”、“Mouse”、“Timer”，分别表示键盘(注意有不同的键盘消息，所以不同的Keyboard消息优先级允许不一样)、鼠标和定时器消息。每个消息有自己的优先级，用整数表示，该值越大表示优先级越高。输入描述：首先是一个整数n，表示要处理消息的数目，接下来有2n行，每行可能为一个消息（格式为“消息名称优先级”），也可能为“Process”，后者表示处理一个消息(总是处理当前优先级高的消息)。输入数据保证不会出现“在要处理消息时，优先级队列为空”的情形，也能保证在同一时刻，优先级队列中不存在两个优先级相同的消息。输出描述：输出依次处理的每个消息，格式如样例输出所示。样例输入/输出如下。样例输入：8Keyboard12Mouse7ProcessTimer13Keyboard11Timer9ProcessProcessTimer16ProcessProcessKeyboard8Mouse24Proces