数据结构栈和队列

1、实验二栈和队列、实验目的1、掌握栈的特点（先进后出FILO）及基本操作，如入栈、出栈等，栈的顺序存储 结构和链式存储结构，以便在实际问题背景下灵活应用。2、掌握队列的特点（先进先出FIFO）及基本操作,如入队、出队等，队列顺序存储 结构、链式存储结构和循环队列的实现，以便在实际问题背景下灵活应用。二、实验内容1、顺序栈的实现和运算；2、循环队列的实现和运算；3、栈的运用一十进制转八进制运算。三、实验要求1、学生用C+/C完成算法设计和程序设计并上机调试通过；2、撰写实验报告，提供实验测试数据和实验结果；3、分析算法，要求给出具体的算法分析结果，包括时间复杂度和空间复杂度， 并简要给出算法设计小

2、结和心得。四、实验准备1、掌握栈和队列这两种抽象数据类型的特点，并能在相应的应用任务中正确选用它们；2、熟练掌握顺序栈和循环队列的基本操作实现算法，特别应注意栈满和栈空的 条件以及它们的描述方法，循环队列中队满和队空的描述方法。3、在学习顺序栈的基本操作实现算法时，应注意：在书上给出的结构定义是采 用了一种动态管理方式（不够时，可以再分配），但在 C语言中，用数组来存储顺序栈，是静态分配，即不能随机分配空间，这点易引起大家的误解 五、实验步骤1、编程实现顺序栈的各种基本运算，并在此基础上设计一个主程序，完成如下功能：(1) 初始化顺序栈；(2) 给定一个元素，将此元素压入此栈中；(3) 将栈顶

3、一个元素弹出此栈。2、 编写一个程序实现循环队列的各种基本运算，并在此基础上设计一个主程序,完成如下功能：(1) 初始化循环队列；(2) 给定一个元素，将此元素插入此队列中；(3) 将队头一个元素出队。3、 栈的运用实例十进制转八进制。六、实验参考代码1、顺序栈的实现和运算；#i nclude #i nclude #defi ne OK 1#defi ne ERROR 0#defi ne OVERFLOW -2typedef int ElemType;typedef int Status;II栈的顺序存储表示#defi ne STACK_INIT_SIZE 100 II 存储空间的初始分配量#

4、defi ne STACKINCREMENT 10 II 存储空间的分配增量typedef struct ElemType *base;ElemType *top;int stacksize; SqStack;/构造一个空栈SStatus In itStack(SqStack & S)S.base = (ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType);if(!S.base) exit (OVERFLOW);S.top = S.base;S.stacksize = STACK_INIT_SIZE;return OK;/判栈S是否为空栈St

5、atus StackEmpty(SqStack S)if (S.top=S.base) return OK;else return ERROR;/入栈函数Status Push (SqStack &S, ElemType e) if(S.top - S.base = S.stacksize)S.base=(ElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)* sizeof(ElemType); if(!S.base) exit (OVERFLOW);S.top = S.base + S.stacksize;S.stacksize += S

6、TACKINCREMENT;* S.top+ = e;return OK;/出栈函数Status Pop (SqStack &S, ElemType &e) if(S.top = S.base) return ERROR;e = * -S.top;return OK;/输出顺序栈函数void OutStack(SqStack S) int *p;if(S.top = S.base)printf(”这是一个空栈！”)；elsefor(p= S.top-1; p= S.base;p-)prin tf(%6d, *p);prin tf(n);/主函数void mai n() SqStack s;in

7、t cord; ElemType a;printf(”第一次使用必须初始化！n);doprin tf(n主菜单n);prin tf( 1初始化顺序栈printf( 2插入一个兀素printf( 3删除栈顶兀素printf( 4结束程序运行prin tf(n-n);printf(”请输入您的选择(1,2, 3, 4);sca nf(%d,&cord);prin tf(n);switch(cord) case 1:In itStack(s);OutStack(s);break;case 2:printf(”请输入要插入的数据元素：a=);sca nf(%d,&a);Push(s,a);printf

8、(%d进栈之后的栈：”,a);OutStack(s);break;case 3:Pop(s,a);printf(”栈顶元素 %d出栈之后的栈：,a);OutStack(s);break;case 4:exit(0);while (cord=4);2、循环队列的实现和运算；#in clude #in clude #define OK 1#define ERROR 0#define OVERFLOW -2typedef int QElemType;typedef int Status;II队列的顺序存储表示#defi ne MAXQSIZE 100 II存储空间的初始分配量typedef stru

9、ct QElemType *base;int front;int rear; SqQueue;II构造一个空队列QStatus Ini tQueue(SqQueue & Q)Q.base=(QEIemType*)malloc(MAXQSIZE*sizeof(QEIemType); if(!Q.base)exit(OVERFLOW);Q.fro nt=Q.rear=0;return OK;II判队列是否为空Status QueueEmpty (SqQueue Q) if(Q.rear=Q.front) return OK;else return ERROR ;II入队函数Status En Qu

10、eue (SqQueue &Q, QElemType e) if(Q.rear+1)%MAXQSIZE=Q.fro nt) return ERROR; Q.baseQ.rear=e;Q.rear=(Q.rear+1)%MAXQSIZE;return OK;II出队函数Status DeQueue (SqQueue &Q, QElemType &e) if(Q.rear=Q.front) return ERROR;e=Q.baseQ.fr on t;Q.fro nt=(Q.fro nt+1)%MAXQSIZE;return OK;II输出循环队列函数void OutQueue(SqQueue Q

11、) int n, i;if(Q.fro nt = Q.rear)printf(”这是一个空队列！);elsen= (Q.rear- Q.fro nt+ MAXQSIZE) % MAXQSIZE;i= 1;while ( i= n)printf(%6d, Q.base(Q.front+i-1)% MAXQSIZE); i+；prin tf(n);/主函数void mai n() SqQueue q;int cord; QElemType a;printf(”第一次使用必须初始化！n);doprin tf(n主菜单n);prin tf( 1初始化循环队列)printf(” 2进队一个兀素);pri

12、ntf(” 3出队一个兀素);printf(” 4结束程序运行);prin tf(n-n);printf(”请输入您的选择(1,2, 3, 4);sca nf(%d,&cord);prin tf(n);switch(cord) case 1:InitQueue(q); / 调用初始化算法；OutQueue(q);break;case 2:printf(”请输入要插入的数据元素：a=);sca nf(%d,&a);EnQueue (q, a); /调用进队算法; printf(%d进队之后的队列：,a); OutQueue(q);break;case 3:DeQueue (q, a); /调用出

13、队算法；printf(”队头元素 %d出队之后的队列：”,a);OutQueue(q);break;case 4:exit(0);while (cord=4);3、栈的应用一十进制转八进制#in clude #i nclude #defi ne OK 1#defi ne ERROR 0#defi ne OVERFLOW -2typedef int ElemType;typedef int Status;#defi ne STACK_INIT_SIZE 100#defi ne STACKINCREMENT 10typedef struct ElemType *base;ElemType *top

14、;int stacksize; SqStack;/构造一个空栈SStatus In itStack(SqStack & S)S.base = (ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType);if(!S.base) exit (OVERFLOW);S.top = S.base;S.stacksize = STACK_INIT_SIZE;return OK;判栈S是否为空栈Status StackEmpty(SqStack S)if (S.top=S.base) return OK;else return ERROR;/入栈函数Statu

15、s Push (SqStack &S, ElemType e) if(S.top - S.base = S.stacksize)S.base=(ElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)* sizeof(ElemType); if(!S.base) exit (OVERFLOW);S.top = S.base + S.stacksize;S.stacksize += STACKINCREMENT;* S.top+ = e;return OK;出栈函数Status Pop (SqStack &S, ElemType &e) if(S.top = S.base) return ERROR;e = * -S