数据结构 用两个栈模拟队列的操作.doc

数据结构实验报告实验题目:用两个栈模拟队列的操作。实验目的：1、掌握使用Visual C+6.0上机调试程序的基本方法；2、 掌握栈与队列中的基本操作并学会灵活运用；3、 提高自己分析问题和解决问题的能力，在实践中理解教材上的理论。实验内容：通过两个栈s1和s2模拟队列的进队操作，出队操作，对队满和队空的判断，遍历输出队列中的所有数据。一、需求分析1、输入的形式和输入值的范围：根据提示，输入序号以选择要进行的操作（进队、出队、结束），进行进队或出队前，需输入进队或出队数据的个数，再输入相应个数的数据。2、输出的形式：在进队的数据输入完毕后后，输出已经进入队列的所有数据，若队已满存在未进入队列的数据，则输出相应的队满的提示；在输入出队数据的个数完成后，则输出要出队的所有数据，若队列中的数据个数小于操作者想要输出的数据个数，则提示队空，然后再输出出队后队列中的所有数据。3、程序所能达到的功能：根据提示进行操作，模拟进队，出队，判断队满和队空，以及输出队列中的所有数据。4、测试数据：请选择要进行的操作(1.进队 2.出队 3.结束):1请输入进队数据个数:14输入数据:1 2 3 4 5 6 7 8 9 10 11 12 13 14队已满,11未进入队列队已满,12未进入队列队已满,13未进入队列队已满,14未进入队列此时队列中的数据依次为:1 2 3 4 5 6 7 8 9 10请选择要进行的操作(1.进队 2.出队 3.结束):2请输入出队数据个数:3出队的数据为:1 2 3此时队列中的数据依次为:4 5 6 7 8 9 10请选择要进行的操作(1.进队 2.出队 3.结束):2请输入出队数据个数:10出队的数据为:4 5 6 7 8 9 10 队空!此时队列中已没有数据请选择要进行的操作(1.进队 2.出队 3.结束):3谢谢你的使用二 概要设计（一）栈按照“后进先出”的顺序进行操作，队列按照“先进后出”的顺序进行操作，所以本题中利用两个顺序栈s1和s2模拟队列的操作。1、模拟进队可以通过将数据输入栈s1实现，当栈s1已满并且栈s2为空时，须将栈s1中的数据由栈顶至栈底依次全部移入栈s2；2、模拟出队可以将数据由栈s2输出实现，当栈s2已空但仍需要继续模拟出队操作时，若栈s1非空则需要将栈s1中的数据由栈顶至栈底依次全部移入栈s2，继续输出；3、当栈s1满且栈s2非空则表示队列已满，当栈s1空且栈s2空则表示队列已空；4、遍历输出队列中的数据，该过程的模拟通过自栈顶至栈底输出栈s2中的数据，接着自栈底至栈顶输出栈s1中的数据来实现。（二）本程序的基本操作和模块：1、顺序栈的基本操作，包括以下部分：初始化顺序栈：InitStack(SeqStack &s) 判断栈满：StackFull(SeqStack &s)判断栈空：StackEmpty(SeqStack &s)入栈：Push(SeqStack &s,int a)出栈：Pop(SeqStack &s)将栈s1中数据全部移入栈s2：Fun(SeqStack &s1,SeqStack &s2)2、 利用栈的基本操作，模拟队列的操作：判断队满：QueueFull(SeqStack &s1,SeqStack &s2)判断队空：QueueEmpty(SeqStack &s1,SeqStack &s2) 进队：enQueue(SeqStack &s1,SeqStack &s2,int m)出队：deQueue(SeqStack &s1,SeqStack &s2,int n)遍历队列：display(SeqStack &s1,SeqStack &s2) 3、 主函数：main( )在主函数中调用模拟队列操作的函数，实现题目的要求。三 详细设计（1） 顺序栈类型描述typedef structint datamaxsize;int top;SeqStack; （2） 顺序栈的基本操作1、 初始化顺序栈：InitStack(SeqStack &s) 空栈时栈顶指针top为-12、 判断栈满：StackFull(SeqStack &s) 若栈顶指针值top=maxsize-1,说明栈满，返回1；否则返回03、 判断栈空：StackEmpty(SeqStack &s) 若栈顶指针值top=-1,说明栈空，返回1；否则返回04、 入栈：Push(SeqStack &s,int a)首先判断栈是否满，若栈未满，则让栈顶指针上移，数据元素入栈5、 出栈：Pop(SeqStack &s)首先判断栈是否空，若栈不空，则输出栈顶元素值，栈顶指针下移6、将栈s1中数据全部移入栈s2：Fun(SeqStack &s1,SeqStack &s2while(s1.top-1)/当栈s1非空时，执行以下操作s2.top+;/栈s2的栈顶加1s2.datas2.top=s1.datas1.top;/将栈s1的栈顶赋给栈s2的栈顶s1.top-;/栈s1的指针减1（3） 利用栈的基本操作所模拟的队列的操作1、判断队满：QueueFull(SeqStack &s1,SeqStack &s2)若栈s1满且栈s2非空，说明队满，返回1；否则返回0(该函数调用了判栈满函数StackFull和判栈空函数StackEmpty)2、判断队空：QueueEmpty(SeqStack &s1,SeqStack &s2) 若栈s1空且栈s2空，说明队空，返回1；否则返回0(该函数调用了判栈空函数StackEmpty)3、 进队：enQueue(SeqStack &s1,SeqStack &s2,int m)输入m个数据，执行以下操作：如果队满,输出队满的提示，此时数据不能进入队列如果队不满，若“栈s1满，栈s2空”，则将栈s1中数据全部移入栈s2，若不满足“栈s1满，栈s2空”的条件，则不必执行上述操作。之后将输入的数据入栈s1。(该函数调用了判栈满函数StackFull，判栈空函数StackEmpty，判队满函数QueueFull，将栈s1中数据全部移入栈s2的函数Fun，入栈函数Push) 4、 出队：deQueue(SeqStack &s1,SeqStack &s2,int n)根据要出队的数据的个数，执行以下操作：如果队空，则输出队空的提示如果队不空，若“栈s1非空，栈s2空”，则将栈s1中数据全部移入栈s2，若不满足“栈s1非空，栈s2空”的条件，则不必执行上述操作。之后将栈s2中的数据出栈。(该函数调用了判栈空函数StackEmpty，判队空函数QueueEmpty，将栈s1中数据全部移入栈s2的函数Fun，出栈函数Pop) 5、 遍历队列：display(SeqStack &s1,SeqStack &s2) 如果队空，则提示队列中已没有数据如果队不空，则由栈顶至栈底，依次输出s2中的数据；接着由栈底至栈顶，依次输出s1中的数据。(该函数调用了判队空函数QueueEmpty) （4） 主函数在主函数中调用进队函数enQueue、出队函数deQueue和遍历队列函数displaywhile(1)输入数据选择要进行的操作(1.进队 2.出队 3.结束)如果选择3，则退出循环，结束程序运行。如果选择1，则输入进队数据个数，接着调用进队函数，输入相应个数的数据，完成数据进队；最后遍历输出队列中的所有数据如果选择2，则输入出队数据个数，接着调用出队函数，输出相应的数据，完成数据出队；最终遍历输出队列中的所有数据四 使用说明、测试分析及结果1、 程序使用说明：（1） 本程序运行环境为Visual C+ 6.0；（2） 根据界面提示进行操作，以空格分隔分隔输入的连续数据，输入完毕后以回车结束2、 测试结果与分析：页面提示“请选择要进行的操作(1.进队 2.出队 3.结束):”输入序号“1”，按回车确定，页面显示“请输入进队数据个数:”输入“14”，按回车确定，则提示“输入数据:”依次输入以下数据“1 2 3 4 5 6 7 8 9 10 11 12 13 14”（空格分隔），按回车确定则页面显示如下：“队已满,11未进入队列队已满,12未进入队列队已满,13未进入队列队已满,14未进入队列此时队列中的数据依次为:1 2 3 4 5 6 7 8 9 10请选择要进行的操作(1.进队 2.出队 3.结束):”输入序号“2”，按回车确定，表示选择出队操作，页面提示“请输入出队数据个数:”输入“3”，按回车确定，则页面显示如下：“出队的数据为:1 2 3此时队列中的数据依次为:4 5 6 7 8 9 10请选择要进行的操作(1.进队 2.出队 3.结束):”输入序号“2”，按回车确定，表示继续选择出队操作，页面提示“请输入出队数据个数:”输入“10”，按回车确定，则页面显示如下：“出队的数据为:4 5 6 7 8 9 10 队空!此时队列中已没有数据请选择要进行的操作(1.进队 2.出队 3.结束):”输入序号“3”，按回车确定，页面显示如下：“谢谢你的使用Press any key to continue”由上测试结果分析得，该程序功能满足题目要求。3、 调试过程中遇到的问题及解决方法在第一次运行程序时，出队结果为部分输入的进队数据和乱码，认真分析后发现栈顶指针移动的次序错误，这是个特别低级的错误，在检查代码时及时发现了。另一个错误是出队数据的结果正确，但是遍历输出队列中的数据显示有误，因为错误发生在后半部分输出的数据，所以检查了display函数，发现循环条件不够完整，在修改了程序之后，该过程也得以纠正。运行的页面中显示的对操作的提示，以及对队满和队空的提示虽然正确，但是很混乱，比如输入数据完毕后仍然有让操作者输入数据的提示，还有输入的数据太多，有两个输入的数据不能进入队列，此时显示结果为两个“队满”，为解决问题，我调整了和输入数据相关的语句在函数中的位置，输出提示也作了一点修改，最终得到运行界面中所示的结果。4、 运行界面五、实验总结本次实验，我进行了预习，但是预习的思路出现了错误，在课上老师对该实验作了提示后，我意识到了自己思路中的问题。即将数据由栈s1移入栈s2，若移动就应全部移走，只有在栈s2为空时，才可以向栈s2中移入数据。我在10月19日下午完成了代码的编写，运行结果正确，但是仍存在一些问题，如函数名的命名，进队函数名为Push，出队函数名为Pop，这样命名很不规范，且代码可读性差，对题目中要求的用两个栈模拟队列操作体现不够明显，在老师的指导下，我又在实验课上作了修改。在本次编写程序过程中，发生了一些很低级的错误，但是都很快解决。在对最后运行的页面的修改花费了很多时间才使之和谐统一，因为虽然程序编写正确，运行结果也正确，但是输入和输出结果不够人性化，对输入的处理也出现过一些错误，我觉得在以后应该注意这个问题。按照本实验的设计思路，可以模拟队列中“先进先出”的功能，但是所模拟的队列能存储的最大数据个数是不确定的，如第二个运行界面中所示，第一次输入数据后栈s1和栈s2都已满，此时表示队列已满，队列中存放了10个数据。接着令4个数据出队，则栈s2中剩一个数据，栈s1满，但此时也表示队列已满，不能继续进队。即队列中的数据个数n满足maxsize+1n2*maxsize。本次实验，我很感谢老师和同学对我的指点。通过本次实验，对队列和栈的结构有了更深层次的认识，对一些细节更加理解，收获了很多。教师评语：实验成绩：指导教师签名：批阅日期： 代码：# include# define maxsize 5/typedef struct/顺序栈类型描述int datamaxsize;int top;SeqStack;/void InitStack(SeqStack &s)/初始化顺序栈s.top=-1;/int StackFull(SeqStack &s)/判栈满的函数if(s.top=maxsize-1)return 1;else return 0;/int StackEmpty(SeqStack &s)/判栈空的函数if(s.top=-1) return 1;else return 0;/void Push(SeqStack &s,int a)/入栈函数if(StackFull(s) printf(栈满!);elses.top+;s.datas.top=a;/void Pop(SeqStack &s)/出栈函数if(StackEmpty(s) printf(栈空!);else printf(%d ,s.datas.top);s.top-;/int QueueFull(SeqStack &s1,SeqStack &s2)/判队满函数if(StackFull(s1)&!StackEmpty(s2) return 1;/当栈s1满且栈s2非空，则队满else return 0;/int QueueEmpty(SeqStack &s1,SeqStack &s2)/判队空函数if(StackEmpty(s1)&StackEmpty(s2) return 1;/当栈s1空且栈s2空，则栈空else return 0;/void Fun(SeqStack &s1,SeqStack &s2)/将栈s1中的数据全部移入栈s2while(s1.top-1)/当栈s1非空时，执行以下操作s2.top+;/栈s2的栈顶加1s2.datas2.top=s1.datas1.top;/将栈s1的栈顶赋给栈s2的栈顶s1.top-;/栈s1的指针减1/void enQueue(SeqStack &s1,SeqStack &s2,int m)/进队函数 int i,a;printf(输入数据:);/输出输入数据的提示for(i=0;im;i+)scanf(%d,&a);/输入数据if(QueueFull(s1,s2)/如果队满,输出队满的提示，此时数据不能进入队列printf(队已满,%d未进入队列n,a);elseif(StackFull(s1)&StackEmpty(s2)/如果栈s1满，栈s2空，则将栈s1中数据全部移入栈s2Fun(s1,s2);/调用函数，将栈s1中数据全部移入栈s2Push(s1,a);/调用入栈函数，将输入的数据入栈s1/void deQueue(SeqStack &s1,SeqStack &s2,int