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

.

数据结构实验报告

实验名称： 实验2——栈和队列 学生姓名： 班 级： 班内序号： 学 号： 日 期： 一、 实验要求

1、实验目的： 进一步掌握指针、模板类、异常处理的使用

掌握栈的操作的实现方法 掌握队列的操作的实现方法 学习使用栈解决实际问题的能力 学习使用队列解决实际问题的能力

2、实验内容：

根据栈和队列的抽象数据类型的定义，按要求实现一个栈或一个队列。 要求： 实现一个共享栈 实现一个链栈 实现一个循环队列 实现一个链队列

编写测试main()函数测试线性表的正确性 二、程序分析 2.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 \下溢\

.

.

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;//定义新结点

.

.

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<data<

linkstack::~linkstack()//析构 {while(top) {Node*p=top; top=top->next; delete p; } }

C、实现一个循环队列

a、 伪代码实现:

.