实验二栈、队列的实现及应用实验课程名：数据结构与算法专业班级：学号：姓名：实验时间：实验地点：指导教师：冯珊一、实验目的1、掌握栈和队列的顺序存储结构和链式存储结构，以便在实际背景下灵活运用。

2、掌握栈和队列的特点，即先进后出与先进先出的原则。

3、掌握栈和队列的基本操作实现方法。

二、实验内容一、实验目的及要求1、掌握栈和队列的顺序存储结构和链式存储结构，以便在实际背景下灵活运用。

2、掌握栈和队列的特点，即先进后出与先进先出的原则。

3、掌握栈和队列的基本操作实现方法。

二、实验学时2学时三、实验任务任务一：（1）实现栈的顺序存储（2）实现栈的链式存储。

任务二：实现顺序存储的循环队列，完成键盘缓冲区的功能。

四、实验重点、难点1.进栈、出栈栈顶指针都要改变。

2.队空、队满的条件及入队、出队时指针的变更。

五、操作内容与要求1.任务一（1）：完成下列程序，该程序实现栈的顺序存储结构，构建顺序栈（栈中的元素依次为R，S，Y，F，C，T），依次进行进栈和出栈操作，判断栈空和栈满操作，返回栈顶元素操作。

要求生成顺序栈时，从键盘上读取数据元素。

（1）源代码：#include<stdio.h>#include<stdlib.h>#define STACK_INIT_SIZE 100#define STACKINCREMENT 10# define OK 1# define ERROR 0typedef char SElemType;/* 顺序栈的存储类型 */typedef struct//define structure SqStack(){SElemType *base;SElemType *top;int stacksize;}SqStack;/*构造空顺序栈*/int InitStack(SqStack *S) //InitStack() sub-function{S->base = (SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));if (!S->base){printf("分配空间失败!\n");return (ERROR);}S->top = S->base;S->stacksize = STACK_INIT_SIZE;printf("栈初始化成功！\n");return (OK);} //InitStack() end/*取顺序栈顶元素*/int GetTop(SqStack *S, SElemType *e) //GetTop() sub-function{if (S->top == S->base){printf("栈为空!\n"); //if empty SqStackreturn (ERROR);}*e = *(S->top - 1);return (OK);} //GetTop() end/*将元素压入顺序栈*/int Push(SqStack *S) //Push() sub-function{SElemType e;if (S->top - S->base>S->stacksize){S->base = (SElemType *)realloc(S->base, (S->stacksize +STACKINCREMENT*sizeof(SElemType)));if (!S->base){printf("存储空间分配失败!\n");return (ERROR);}S->top = S->base + S->stacksize;S->stacksize += STACKINCREMENT;}fflush(stdin);//清除输入缓冲区，否则原来的输入会默认送给变量xprintf("请输入要入栈的元素的值:");e = getchar();*S->top++ = e;return (OK);} //Push() end/* 将元素弹出顺序栈*/int Pop(SqStack *S, SElemType *e) //Pop() sub-function {if (S->top == S->base){printf("栈为空!\n");return (ERROR);}*e = *--S->top;return (OK);} //Pop() endvoid display(SqStack *s){if (s->top == s->base)printf("栈为空!\n");else{while (s->top != s->base){s->top = s->top - 1;printf("%c->", *(s->top));}}printf("\n");}int main(){int choice;SElemType e;SqStack s;do{printf("===============================\n");printf(" 0:退出\n");printf(" 1:初始化栈\n");printf(" 2:入栈\n");printf(" 3:出栈\n");printf(" 4:读取栈顶元素\n");printf(" 5:显示栈中元素\n");printf("===============================\n");printf("输入操作选择代码(0-5):");scanf("%d", &choice);while(choice<0 || choice>5) { printf("输入有误，请重新输入(0-5):"); scanf("%d", &choice); }switch (choice){case 0:exit(1);case 1:InitStack(&s); break;case 2:printf("2\n"); Push(&s); break;case 3:Pop(&s, &e); printf("出栈元素的值是:%c\n", e); break;case 4:GetTop(&s, &e); printf("栈顶元素的值是:%c\n", e); break;case 5: printf("栈中元素的值是为：\n"); display(&s); break;}} while (choice);return 0;}（2）运行结果（3）结果分析顺序表通过设置栈顶运用线性结构实现先进先出功能。

2.任务一（2）：完成下列程序，该程序实现栈的链式存储结构，构建链栈（栈中的元素依次为China，Japan，France，India，Australia），依次进行进栈和出栈操作，判断栈空和栈满操作，返回栈顶元素操作。

要求生成链栈时，从键盘上读取数据元素。

（1）源代码：#include<stdio.h>#include<stdlib.h>#include<string.h># define OK 1# define ERROR 0typedef char DataType;/* 链式栈的存储类型 */typedef struct SNode //define structure LinkStack{ DataType data[20];struct SNode *next;}SNode,*LinkStack;void InitStack_L (LinkStack *top){top = (LinkStack)malloc(sizeof(SNode)) ;top->next = NULL;printf("\n\n栈初始化成功！\n\n");}/*取链式栈顶元素*/int GetTop_L(LinkStack *top,DataType e[]) //GetTop_L() sub-function { if(!top->next){ printf("链栈为空!\n");return (ERROR);}else{ strcpy(e,top->next->data);return (OK);}} //GetTop_L() end/* 将元素压入链式栈*/int Push_L(LinkStack *top) //Push_L() sub-function{ SNode *q;DataType e[20];q=(LinkStack)malloc(sizeof(SNode));if(!q){ printf("存储空间分配失败! \n");return (ERROR);}fflush(stdin);//清除输入缓冲区，否则原来的输入会默认送给变量e printf("\n请输入要入栈的元素的值:");gets(e);strcpy(q->data,e);q->next=top->next;top->next=q;return (OK);} //Push_L() end/*将元素弹出链式栈*/int Pop_L(LinkStack *top,DataType e[]) //Pop_L() sub-function{ SNode *q;if(!top->next){ printf("链栈为空! \n ");return (ERROR);}strcpy(e,top->next->data);q=top->next;top->next=q->next;free(q);return (OK);} //Pop_L() endvoid display(LinkStack *top){LinkStack p=top->next;if(!p)printf("栈为空!\n");else{while(p){printf("%s->",p->data);p=p->next;}}printf("^\n");}int main(){char choice;DataType e[20]="";LinkStack s=NULL;do{printf("===============================\n"); printf(" 0:退出\n");printf(" 1:初始化栈\n");printf(" 2:入栈\n");printf(" 3:出栈\n");printf(" 4:读取栈顶元素\n");printf(" 5:显示栈中元素\n");printf("===============================\n"); printf("输入操作选择代码(0-5):");fflush(stdin);scanf("%c",&choice);while(choice<'0'||choice>'5'){printf("输入有误，请重新输入(0-5):");fflush(stdin);scanf("%c",&choice);}switch(choice){case '0':exit(1);case '1': InitStack_L(&s);break;case '2': Push_L(&s);break;case '3':Pop_L(&s, e);break;case '4':GetTop_L(&s, e);printf("栈顶元素的值是:%s\n",e);break; case '5': printf("栈中元素的值是: ");display(&s);}}while(choice);return 0;}（2）运行结果（3）结果分析链表通过设置栈顶运用指针实现先进先出功能3.任务二：完成下列程序，该程序实现循环队列的存储和基本操作，构建循环队列，完成键盘缓冲区的功能，每输入一个字符，链入缓冲区队列中；每输出一个字符，将该字符从缓冲区中删除。