数据结构栈和队列

实验二 栈和队列一、实验目的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)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;/入栈函数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 += STACKINCREMENT;* 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-)printf(%6d, *p);printf(n);/主函数void main() SqStack s;int cord; ElemType a;printf(第一次使用必须初始化！n);doprintf(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)Q.base=(QElemType*)malloc(MAXQSIZE*sizeof(QElemType);if(!Q.base)exit(OVERFLOW);Q.front=Q.rear=0;return OK;/判队列是否为空Status QueueEmpty (SqQueue Q) if(Q.rear=Q.front) return OK;else return ERROR ;/入队函数Status EnQueue (SqQueue &Q, QElemType e) if(Q.rear+1)%MAXQSIZE=Q.front) return ERROR;Q.baseQ.rear=e;Q.rear=(Q.rear+1)%MAXQSIZE;return OK;/出队函数Status DeQueue (SqQueue &Q, QElemType &e) if(Q.rear=Q.front) return ERROR;e=Q.baseQ.front;Q.front=(Q.front+1)%MAXQSIZE;return OK;/输出循环队列函数void OutQueue(SqQueue Q) int n, i;if(Q.front = Q.rear)printf(这是一个空队列！);elsen= (Q.rear- Q.front+ MAXQSIZE) % MAXQSIZE;i= 1;while ( i= n)printf(%6d, Q.base(Q.front+i-1)% MAXQSIZE );i+;printf(n);/主函数void main() SqQueue q;int cord; QElemType a;printf(第一次使用必须初始化！n);doprintf(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;case 4: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)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;/入栈函数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 += STACKINCREMENT;* S.top+ = e;return OK;/出栈函数Status Pop (SqStack &S, ElemType &e) if(S.top = S.base) return ERROR;e