实验5 栈和队列的应用.docVIP

实验5 栈和队列的应用 目的和要求： （1）熟练栈和队列的基本操作； （2）能够利用栈与队列进行简单的应用。 一、题目 题目1.利用顺序栈和队列，实现一个栈和一个队列，并利用其判断一个字符串是否是回文。所谓回文，是指从前向后顺读和从后向前倒读都一样的字符串。例如，a+bb+a等等。 题目2. 假设在周末舞会上，男士们和女士们进入舞厅时，各自排成一队。跳舞开始时，依次从男队和女队的队头上各出一人配成舞伴。若两队初始人数不相同，则较长的那一队中未配对者等待下一轮舞曲。现要求写一算法模拟上述舞伴配对问题，并实现。 题目3. 打印机提供的网络共享打印功能采用了缓冲池技术，队列就是实现这个缓冲技术的数据结构支持。每台打印机具有一个队列（缓冲池），用户提交打印请求被写入到队列尾，当打印机空闲时，系统读取队列中第一个请求，打印并删除之。请利用队列的先进先出特性，完成打印机网络共享的先来先服务功能。 题目4. 假设以数组Q[m]存放循环队列中的元素, 同时设置一个标志tag，以tag == 0和tag == 1来区别在队头指针(front)和队尾指针(rear)相等时，队列状态为“空”还是“满”。试编写与此结构相应的插入(enqueue)和删除(dlqueue)算法。 题目5. 利用循环链队列求解约瑟夫环问题。 请大家从本组未讨论过的五道题中选择一道，参照清华邓俊辉老师MOOC视频及课本相关知识，编写相应程序。 题目选择第三题：打印机提供的网络共享打印功能采用了缓冲池技术，队列就是实现这个缓冲技术的数据结构支持。每台打印机具有一个队列（缓冲池），用户提交打印请求被写入到队列尾，当打印机空闲时，系统读取队列中第一个请求，打印并删除之。请利用队列的先进先出特性，完成打印机网络共享的先来先服务功能。 二、程序清单 #includeiostream.h #includestdio.h #includech3.h template class T void LinkedQueueT::makeEmpty()//makeEmpty函数的实现 { LinkNodeT*p; while(front!=NULL)//逐个删除队列中的结点 { p=front; front=front-link; delete p; } }; template class T bool LinkedQueueT::put_in(Tx）{//提交命令函数 if(front==NULL){//判断是否为空 front=rear=new LinkNodeT;//如果为空，新结点为对头也为对尾 front-data=rear-data=x; if(front==NULL) //分配结点失败 return false;} else{ rear-link=new LinkNodeT;//如不为空，在链尾加新的结点 rear-link-data=x; if(rear-link==NULL) return false; rear=rear-link;} return true; }; template class T bool LinkedQueueT::carry_out()//执行命令函数 { if(IsEmpty()==true)//判断是否为空 { return false; } coutfront-data ;//输出链尾的数据，代表执行打印命令 LinkNodeT*p=front; front=front-link;//删除以执行的命令，即对头修改 delete p; //释放原结点 return true; }; void main() //主函数 { LinkedQueuechar q;//定义类对象 char flag=Y; //标志是否输入了命令 const int max=30;//一次获取输入命令的最大个数 while(flag==Y) //循环 { int i=0; char str[max]; //定义存储屏幕输入的命令的数组 gets(str); //获取屏幕输入的命令 while(str[i]!=\0) { q.put_in(str[i]);//调用提交命令函数，将每个命令存入队列中 i++; } for(int j=0;j=i;j++) { if(q.IsEmpty()==true) //判断是否为空，为空则说明没有可执行的命令