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

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