数据结构栈和队列

实验二栈和队列一、实验目的1、掌握栈的特点(先进后出FILO)及基本操作，如入栈、出栈等，栈的顺序存储结构和链式存储结构，以便在实际问题背景下灵活应用。

2、掌握队列的特点(先进先出FIFO)及基本操作,如入队、出队等，队列顺序存储结构、链式存储结构和循环队列的实现，以便在实际问题背景下灵活应用。

二、实验内容1、顺序栈的实现和运算；2、循环队列的实现和运算；3、栈的运用—十进制转八进制运算。

三、实验要求1、学生用C++/C完成算法设计和程序设计并上机调试通过；2、撰写实验报告，提供实验测试数据和实验结果；3、分析算法，要求给出具体的算法分析结果，包括时间复杂度和空间复杂度，并简要给出算法设计小结和心得。

四、实验准备1、掌握栈和队列这两种抽象数据类型的特点，并能在相应的应用任务中正确选用它们；2、熟练掌握顺序栈和循环队列的基本操作实现算法，特别应注意栈满和栈空的条件以及它们的描述方法，循环队列中队满和队空的描述方法。

3、在学习顺序栈的基本操作实现算法时，应注意：在书上给出的结构定义是采用了一种动态管理方式（不够时，可以再分配），但在C 语言中，用数组来存储顺序栈，是静态分配，即不能随机分配空间，这点易引起大家的误解。

五、实验步骤1、编程实现顺序栈的各种基本运算，并在此基础上设计一个主程序，完成如下功能：(1)初始化顺序栈；(2)给定一个元素，将此元素压入此栈中；(3)将栈顶一个元素弹出此栈。

2、编写一个程序实现循环队列的各种基本运算，并在此基础上设计一个主程序，完成如下功能：(1)初始化循环队列；(2)给定一个元素，将此元素插入此队列中；(3)将队头一个元素出队。

3、栈的运用实例十进制转八进制。

六、实验参考代码1、顺序栈的实现和运算；#include <>#include <>#define OK 1#define ERROR 0#define OVERFLOW -2typedef int ElemType;typedef int Status;//----- 栈的顺序存储表示 -----#define STACK_INIT_SIZE 100 // 存储空间的初始分配量#define STACKINCREMENT 10 // 存储空间的分配增量typedef struct {ElemType *base;ElemType *top;int stacksize;} SqStack;// 构造一个空栈SStatus InitStack(SqStack &S){= (ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType)); if(! exit (OVERFLOW);= ;= STACK_INIT_SIZE;return OK;}// 判栈S是否为空栈Status StackEmpty(SqStack S){if == return OK;else return ERROR;}//入栈函数Status Push (SqStack &S, ElemType e) {if - >= {=(ElemType*)realloc,+STACKINCREMENT)* sizeof(ElemType)); if(! exit (OVERFLOW);= + ;+= STACKINCREMENT;}* ++ = e;return OK;}//出栈函数Status Pop (SqStack &S, ElemType &e) {if == return ERROR;e = * ;return OK;}//输出顺序栈函数void OutStack(SqStack S){ int *p;if == {printf("这是一个空栈！");}elsefor(p= ; p>= ;p--)printf("%6d", *p);printf("\n");}//主函数void main(){ SqStack s;int cord; ElemType a;printf("第一次使用必须初始化！\n");do{printf("\n 主菜单 \n");printf(" 1 初始化顺序栈 ");printf(" 2 插入一个元素 ");printf(" 3 删除栈顶元素 ");printf(" 4 结束程序运行 ");printf("\n------------------------------------------------------------------------------\n");printf("请输入您的选择( 1, 2, 3, 4)");scanf("%d",&cord);printf("\n");switch(cord){ case 1:InitStack(s);OutStack(s);break;case 2:printf("请输入要插入的数据元素：a=");scanf("%d",&a);Push(s,a);printf("%d 进栈之后的栈：",a);OutStack(s);break;case 3:Pop(s,a);printf("栈顶元素 %d 出栈之后的栈：",a);OutStack(s);break;case 4:exit(0);}}while (cord<=4);}2、循环队列的实现和运算；#include <>#include <>#define OK 1#define ERROR 0#define OVERFLOW -2typedef int QElemType;typedef int Status;//----- 队列的顺序存储表示 -----#define MAXQSIZE 100 // 存储空间的初始分配量typedef struct {QElemType *base;int front;int rear;} SqQueue;// 构造一个空队列QStatus InitQueue(SqQueue &Q){=(QElemType*)malloc(MAXQSIZE*sizeof(QElemType)); if(!exit(OVERFLOW);==0;return OK;}//判队列是否为空Status QueueEmpty (SqQueue Q) {if== return OK;else return ERROR ;}//入队函数Status EnQueue (SqQueue &Q, QElemType e) {if(+1)%MAXQSIZE== return ERROR;[]=e;=+1)%MAXQSIZE;return OK;}//出队函数Status DeQueue (SqQueue &Q, QElemType &e) {if== return ERROR;e=[];=+1)%MAXQSIZE;return OK;}//输出循环队列函数void OutQueue(SqQueue Q){ int n, i;printf("这是一个空队列！");}else{n= + MAXQSIZE) % MAXQSIZE;i= 1;while ( i<= n){printf("%6d", [+i-1)% MAXQSIZE] );i++;}printf("\n");}}//主函数void main(){ SqQueue q;int cord; QElemType a;printf("第一次使用必须初始化！\n");do{printf("\n 主菜单 \n");printf(" 1 初始化循环队列 ");printf(" 2 进队一个元素 ");printf(" 3 出队一个元素 ");printf(" 4 结束程序运行 ");printf("\n------------------------------------------------------------------------------\n");printf("请输入您的选择( 1, 2, 3, 4)");scanf("%d",&cord);printf("\n");switch(cord){ case 1:InitQueue(q); //调用初始化算法;OutQueue(q);break;case 2:printf("请输入要插入的数据元素：a=");scanf("%d",&a);EnQueue (q, a); //调用进队算法;printf("%d 进队之后的队列：",a);OutQueue(q);break;case 3:DeQueue (q, a); //调用出队算法;printf("队头元素 %d 出队之后的队列：",a);OutQueue(q);break;exit(0);}}while (cord<=4);}3、栈的应用—十进制转八进制#include <>#include <>#define OK 1#define ERROR 0#define OVERFLOW -2typedef int ElemType;typedef int Status;#define STACK_INIT_SIZE 100#define STACKINCREMENT 10typedef struct {ElemType *base;ElemType *top;int stacksize;} SqStack;// 构造一个空栈SStatus InitStack(SqStack &S){= (ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType)); if(! exit (OVERFLOW);= ;= STACK_INIT_SIZE;return OK;}// 判栈S是否为空栈Status StackEmpty(SqStack S){if == return OK;else return ERROR;}//入栈函数Status Push (SqStack &S, ElemType e) {if - >= {=(ElemType*)realloc,+STACKINCREMENT)* sizeof(ElemType)); if(! exit (OVERFLOW);= + ;+= STACKINCREMENT;}* ++ = e;return OK;}//出栈函数Status Pop (SqStack &S, ElemType &e) {if == return ERROR;e = * ;return OK;}//十进制转八进制函数void conversion(){ SqStack S;int n,e;InitStack(S);printf("请输入一个十进制数：");scanf("%d",&n);while(n){Push(S,n%8);n=n/8;}printf("转换之后的八进制数为：");while(!StackEmpty(S)){Pop(S, e);printf("%d",e);}printf("\n");}void main(){conversion();}。