《数据结构实验二题目一栈和队列实验报告》由会员分享，可在线阅读，更多相关《数据结构实验二题目一栈和队列实验报告（12页珍藏版）》请在金锄头文库上搜索。
1、数据结构实验报告实验名称： 实验2栈和队列学生姓名： 班 级： 班内序号： 学 号：日 期： 一、 实验要求1、实验目的： 进一步掌握指针、模板类、异常处理的使用掌握栈的操作的实现方法掌握队列的操作的实现方法学习使用栈解决实际问题的能力学习使用队列解决实际问题的能力 2、实验内容：根据栈和队列的抽象数据类型的定义，按要求实现一个栈或一个队列。要求：实现一个共享栈实现一个链栈实现一个循环队列实现一个链队列编写测试main()函数测试线性表的正确性二、程序分析2.1 存储结构顺序栈、链栈和顺序队列 顺序栈 链栈 顺序队列2.2 关键算法分析A、实现一个共享栈： a、伪代码实现入栈操作：如果栈满，则
2、抛出上溢异常； 判断是插在栈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、算法实现：void shareseqstack:push(int x,int pushnumber)/进栈操作if(top1+1=top2)
3、/异常处理throw 上溢;if(pushnumber=1)/判断栈1还是栈2data+top1=x;if(pushnumber=2)data-top2=x;void shareseqstack:pop(int popnumber)/出栈操作if(popnumber=1) /异常处理 if(top1=-1) throw 下溢;else coutdatatop1-endl; if(popnumber=2) /异常处理if(top2=seqstack) throw 下溢;else coutdatatop2+endl;void shareseqstack:gettop(int getnumber)/
4、得到栈顶元素if(getnumber=1) /判断栈1还是栈2if(top1=-1) throw 下溢; /异常处理coutdatatop1endl;if(getnumber=2)if(top2=seqstack) throw 下溢;coutdatatop2data=x;p-next=top;top=p;void linkstack:pop()/出栈操作if(empty() throw 下溢;/异常处理int x=top-data;Node*p=new Node; /定义新结点p=top;top=top-next;delete p;coutx ;void linkstack:gettop()/
5、得到栈顶元素if(empty() throw 下溢;/异常处理coutdatanext;delete p;C、实现一个循环队列a、 伪代码实现:入队：判断若为队满，抛出异常，尾指针后移，指向入队元素。出队：判断若为队空，抛出异常，头指针后移，输出队头元素。b、 算法实现void circlequeue:enqueue(int x)/进队操作if(rear+1)%queuesize=front) throw 上溢;/异常处理rear=(rear+1)%queuesize;datarear=x;void circlequeue:dequeue()/出队操作if(rear=front) throw
6、下溢;/异常处理front=(front+1)%queuesize;coutdatafrontendl;void circlequeue:getfront()得到队头元素if(rear=front) throw 下溢;/异常处理coutdata(front+1)%queuesizeendl;void circlequeue:getlength()/得到队列长度cout(rear-front+queuesize)%queuesize)next=new Node;rear=rear-next;rear-data=x;rear-next=NULL;void linkqueue:dequeue()/出
7、队操作Node*p=front-next;front-next=p-next;int x=p-data;delete p;if(!(front-next)rear=front;coutxnext) throw 上溢;/异常处理coutnext-data)next;delete front;front=rear;2.3 其他源代码#includeusing namespace std;struct Node /定义结点int data;struct Node*next;const int seqstack=100;class shareseqstack /定义共享栈 public:sharese
8、qstack();void push(int x,int pushnumber);void pop(int popnumber);void gettop(int getnumber);private:int dataseqstack;int top1;int top2;shareseqstack:shareseqstack()/构造top1=-1;top2=seqstack;void shareseqstack:push(int x,int pushnumber)/进栈操作if(top1+1=top2)/异常处理throw 上溢;if(pushnumber=1)/判断栈1还是栈2data+to
9、p1=x;if(pushnumber=2)data-top2=x;void shareseqstack:pop(int popnumber)/出栈操作if(popnumber=1) /异常处理 if(top1=-1) throw 下溢;else coutdatatop1-endl; if(popnumber=2) /异常处理if(top2=seqstack) throw 下溢;else coutdatatop2+endl;void shareseqstack:gettop(int getnumber)/得到栈顶元素if(getnumber=1) /判断栈1还是栈2if(top1=-1) thr
10、ow 下溢; /异常处理coutdatatop1endl;if(getnumber=2)if(top2=seqstack) throw 下溢;coutdatatop2next=NULL;linkqueue();void enqueue(int x);void dequeue();void getfront();bool empty()return front=rear? true:false;private:Node*front;Node*rear;void linkqueue:enqueue(int x)/进队操作rear-next=new Node;rear=rear-next;rear-
11、data=x;rear-next=NULL;void linkqueue:dequeue()/出队操作Node*p=front-next;front-next=p-next;int x=p-data;delete p;if(!(front-next)rear=front;coutxnext) throw 上溢;/异常处理coutnext-data)next;delete front;front=rear;class linkstack/定义链栈public:linkstack()top=NULL;linkstack();void push(int x);void pop();void gettop();bool empty()return(NULL=top)? true:false;private:struct Node*top;void linkstack:push(int x
