数据结构实验报告
实验名称：实验二——栈和队列
学生姓名：
班级：
班内序号：
学号：
日期：
1．实验要求
2.1题目1
根据栈和队列的抽象数据类型的定义，按要求实现一个栈或一个队列。
要求：
1、 实现一个共享栈
2、 实现一个链栈
3、 实现一个循环队列
4、 实现一个链队列
编写测试main()函数测试线性表的正确性。
2. 程序
分析
定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析
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[--top2] = x; //top指针减1，赋值
}
出栈：
if (i == 1)
{
if (top1 == -1) //判断栈1是否为空
{
throw "下溢";
}
return data[top1--]; //返回出栈元素的值并且栈顶指针下移
}
if (i == 2)
{
if (top2 == StackSize)
{
throw "下溢";
}
return data[top2++]; //返回出栈元素的值并且栈顶指针上移
}
查找栈顶元素：
if (i == 1)
{
if (top1 != -1) //如果栈1非空
{
return data[top1];
}
}
if (i == 2)
{
if (top2 != StackSize) //如果栈2非空
{
return data[top2];
}
}
判断栈是否为空：
if (i == 1)
{
if (top1 == -1)
{
return true;
}
else
{
return false;
}
}
if (i == 2)
{
if (top2 == StackSize)
{
return true;
}
else
{
return false;
}
}
return false;
输出栈中元素：
int temp1 = top1; //工作指针
while (temp1 != -1) //判断栈一是否为空
{
cout<< data[temp1--] << " "; //输出元素，工作指针减一
}
int temp2 = top2; //工作指针
while (temp2 != StackSize) //判断栈二是否为空
{
cout<< data[temp2++] << " "; //输出元素，工作指针加一
}
2.2.2 链栈
析构函数：
while (top) //判断是否为空
{
struct Node
*p = top; //新建工作指针，并用top指针初始化
top = top->next; //top指针后移
delete p;
}
入栈：
struct Node*p = new Node; //新建工作指针指向新结点
p->data = x; //新结点的数据域赋值为x
p->next = top; //新节点的next域记录top指针指向地址
top = p; //栈顶指针该为p
出栈：
if (Empty()) throw"下溢";
T x = top->data; //保存数据
struct Node*p = top; //保存栈顶指针地址
top = top->next; //栈顶指针后移
delete p; //删除
return x; //返回数值
查找栈顶元素：
if (Empty()){ throw"empty"; }
return top->data;
3. 程序运行结果
1.共享栈测试主函数流程
开始
新建共享栈
入栈操作
出栈操作
查找栈顶元素
判断栈是否为空
输出栈中元素
结束
2.链栈测试主函数流程图
开始
新建数组
为数组元素赋值并入栈
出栈操作
查找栈顶元素
判断栈是否为空
执行析构函数
结束
程序运行结果：
源代码
#include
usingnamespacestd;
constintStackSize = 10; //定义栈的最大高度
template
classBothStack//定义两栈共享空间的c++模板类
{
public:
BothStack() //构造函数，初始化空栈
{
top1 = -1;
top2 = StackSize;
}
voidPush(inti, T1 x); //入栈操作
T1Pop(inti); //出栈操作
T1GetTop(inti); //查找栈顶元素
boolEmpty(inti); //判断栈是否为空栈
voidPrint(); //先打印栈1，再打印栈2
private:
T1data[StackSize];
inttop1, top2;
};
template
voidBothStack::Push(inti, T1x) //入栈函数
{
if (top1 == top2 - 1)
{
throw"上溢";
}
if (i == 1)
{
data[++top1] = x;
}
if (i == 2)
{
data[--top2] = x;
}
}
template
T1BothStack::Pop(inti) //出栈函数
{
if (i == 1)
{
if (top1 == -1) //判断栈1是否为空
{
throw"下溢";
}
returndata[top1--]; //返回出栈元素的值并且栈顶指针下移
}
if (i == 2)
{
if (top2 == StackSize)
{
throw"下溢";
}
returndata[top2++]; //返回出栈元素的值并且栈顶指针上移
}
return 0;
}
template
T1BothStack::GetTop(inti) //查找栈顶元素
{
if (i == 1)
{
if (top1 != -1)
{
returndata[top1];
}
}
if (i == 2)
{
if (top2 != StackSize)
{
returndata[top2];
}
}
return 0;
}
template
boolBothStack::Empty(inti) //判断栈是否为空
{
if (i == 1)
{
if (top1 == -1)
{
returntrue;
}
else
{
returnfalse;
}
}
if (i == 2)
{
if (top2 == StackSize)
{
returntrue;
}
else
{
returnfalse;
}
}
returnfalse;
}
template
voidBothStack::Print() //输出栈中元素
{
inttemp1 = top1;
while (temp1 != -1)
{
cout<
structNode
{
T2data;
structNode*next;
};
template
classLinkStack//定义链栈模板类
{
public:
LinkStack(){ top = NULL; } //构造函数，初始化空栈
~LinkStack(); //析构函数
voidPush(T2 x); //入栈操作
T2Pop(); //出栈操作
T2GetTop(); //查找栈顶元素
boolEmpty(){ return (NULL == top) ? true : false; } //判别栈是否为空
private:
structNode*top; //栈顶指针
};
template
LinkStack::~LinkStack() //析构函数
{
while (top) //判断是否为空
{
structNode*p = top;
top = top->next;
deletep;
}
}
template
voidLinkStack::Push(T2x) //入栈操作
{
structNode*p = newNode;
p->data = x;
p->next = top;
top = p;
}
template
T2LinkStack::Pop() //出栈操作
{
if (Empty()) throw"下溢";
T2x = top->data;
structNode*p = top;
top = top->next;
deletep;
returnx;
}
template
浙公网安备 33021202002483