数据结构实验二题目一栈和队列实验报告

北京邮电大学信息与通信工程学院第1页数据结构实验报告实验名称：实验2——栈和队列学生姓名：班级：班内序号：学号：日期：一、实验要求1、实验目的：进一步掌握指针、模板类、异常处理的使用掌握栈的操作的实现方法掌握队列的操作的实现方法学习使用栈解决实际问题的能力学习使用队列解决实际问题的能力2、实验内容：根据栈和队列的抽象数据类型的定义，按要求实现一个栈或一个队列。要求：实现一个共享栈实现一个链栈实现一个循环队列实现一个链队列编写测试main()函数测试线性表的正确性二、程序分析2.1存储结构顺序栈、链栈和顺序队列北京邮电大学信息与通信工程学院第2页顺序栈链栈顺序队列2.2关键算法分析A、实现一个共享栈：a、伪代码实现入栈操作：如果栈满，则抛出上溢异常；判断是插在栈1还是栈2，如果在栈1插入，则栈顶指针top1加1，在top1处填入x，如果在栈2插入，则栈顶指针top2加1，在top2处填入x。出栈操作：如果栈空，则抛出下溢异常；判断是栈1出栈还是栈2，如果是栈1，则输出栈1栈顶元素，并且top1减1，如果是栈2，则输出栈2栈顶元素，并且top2加1。得到栈顶元素操作：如果栈空，则抛出下溢异常；判断是栈1出栈还是栈2，如果是栈1，则输出栈1栈顶元素，如果是栈2，则输出栈2栈顶元素。b、算法实现：voidshareseqstack::push(intx,intpushnumber)//进栈操作{if(top1+1==top2)//异常处理throw上溢;if(pushnumber==1)//判断栈1还是栈2data[++top1]=x;if(pushnumber==2)data[--top2]=x;}voidshareseqstack::pop(intpopnumber)//出栈操作{if(popnumber==1)//异常处理{if(top1==-1)throw下溢;北京邮电大学信息与通信工程学院第3页elsecoutdata[top1--]endl;}if(popnumber==2)//异常处理{if(top2==seqstack)throw下溢;elsecoutdata[top2++]endl;}}voidshareseqstack::gettop(intgetnumber)//得到栈顶元素{if(getnumber==1)//判断栈1还是栈2{if(top1==-1)throw下溢;//异常处理coutdata[top1]endl;}if(getnumber==2){if(top2==seqstack)throw下溢;coutdata[top2]endl;}}B、实现一个链栈插入删除a伪代码实现入栈：生成新结点，对新结点赋值，新结点的指向原栈顶指针，修改栈顶指针为新结点。出栈：判断若为空栈抛出下溢异常，保存栈顶元素，建立新结点，保存栈顶指针，修改栈顶指针为原栈顶指针的下一个结点，删除栈顶指针并输出栈顶元素。b、算法实现：voidlinkstack::push(intx)//进栈操作{Node*p=newNode;//定义新结点北京邮电大学信息与通信工程学院第4页p-data=x;p-next=top;top=p;}voidlinkstack::pop()//出栈操作{if(empty())throw下溢;//异常处理intx=top-data;Node*p=newNode;//定义新结点p=top;top=top-next;deletep;coutx;}voidlinkstack::gettop()//得到栈顶元素{if(empty())throw下溢;//异常处理couttop-dataendl;}linkstack::~linkstack()//析构{while(top){Node*p=top;top=top-next;deletep;}}C、实现一个循环队列a、伪代码实现:北京邮电大学信息与通信工程学院第5页入队：判断若为队满，抛出异常，尾指针后移，指向入队元素。出队：判断若为队空，抛出异常，头指针后移，输出队头元素。b、算法实现voidcirclequeue::enqueue(intx)//进队操作{if((rear+1)%queuesize==front)throw上溢;//异常处理rear=(rear+1)%queuesize;data[rear]=x;}voidcirclequeue::dequeue()//出队操作{if(rear==front)throw下溢;//异常处理front=(front+1)%queuesize;coutdata[front]endl;}voidcirclequeue::getfront()得到队头元素{if(rear==front)throw下溢;//异常处理coutdata[(front+1)%queuesize]endl;}voidcirclequeue::getlength()//得到队列长度{cout((rear-front+queuesize)%queuesize)endl;}D、实现一个链队列voidlinkqueue::enqueue(intx)//进队操作{rear-next=newNode;rear=rear-next;rear-data=x;rear-next=NULL;}voidlinkqueue::dequeue()//出队操作{Node*p=front-next;front-next=p-next;北京邮电大学信息与通信工程学院第6页intx=p-data;deletep;if(!(front-next))rear=front;coutxendl;}voidlinkqueue::getfront()//得到头结点元素{if(!(front-next))throw上溢;//异常处理cout(front-next-data)endl;}linkqueue::~linkqueue()//析构{while(front){rear=front-next;deletefront;front=rear;}}2.3其他源代码#includeiostreamusingnamespacestd;structNode//定义结点{intdata;structNode*next;};constintseqstack=100;classshareseqstack//定义共享栈{public:shareseqstack();voidpush(intx,intpushnumber);voidpop(intpopnumber);voidgettop(intgetnumber);private:intdata[seqstack];inttop1;inttop2;};shareseqstack::shareseqstack()//构造{top1=-1;top2=seqstack;}北京邮电大学信息与通信工程学院第7页voidshareseqstack::push(intx,intpushnumber)//进栈操作{if(top1+1==top2)//异常处理throw上溢;if(pushnumber==1)//判断栈1还是栈2data[++top1]=x;if(pushnumber==2)data[--top2]=x;}voidshareseqstack::pop(intpopnumber)//出栈操作{if(popnumber==1)//异常处理{if(top1==-1)throw下溢;elsecoutdata[top1--]endl;}if(popnumber==2)//异常处理{if(top2==seqstack)throw下溢;elsecoutdata[top2++]endl;}}voidshareseqstack::gettop(intgetnumber)//得到栈顶元素{if(getnumber==1)//判断栈1还是栈2{if(top1==-1)throw下溢;//异常处理coutdata[top1]endl;}if(getnumber==2){if(top2==seqstack)throw下溢;coutdata[top2]endl;}}classlinkqueue//定义链队列{public:linkqueue(){front=rear=newNode;front-next=NULL;}~linkqueue();voidenqueue(intx);voiddequeue();voidgetfront();boolempty(){returnfront==rear?true:false;}private:Node*front;Node*rear;};voidlinkqueue::enqueue(intx)//进队操作{rear-next=newNode;rear=rear-next;rear-data=x;北京邮电大学信息与通信工程学院第8页rear-next=NULL;}voidlinkqueue::dequeue()//出队操作{Node*p=front-next;front-next=p-next;intx=p-data;deletep;if(!(front-next))rear=front;coutxendl;}voidlinkqueue::getfront()//得到头结点元素{if(!(front-next))throw上溢;//异常处理cout(front-next-data)endl;}linkqueue::~linkqueue()//析构{while(front){rear=front-next;deletefront;front=rear;}}classlinkstack//定义链栈{public:linkstack(){top=NULL;}~linkstack();voidpush(intx);voidpop();voidgettop();boolempty(){return(NULL==top)?true:false;}private:structNode*top;};voidlinkstack::push(intx)//进栈操作{Node*p=newNode;//定义新结点p-data=x;p-next=top;top=p;}voidlinkstack::pop()//出栈操作{if(empty())throw下溢;//异常处理intx=top-data;Node*p=newNode;//定义新结点p=top;top=top-next;北京邮电大学信息与通信工程学院第9页deletep;coutx;}voidlinkstack::gettop()//得到栈顶元素{if(empty())throw下溢;//异常处理couttop-dataendl;}linkstack::~linkstack()//析构{while(top){Node*p=top;top=top-next;deletep;}}constintqueuesize=1000;//定义循环队列classcirclequeue{public:circlequeue(){front=rear=0;}voidenqueue(intx);voiddequeue();voidgetfront();voidgetlength();boolempty(){returnfront=rear?true:false;}private:intdata[queuesize];intfront;intrear;};voidcirclequeue::enqueue(intx)//进队操作{if((rear+1)%queuesize==front)throw上溢;//异常处理