数据结构栈与队列报告_数据结构栈和队列经典
数据结构栈与队列报告由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“数据结构栈和队列经典”。
栈和队列上机实习
1、实验目的：
（1）熟练掌握栈的逻辑结构和操作规则，能在相应的实际问题中正确选用该结构。（2）熟练掌握栈的2种存储结构实现方法（顺序栈和链栈），两种存储结构和基本运算的实
现算法，注意栈空盒满的判断条件及它们的描述方法。
（3）熟练掌握队列的逻辑结构和操作规范，能在相应的实际问题中正确选用该结构。（4）掌握循环队列与链队列两种存储结构的实现，熟练掌握各种队列基本运算的实现。
2、实验要求：
（1）顺序栈的插入、删除，栈顶数据元素的读取。（2）链栈的插入、删除，栈顶数据元素的读取。（3）循环队列的插入、删除。（4）链队列的插入、删除。
3、实验内容: ① 栈
（1）抽象数据类型定义
typedef struct
{
ElemType data[MaxSize];
//栈的空间大小为MaxSize
int top;
//设置栈顶指针
}SqStack;
//栈的结构定义
在本次实验中，首先建立一个空栈，进入主程序后首先初始化栈为其分配空间，然后进入菜单选择界面，通过不同的数字输入，实现入栈，出栈，读取栈顶元素，显示栈的所有元素，栈的长度，释放栈等操作。
（2）存储结构定义及算法思想
在栈结构体的定义中，typedef int Typeelem 为整型，存储结构（入栈）如下：
cin>>a;
s->top++;
//在入栈是首先将栈顶指针向上加1
s->data[s->top]=a;
//与数组赋值一样，直接赋值
//其他存储与此类似，都是直接赋值与数组的某一位
退栈函数模块：
void Pop(SqStack * &s){
//对指针的引用
if(s->top ==-1){
cout
//首先判断是否为空栈，若为空，则退出
return;} coutdata[s->top]
//显示退栈元素
s->top--;
//栈顶元素减1，指向实际栈的最上面 }
显示栈所有元素函数模块：
void DispStack(SqStack *s){
//从栈顶到栈底顺序显示所有元素
int i;couttop;i>=0;i--){ coutdata[i]
//同过循环实现实现从栈顶元素到栈底元素的遍历以输出
} cout
栈结构的入栈和退栈是两个相反的过程，先进后出，入栈是先让栈顶指针加1,指向未被赋值位置，然后进行赋值，退栈是先取出退栈元素，然后栈顶元素减1，指向推展后的实际栈顶。诸如读取栈顶元素，显示栈的元素，读取栈的长度，都是用过对栈顶指针实现相关操作。
（3）实验结果与分析
② 循环队列
（1）抽象数据类型定义
typedef struct {
ElemType elem[Maxqsize];
//循环队列的长度为MaxSize
int front,rear;
//设置队列的头指针和尾指针
}SqQueue;
//循环队列的结构体定义
在本次实验中，首先建立一个空队列，进入主程序后首先初始化队列为其分配空间，然后进入菜单选择界面，通过不同的数字输入，实现入队，出队，显示队列的所有元素，队列的长度，释放队列等操作。
（2）存储结构定义及算法思想
在队列结构体的定义中，typedef int Typeelem 为整型，存储（入队）结构如下：
q->rear=(q->rear+1)%Maxqsize;
//尾指针加1
q->elem[q->rear]=a;
//将入队元素装到新的空尾部
在此队列的存储结构的实现：先让队尾指针进1，再将新的元素加入到队尾指针所指示的位置，因此，队尾指针指示实际的队尾位置，队头指针指示实际队头的前一位置，要想退出队头元素，必须先让队头指针进1，才能取出队头元素。
退队函数模块如下：
void deQueue(SqQueue *&q){
//对指针的引用
if(QueueEmpty(q))
{
//调用带返回值的判断空队函数
cout
//判断队列是否为空
}
q->front=(q->front+1)%Maxqsize;
//队头指针进1
coutelem[q->front]
//取出队头元素 }
遍历队表函数：
void displayqueue(SqQueue *q){
int m;m=q->front+1;
//队头元素进1，指向实际队头
if(QueueEmpty(q))
{
cout
//判断是够为空队
}
cout
while(q->rear+1>m){
coutelem[m]
//通过循环遍历所有元素
m++;
}
cout
循环队列的入队和退队分别是在队尾与队头跟别进行操作的，通过队头队尾指针的操作便可实现对队列的相关操作。
（3）实验结果与分析
③ 心得体会
本次上机是做栈与队列的操作，这次实验，我有意的用到了对指针的引用与指针实现子函数功能的调用，刚开始编译的时候也有错误，但是在慢慢的摸索中，也逐渐掌握了它们的用法，这次实验也让我熟练了对队列与栈存储结构的应用。
附录：
顺序表源代码: 栈：
#include using namespace std;#define MaxSize 5 typedef int ElemType;int e;typedef struct { ElemType data[MaxSize];int top;}SqStack;
void InitStack(SqStack * &s)
//建立一个空栈，即将栈顶指针指向-1即可 的引用 { s=(SqStack *)malloc(sizeof(SqStack));s->top=-1;}
void ClearStack(SqStack * &s)
//释放栈s占用的存储空间 { free(s);}
void StackLength(SqStack *s)
{ couttop +1)
int StackEmpty(SqStack *s){ return(s->top==-1);}
void Push(SqStack *&s){ if(s->top==MaxSize-1)
{
cout
//
s=(SqStack *)realloc(s,sizeof(SqStack));} int a;
指针
cout>a;s->top++;s->data[s->top]=a;}
void Pop(SqStack * &s){ if(s->top ==-1){
cout
return;} coutdata[s->top]top--;}
void GetTop(SqStack * &s,ElemType &e){ if(s->top==-1){coutdata[s->top];}
void DispStack(SqStack *s)
//从栈顶到栈底顺序显示所有元素 { int i;couttop;i>=0;i--){ coutdata[i]
cout
cout
入栈
1“
cout
出栈
2”
cout
读取栈顶元素
3“
cout
显示栈所有元素
4”
cout
栈的长度
5“
cout
释放栈
6”
cin>>k;
switch(k)
{
case 1: Push(s);break;
case 2: Pop(s);break;
case 3: GetTop(s,e);cout
case 4: DispStack(s);break;
case 5: StackLength(s);break;
case 6: ClearStack(s);break;
default :break;
} } }
队列：
#include using namespace std;#define Maxqsize 8 typedef int TypeElem;typedef struct {
TypeElem elem[Maxqsize];
int front,rear;}SqQueue;void InitQueue(SqQueue *&q){
q=(SqQueue *)malloc(sizeof(SqQueue));
q->front=q->rear=0;} void ClearQueue(SqQueue *&q){
free(q);exit(0);} void QueueLength(SqQueue *q){
coutrear-q->front+Maxqsize)%Maxqsize
return(q->front==q->rear);
} void enQueue(SqQueue *&q){ int a;
if((q->rear+1)%Maxqsize==q->front)
{
cout
}
cout
cin>>a;
q->rear=(q->rear+1)%Maxqsize;
q->elem[q->rear]=a;} void deQueue(SqQueue *&q){
if(QueueEmpty(q))
{
cout
}
q->front=(q->front+1)%Maxqsize;
coutelem[q->front]
}
void displayqueue(SqQueue *q){
int m;m=q->front+1;
if(QueueEmpty(q))
{
cout
}
cout
while(q->rear+1>m)
{
coutelem[m]
m++;
}
cout
int k=0;
SqQueue *q;
InitQueue(q);
if(QueueEmpty(q))cout
while(1){
cout
cout
入队
cout
出队
cout
队列长度
cout
显示队列元素
cout
释放栈
cin>>k;
switch(k)
{
case 1: enQueue(q);break;
case 2: deQueue(q);break;
case 3: QueueLength(q);break;
case 4: displayqueue(q);break;
case 5: ClearQueue(q);break;
default :break;
} } }
1“
2”
4"
