用两个栈模拟一个队列,并实现判断栈空.栈满以及入队和出队操作

《数据结构》实验报告班级:JS001001姓名:葛赛磊学号:2010300006E-mail:[e-mail]日期:2012.10.25◎实验题目:用两个栈模拟一个队列◎实验目的：理解并掌握栈与队列的特点，以及他们之间的联系和区别◎实验内容：用两个栈模拟一个队列，实现判断栈空.栈满以及入队和出队操作。一、需求分析1、输入的形式和输入值的范围：①输入字母选择相应操作；②输入需要进队或出队的元素个数。2、输出的形式:输出入队或者出队的元素，若队空则输出队空以及队空时输出的元素及其个数；若队满则输出“队已满”，并输出截止队满时出队的元素个数。3、程序所能达到的功能：（1）执行任意个数元素的入队操作（2）执行任意个数元素的出队操作（3）判断队空（4）判断队满4、测试数据：操作选项输入a；入队元素个数：3123操作选项输入b；出队元素个数：2操作选项输入a；入队元素个数12111213141516171819202122二概要设计（1）抽象数据类型定义：定义两个链表：typedefstruct{intdata[Maxsize];inttop;}seqstack;seqstacks1,s2;输入输出元素个数：intn,m,x,i,j;操作选项控制符：charw,a,b,c;（2）主程序的流程：1.根据提示输入符号选择相应操作；2.根据选择执行相关操作①进行入栈：判断栈是否已满，并进行入队操作并输出成功入队的元素个数，②进行出栈；判断栈是否为空，并进行出栈操作，输出成功出栈的元素个数（3）其函数之间调用关系如下：（开始创建链表）main()模块操作判定模块入队操作模块模块出队操作模块块②调用结束后，main()函数返回0执行结束后，重新执行判定操作和循环。注：大箭头表示函数调用，小箭头表示程序执行过程；三详细设计1.元素类型typedefstruct{intdata[Maxsize];inttop;}seqstack;seqstacks1,s2;intn,m,x,i,j;charw,a,b,c;2．每个模块的分析：（1）主程序模块：//主函数intmain(){s1.top=-1,s2.top=-1;//执行选择操作cout执行进队操作请输入a;\n执行出队操作请输入b；\n停止操作请输入cendl;cinw;while(w!='c'){//判断栈满，并执行入队操作if(w=='a'){cout请输入入队元素个数endl;cinn;for(i=0,j=0;in;i++){cinx;if(s1.top==Maxsize-1&&s2.top!=-1){if(i==j)cout队已满endl;}else{push(s1,x);j++;}}cout共入队j个元素endl;}//判断栈空并进行出队操作elseif(w=='b'){cout请输入出队元素个数endl;cinm;for(j=0;jm;j++){if(s1.top==-1&&s2.top==-1){cout队已空endl;break;}elsepop(s2);}cout共出队j个元素endl;}elsecout输入有误，请核对后重新输入endl;cout执行进队操作请输入a;\n执行出队操作请输入b；\n停止操作请输入cendl;cinw;}return0;}（2）入队函数voidpush(seqstack&s1,intx){//1栈满，2栈空，进行倒栈操作if(s1.top==Maxsize-1&&s2.top==-1){while(s1.top!=-1){s2.top++;s2.data[s2.top]=s1.data[s1.top];s1.top--;}s1.top++;s1.data[s1.top]=x;}else{s1.top++;s1.data[s1.top]=x;}}（3）出队函数voidpop(seqstack&s2){intx;if(s2.top==-1){while(s1.top!=-1){s2.top++;s2.data[s2.top]=s1.data[s1.top];s1.top--;}{x=s2.data[s2.top];s2.top--;coutxendl;}}else{x=s2.data[s2.top];s2.top--;coutxendl;}}四使用说明、测试分析及结果1.程序使用说明；（1）本程序的运行环境为VC6.0。（2）进入演示程序后即显示提示信息：执行进队操作请输入a;执行出队操作请输入b；停止操作请输入c;2、测试结果与分析；操作选项：输入a；入队元素个数：3123共入队3个元素；操作选项输入b；出队元素个数：212共出队2个元素；操作选项输入a；入队元素个数12111213141516171819202122栈已满，共入队10个元素；操作选项：输入f输入有误，请核对后重新输入3、调试过程中遇到的问题是如何解决提以及对设计与实现的回顾讨论和分析；首先是一次性在栈1中输入较多元素时出现错误，解决方案：进一步分析，增加了二栈为空时的倒栈操作，解决了问题；其次是判断栈满后继续操作时出现错误，请教别人得知是由于输入区缓存未清除造成的。4、运行界面。五、实验总结(1)你在编程过程中花时多少？一个晚上。(2)多少时间在纸上设计？半小时。（3）多少时间上机输入和调试？四个小时。（4）多少时间在思考问题？一个小时（5）遇到了哪些难题？循环链表的输出时出现问题，调用函数时出现错误。（6）你是怎么克服的？根据提示检查错误，上互联网进行搜索，求助于同学。（7）你的收获有哪些？使用指针时要慎重，学会独立解决自己遇见的问题。教师评语：实验成绩：指导教师签名：批阅日期：