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