数据结构实验报告栈和队列共享栈与链栈的模板类实现及测试函数

《数据结构实验报告栈和队列共享栈与链栈的模板类实现及测试函数》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构实验报告实验名称：实验二——栈和队列学生姓名：班级：班内序号：学号：日期：1．实验要求2.1题目1根据栈和队列的抽象数据类型的定义，按要求实现一个栈或一个队列。要求：1、实现一个共享栈2、实现一个链栈3、实现一个循环队列4、实现一个链队列编写测试main()函数测试线性表的正确性。2.程序分析2.1存储结构共享栈：链栈：2.2关键算法分析2.2.1共享栈入栈：if(top1==top2-1)//判断栈是否已满{throw"上溢";}if(i==1)//如果要入栈1{data[++top1]=x;//top指针加一，然后赋值}if(i==2)//如果要入栈2{data[--t

2、op2]=x;//top指针减1，赋值}出栈：if(i==1){if(top1==-1)//判断栈1是否为空{throw"下溢";}returndata[top1--];//返回出栈元素的值并且栈顶指针下移}if(i==2){if(top2==StackSize){throw"下溢";}returndata[top2++];//返回出栈元素的值并且栈顶指针上移}查找栈顶元素：if(i==1){if(top1!=-1)//如果栈1非空{returndata[top1];}}if(i==2){if(top2!=StackSize)//如果栈2非空{returndata[top2];}}

3、判断栈是否为空：if(i==1){if(top1==-1){returntrue;}else{returnfalse;}}if(i==2){if(top2==StackSize){returntrue;}else{returnfalse;}}returnfalse;输出栈中元素：inttemp1=top1;//工作指针while(temp1!=-1)//判断栈一是否为空{cout<

4、2++]<<"";//输出元素，工作指针加一}2.2.2链栈析构函数：while(top)//判断是否为空{structNode*p=top;//新建工作指针，并用top指针初始化top=top->next;//top指针后移deletep;}入栈：structNode*p=newNode;//新建工作指针指向新结点p->data=x;//新结点的数据域赋值为xp->next=top;//新节点的next域记录top指针指向地址top=p;//栈顶指针该为p出栈：if(Empty())throw"下溢";Tx=top->data;//保存数据structNode<

5、T>*p=top;//保存栈顶指针地址top=top->next;//栈顶指针后移deletep;//删除returnx;//返回数值查找栈顶元素：if(Empty()){throw"empty";}returntop->data;3.程序运行结果1.共享栈测试主函数流程开始新建共享栈入栈操作出栈操作查找栈顶元素判断栈是否为空输出栈中元素结束2.链栈测试主函数流程图开始新建数组为数组元素赋值并入栈出栈操作查找栈顶元素判断栈是否为空执行析构函数结束程序运行结果：源代码#includeusingnamespacestd;constintStackSize=10;//

6、定义栈的最大高度templateclassBothStack//定义两栈共享空间的c++模板类{public:BothStack()//构造函数，初始化空栈{top1=-1;top2=StackSize;}voidPush(inti,T1x);//入栈操作T1Pop(inti);//出栈操作T1GetTop(inti);//查找栈顶元素boolEmpty(inti);//判断栈是否为空栈voidPrint();//先打印栈1，再打印栈2private:T1data[StackSize];inttop1,top2;};templatevoidBot

7、hStack::Push(inti,T1x)//入栈函数{if(top1==top2-1){throw"上溢";}if(i==1){data[++top1]=x;}if(i==2){data[--top2]=x;}}templateT1BothStack::Pop(inti)//出栈函数{if(i==1){if(top1==-1)//判断栈1是否为空{throw"下溢";}returndata[top1--];//返回出栈元素的值并且