北京邮电大学信息与通信工程学院
数据结构实验报告
实验名称： 实验2——栈和队列 学生姓名： 班 级： 班内序号： 学 号： 日 期： 一、 实验要求
1、实验目的： 进一步掌握指针、模板类、异常处理的使用
掌握栈的操作的实现方法 掌握队列的操作的实现方法 学习使用栈解决实际问题的能力 学习使用队列解决实际问题的能力
2、实验内容：
根据栈和队列的抽象数据类型的定义，按要求实现一个栈或一个队列。 要求： 实现一个共享栈 实现一个链栈 实现一个循环队列 实现一个链队列
编写测试main()函数测试线性表的正确性 二、程序分析 2.1 存储结构
顺序栈、链栈和顺序队列
第1页
北京邮电大学信息与通信工程学院
顺序栈 链栈 顺序队列 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、算法实现：
void shareseqstack::push(int x,int pushnumber)//进栈操作 {if(top1+1==top2)//异常处理 throw \上溢\
if(pushnumber==1)//判断栈1还是栈2 data[++top1]=x; if(pushnumber==2) data[--top2]=x; }
void shareseqstack::pop(int popnumber)//出栈操作 {if(popnumber==1) //异常处理 { if(top1==-1) throw \下溢\
第2页
北京邮电大学信息与通信工程学院
else cout< if(popnumber==2) //异常处理 {if(top2==seqstack) throw \下溢\else cout< void shareseqstack::gettop(int getnumber)//得到栈顶元素 {if(getnumber==1) //判断栈1还是栈2 {if(top1==-1) throw \下溢\异常处理 cout< {if(top2==seqstack) throw \下溢\cout< B、实现一个链栈 插入 删除 a伪代码实现 入栈：生成新结点，对新结点赋值，新结点的指向原栈顶指针，修改栈顶指针为新结点。 出栈：判断若为空栈抛出下溢异常，保存栈顶元素，建立新结点，保存栈顶指针，修改栈顶指针为原栈顶指针的下一个结点，删除栈顶指针并输出栈顶元素。 b、算法实现： void linkstack::push(int x)//进栈操作 {Node*p=new Node;//定义新结点 第3页 北京邮电大学信息与通信工程学院 p->data=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; cout< void linkstack::gettop()//得到栈顶元素 {if(empty()) throw \下溢\异常处理 cout< linkstack::~linkstack()//析构 {while(top) {Node*p=top; top=top->next; delete p; } } C、实现一个循环队列 a、 伪代码实现: 第4页 北京邮电大学信息与通信工程学院 入队：判断若为队满，抛出异常，尾指针后移，指向入队元素。 出队：判断若为队空，抛出异常，头指针后移，输出队头元素。 b、 算法实现 void circlequeue::enqueue(int x)//进队操作 {if((rear+1)%queuesize==front) throw \上溢\异常处理 rear=(rear+1)%queuesize; data[rear]=x; } void circlequeue::dequeue()//出队操作 {if(rear==front) throw \下溢\异常处理 front=(front+1)%queuesize; cout< void circlequeue::getfront()得到队头元素 {if(rear==front) throw \下溢\异常处理 cout< void circlequeue::getlength()//得到队列长度 {cout<<((rear-front+queuesize)%queuesize)< D、实现一个链队列 void linkqueue::enqueue(int x)//进队操作 {rear->next=new Node; rear=rear->next; rear->data=x; rear->next=NULL; } void linkqueue::dequeue()//出队操作 {Node*p=front->next; front->next=p->next; 第5页