数据结构实验二-栈和队列的基本操作与应用

实验日期2010.4.26教师签字________________ 成绩__________【实验名称】第三章栈和队列的基本操作及应用【实验目的】（1）熟悉栈的特点（先进后出）及栈的基本操作，如入栈、出栈等，掌握栈的基本操作在栈的顺序存储结构和链式存储结构上的实现；（2）熟悉队列的特点（先进先出）及队列的基本操作，如入队、出队等，掌握队列的基本操作在队列的顺序存储结构和链式存储结构上的实现。

【实验内容】1.链栈的基本操作（链栈的初始化、进栈、出栈以及取栈顶的值)#include H stdio.h H#include H malloc.h ninclude "stdlib.h"typedef int Elemtype;typedef struct stacknode {Elemtype data;stacknode * next;JStackNode;typedef struct {stacknode * top; 〃栈顶指针} LinkStack;/*初始化链栈*/void InitStack(LinkStack * s){ s->top=NULL;printf("\n已经初始化链栈！\n”)；)/*链栈置空*/void setEnipty(LinkStack * s){ s・>top 二NULL;printf(H\n 链栈被置空! \n”)；}/*入栈*/void pushLstack(LinkStack * s, Elemtype x){ StackNode * p; p=(StackNode *)maHoc(sizeof(StackNode)); 〃建立一个节点° p->data=x;p->next=s->top; //ill于是在栈顶pushLstack,所以要指向栈顶。

s->top=p; 〃插入}/*出栈勺Elemtype popLstack(LinkStack * s){ Elemtype x;StackNode * p; p=s->top; 〃指向栈顶if (s->top ==0){ printf("\n栈空，不能出栈！\n”)； exit(-l);}x=p->data;s->top=p->next; 〃当前的栈顶指向原栈的nextfree(p); 〃释放return x;}/*取栈顶元素*/Elemtype StackTop(LinkStack *s){ if (s->top ==0){ printf(H\n 链栈空\n”)；exit(-l);)return s->top->data;}/*遍历链栈*/void Disp(LinkStack * s){ printf("\n链栈中的数据为：\n");printf(H======================================\n n); StackNode * p;p=s->top;while (p!=NULL){ printf(H%d\n'\p->data);p=p->next;} printf("=======================================\n");}void main(){ printf(H====================链栈操作==========\n\nj;int i,m,n,a; LinkStack * s; s=(LinkStack *)malloc(sizeof(LinkStack)); int cord;do{ printf(H\n n);printf(”第一次使用必须初始化! \n H);printf(H\ii 主菜单W);printf(H\n 1 初始化链栈\n“);printf(H\n 2 入栈\n“);printf(M\ii 3 出栈\n")；printf(H\n 4 取栈顶元素\n")；printf(H\n 5 置空链栈\n")；printf(H\n 6 结束程序运行\n”);printf(H\n ---------------------------------printfC*请输入您的选择(1,2, 3, 4, 5,6)”)；scanf(M%d,\&cord);printf(H\n n);switch(cord){ case 1:{ InitStack(s);Disp(s);} break;case 2:(printfC输入将要压入链栈的数据的个数：I匸“)；scanf(”％d”,&n);printf(”依次将％d个数据圧入链栈：\n",n);for(i=l;i<=n;i++){scanf("%d”,&a); pushLstack(s,a);}Disp ⑸；[break;case 3:{ printf("\n出栈操作开始!\n“)； printf("输入将要出栈的数据个数：m=”)；scrmf(”％d：&m);for(i=I;i<=m;i++){printf("\n 第％d 次出栈的数据是：%d",i,popLstack(s));)Disp(s);[break;case 4:{ printf("\n\n 链栈的栈顶元素为：%d\n",StackTop(s)); printf(H\n H);(break;case 5:{ setEnipty(s);Disp(s);(break;case 6:exit(O);})while (cord<=6);}2.顺序栈的基本操作(顺序栈的初始化、进栈、出栈以及取栈顶的值) #include<stdio.h>#include<malloc.h>#include<stdlib.h>#define STACKSIZE 100#define STACKINCREMENT 10#define null 0typedef struct {int 水base;int *top;int stacksize;}SqStack;SqStack Initstack(){SqStack S;S.base=(int *)malloc(STACKSIZE*sizeof(int));if(!S.base){printf("\n 存储分配失败\n");exit(0);}S.top=S.base;S.stacksize 二STACKSIZE;return S;}int StackEmpty(SqStack S){if(S.top==S.base) return 1;else return 0;}int StackLength(SqStack S){int *p;p=S.base;for(int i=0;p!=S・top;p++,i++);return i;int GetTop(SqStack S)int e;if(StackEmpty(S)) {printf(”当前栈为空,不能执行此操作\n”);exit(O);}e=*(S.top-l);return e;}int Push(SqStack &Sjnt e){if(StackLength(S)>=S.stacksize) {S.base=(int*)realloc(S.base,(STACKSIZE+STACKINCREMENT)*sizeof(int));if(!S.base){printf("\n 再分配存储失败\n");return 0;}S ・ top=S ・ base+S. stacksize;S.stacksize+二STACKINCREMENT;}*S.top++=e;return 1;}int Pop(SqStack &S){int e;if(StackEmpty(S)){printf("当前栈为空,不能执行此操作\n”);exit(0);}e=*—S.top;return e;}void main(){int i=0,e;int *p;SqStack S;S=Initstack();printf("\n 1.元素进栈\n 2.元素出栈\n 3.取栈顶元素\n 4. 求栈的长度\n 5.判栈空\n 6.退出\n“)；for(;i!=6;){printf(“\n请选择你要进行的操作：“)；scanf(H%d\&i);switch(i){case l:printf("\n请输入进栈元素：")；scanf(”％cT,&e);Push(S,e);p=S.base;printf("\n当前栈中元素："); if(StackEmpty(S))printfC'当前栈为空\n”); while(p!=S.top){printf(n%d '\*p);p++;}break;case 2:printf("\n%d 已出栈\n",Pop(S)); printf("\n当前栈中元素：”)；if(StackEmpty(S))printf(,'当前栈为空\n“);p=S.base;while(p !=S .top) {printf(" %d ",*p);p++;} break;case 3:printf("\n 栈顶元素为:%d\n",GetTop(S));break;case 4:printf("\n 栈的长度为:%d\n",StackLength(S));break;case 5:if(StackEmpty(S))printf("\n 当前栈为空\n");else printf("\n 当前栈不空\n"); break;default:printf("\n 退出程序\n");}}}3•顺序队列的基本操作(顺序队的初始化、进队、出对以及取对头)#include <stdio.h>#include <malloc.h>#define MAXNUM 100#define Elemtype int#define TRUE 1#define FALSE 0typedef struct{ Elemtype queuefMAXNUM];int front;int rear;Jsqqueue;/*队列初始化*/int initQueue(sqqueue *q){ if(!q) return FALSE;q->front=-1;q->rear=-1;return TRUE;}/*入队*/int append(sqqueue Elemtype x){ if(q->rear>=MAXNUM-1) return FALSE;q->rear++;q->queue[q->rear]=x;return TRUE;/*出队*/Elemtype Delete(sqqueue *q){ Elemtype x;if (q->front==q->rear) return 0;x=q->queue[++q->front];return x;}/*判断队列是否为空*/int Empty(sqqueue *q){ if (q->front=q->rear) return TRUE;return FALSE;}/*取队头元素*/int gethead(sqqueue *q){ if (q->front==q->rear) return 0; return(q->queue[q->front+1]);)/*遍历队列*/void display(sqqueue *q){ int s;s=q->front;if (q->front==q->rear) printf(”队列空!\n“)；else{printf("\n顺序队列依次为：“)；while(s<q->rear){s=s+l;printf(H%d<-'\ q->queue[s]);}printf(H\n H);printf("顺序队列的队尾元素所在位置:rear=%d\n",q->rear); printf("顺序队列的队头元素所在位S: front=%d\n " ,q->front);})/*建立顺序队列*/void Setsqqueue(sqqueue *q){ int njjn;printf("\n请输入将要入顺序队列的长度:”)；scanf(H%d,r,&n);printfC*\n请依次输入入顺序队列的元素值:\n“)；for (i=0;i<n;i++){ scanf(”％d”,&m);append(qjn);}main(){ sqqueue *head;int x,y,z,select; head=(sqqueue*)malloc(sizeof(sqqueue));do{printf("\n第一次使用请初始化！\n");printf("\n 请选择操作(1 -7):\n”)；pri ntf("=================================\n"); printf(n l 初始化\n“)；printf("2建立顺序队列\n");printf("3 入队\n”);printf("4 出队\n“)；printf("5判断队列是否为空\n“)；printf("6取队头元素\n");printf(H7 遍历队列\n“)；printf(,,===================================\n");scanf("%d",&select);switch(select){case 1:{ initQueue(head);printfC'B经初始化顺序队列! \n“)； break;)case 2:{ Setsqqueue(head);printf("\n已经建立队列！\n");display(head); break;)case 3:{ printf("请输入队的值:\n”)；scanf(”％cT,&x);append(head,x)； display(head);break;)case 4:{ z=Delete(head);printf("\n队头元素％(1已经出队！\n",z); display(head);break;)case 5:if(Empty(head))printf(”队列空\n”)；elseprintf("队列非空\n“)；break;}case 6:{ y=gethead (head);printf("队头元素为:%d\n",y);break;)case 7:{ display(head);break;}}}while(select<=7);}4•链队列的基本操作(链队列的初始化、进队、出对操作)#include<stdio.h>#include<stdlib.h>#define ElemType inttypedef struct Qnode{ ElemType data;struct Qnode *next;(Qnodetype;typedef struct{ Qnodetype *front;Qnodetype *rear;JLqueue;/*初始化并建立链队列*/void creat(Lqueue *q){ Qnodetype *h;int i,n,x;printf(”输入将建立链队列元素的个数：n=”);scanf(“％d",&n);h=(Qnodetype*)malloc(sizeof(Qnodetype));h->next=NULL;q->front=h;q->rear=h;for(i=l;i<=n;i++){ printfC链队列第％<1个元素的值为：”,i);scanf(“％d”,&x);Lappend(q,x);)/*入链队列*/void Lappend(Lqueue *q,int x){ Qnodetype *s; s=(Qnodetype*)manoc(sizeof(Qnodetype)); s->data=x;s->next=NULL;q->rear->next=s;q->rear=s;}/*出链队列勺ElemType Ldelete(Lqueue *q){ Qnodetype *p;ElemType x;if(q->front==q->rear){ printfC* 队列为空!\n“);x=0;)else{ p=q->front->next;q->front->next=p->next; if(p->next=NULL) q->reai*=q->front;x=p->data;free(p);}return(x);)/*遍历链队列*/void display(Lqueue *q){ Qnodetype *p;p=q->front->next; /*指向第一个数据元素节点*/printf("\n链队列元素依次为：”);while(p!=NULL){ printf("%d—>",p->data);p=p->next;}printf(H\n\n遍历链队列结束！\n n);}main(){ Lqueue *p;int x^cord;printf(H\n*****第一次操作请选择初始化并建立链队列！ **林*\口”);W)； switch(cord){ case 1:{ p=(Lqueue *)malloc(sizeof(Lqueue)); creat(p);display(p);} break;case 2:{ printf (“请输入队列元素的值：x=“);scanf(”％d”,&x);Lappend(p,x); display(p);(break;case 3:{ printf(n 出链队列元素:x=%d\ii*\Ldelete(p));display(p);(break;case 4:{display(p);) break;case 5:{exit (0);) }(while (cord<=5);) 5 •循环队列的基本操作:#include<stdio.h> #include<iostream.h> #include<malloc.h> #define maxsize 100 struct Queueint *base; int front; int rear;)；void initQueue(Queue &Q){Q.base=(int *)malloc(maxsize*sizeof(int));Q.front=Q.rear=0; printf(M 1初始化并建立链队列 \n n ); printf (” 2入链队列 S'); printf (” 3 出链队列 S');printf(H 4 遍历链队列W); printf(H 5 结束程序运行W); 主菜单 W)； printf(H =======================================\n H );printf(Hscanf(M %d 1',&cord);do { printf(H \n链队列的基本操作\n J ； printf(H = printf(n W)；}int QueueLen(Queue Q){return(Q.rear- Q・ front+maxsize)%maxsize;}void EnQueue(Queue &Q,int e){if((Q.rear+1 )%maxsize=Q.front)cout«"队列已满，无法插入!"«endl;else{Q.base[Q.rear]=e; Q.reai-(Q.rear+ l)%maxsize;)}int DeQueue(Queue &Q,int &e){if(Q.reai"==Q.front) coutvv"队列已空，无法删除「vvendl; else{e=Q.base[Q.front]; Q.front=(Q.front+1 )%maxsize;cout«"被删除的元素是:,,<<'\t'«e«endl;return e;})void main(){Queue Q;initQueue(Q);loop:cout«、Fvv"请选择你要进行的操作:"«endl;cout«'\t'«" 1 .插入元素"<<endl«'\t'«,'2.删除元素"<<endl«,\t'«"3.求队列长度,,<<endl«,\t,«,,4.结束u«endl;int i; cin»i;switch(i){case(l):{int e;coutvv”请输入要插入的元素: cin»e;EnQueue(Q,e);goto loop;}case(2):{int e;DeQueue(Q.e);goto loop;}case(3):{int 1;l=QueueLen(Q);cout«"队列的长度为:"«'\t'«l«endl; goto loop;)case(4): break;default:cout«"输入错误，请重新输入!"«endl;goto loop;}}6 •两个栈实现队列的功能#include<stdio.h>#include<malloc.h>#include<stdlib.h>#include<iostream.h>#define STACK_INIT_SIZE 100#define STACKINCREMENT 10typedef char SElemType;typedef struct{SEIeniType *base;SEleniType *top;int stacksize;JSqStack;〃队列III两个栈S1.S2构成typedef struct{SqStack S1;SqStack S2;}Queue;void InitStack(SqStack *S)S->base=(SElemType *)malloc(STACKJNIT_SIZE*sizeof(SElemType)); if(!S->base) exit(O);S->top=S->base; S->stacksize=STACK_INIT_SIZE;}void push(SqStack *S,SElemType e){if(S->top-S->base==S->stacksize){S・> base=(SElemType*)realloc(S->base,(S->stacksize+STACKINCREMENT)*sizeof(SElemType));if(!S->base) exit(O);S->top=S->base+S->stacksize;S->stacksize+=STACKINCREMENT;}*(S->top)++=e;}void pop(SqStack *S,SElemType *e){if(S->top==S->base) exit(O);S->top—; *e=*(S->top);}〃队列的相关操作void InitQueue(Queue *Q){InitStack(&(Q->S 1 ));InitStack(&(Q->S2));}void EnQueue(Queue *Q,SElemType e){push(&(Q->S l),e);)void DeQueue(Queue *Q,SElemType *e){if((Q->S2). top==(Q->S2). base){while((Q->S 1 ).top!=(Q->S 1 ).base) {pop(&(Q->S 1 ),e);push(&(Q->S2),*e);} pop(&(Q->S2),e);}else pop(&(Q->S2),e);}int QueueEmpty(Queue Q)if(Q.S 1 .base==Q.S 1 .top&&Q・S2・bjse==Q・S2・top) return 0; else return 1; void main(){SEIemType e; Queue Q; int i;InitQueue(&Q);for(i=0;i< 10:i++) EnQueue(&Q/a,+i); while(QueueEmpty(Q)!=O){DeQueue(&Q,&e); cout«e;}cout«endl;}7・用双端队列模拟栈#include<stdio.h>#include<malloc.h>#include<stdlib.h>#define null 0typedef struct QNode{int data;struct QNode *next;struct QNode *prior;)QNode;typedef struct)QNode *frontL*front2;QNode *rearl,*rear2;}LinkDeque;LinkDeque InitQueue(){LinkDeque Q;Q.front 1 =Q.rearl =(QNode *)malloc(sizeof(QNode)); if(!Q.front 1){printf("\n 存储分配失败\n");exit(O);} Q.front2=Q.rear2=(QNode *)malloc⑸zeof(QNode));if(!Q.front2){printf("\n 存储分配失败\n H);exit(O);) Q. front l->next=Q.front2;Q.front2->next=Q.frontl;return Q;}int EnDeque(LinkDeque &Q,int e){QNode *p;p=(QNode *)malloc(sizeof(QNode)); if(!p){printf("\n 存储分配失败\n");exit(O);} p->data=e;p->next=Q.front2;p->prior=Q.rearl;Q.rearl->next=p;Q.reail 二p;Q.rear2=Q.front 1 ->next;return 1;}int DeDeque(LinkDeque &Q){int e;QNode *p;if(Q.front 1 ==Q.rear 1){printf("栈为空,不能执行删除操作\n");return 0;)p=Q.rearl;e=p->data;p->prior->next=p->next;p->next->prior=p->prior;Q.rearl=p->prior;if(Q.front l==Q.front2){Q.rear 1=Q.front l;Q.rear2=Q.front2;} free(p);return e;}int DequeLength(LinkDeque Q){int len=0;QNode *p;p=Q.frontl->next;while(p!=Q.front2){ Ien++;p=p->next;)return len;}int Gethead(LinkDeque Q){QNode *p;if(Q.front 1 !=Q.rear 1){p=Q.rear 1 ;return p->data;}}void main(){int i=0,e;LinkDeque Q;QNode *p;Q=InitQueue();printf(n\n 1.元素进栈\n 2.元素出栈\n 3.求栈的长度\n 4. 取栈顶元素\n 5.退出\n");for(:i!=5;){printf(-\n请选择你要进行的操作：”)；scanf(n%d\&i);switch(i){case l:printf("\n请输入进栈元素：”)；scanf(”％cT，&e);EnDeque(Q,e);if(Q.front 1 !=Q.rearl){printf("\n 当前栈元素:");p=Q.front 1 ->next;while(p!=Q.front2){ printf(H%d '\p->data);p=p->next;}}else printf(n当前栈为空\iT);break;case 2:if(Q.frontl!=Q.rearl)printf(H\n 已删除%d\n*\DeDeque(Q));eIse printfC*栈为空，不能此删除操作\n“)；if(Q.frontl !=Q.rearl)(printf("\n 当前栈元素:");p=Q.frontl・>next;while(p!=Q.front2){ printf(H%d H,p->data);p=p->next;}}else printfC当前栈为空E)；break;case 3:printf(M\n 栈的长度：%d,\DequeLength(Q));break;case 4:if(Q.front 1 !=Q.rearl)printf(H\n 栈顶元素:%d\n”,Gethead(Q));else printfC栈为空，不能此删除操作\n H);break;default:printf("\n 结束程序\n");}1}&约瑟夫队列：#include<stdio.h>#include<malloc.h>#include<iostream.h>#define len sizeof(struct QNode)struct QNode{int data;QNode *next;};void main(){int m,n,k,i,e,num=l;cout«"请输入总人数:"«endl; cin»n;cout«"请输入出局数:"«endl; cin»m;coutvv"请输入开始报数人的编号:"«endl; cin»k;QNodeQ=(QNode *)malloc(len);Q->next=Q;Q->data= 1; p二Q;for(i=2;i<=n;i++){p->next=(QNode *)malloc(len);p=p->next;p->data=i;)p->next=Q;r=Q;t=r;for(i= 1 ;i<=k-1 ;i++){ t=r;r=r->next;}cout«"出队顺序为:"vvendl;do{for(i= 1 ;i<=m-1 ；i++){ t=r;r=r->next;)e=r->data;t->next=r->next;r=t->next;cout«e«H H; num++;}while(num<=n);cout«endl;)【小结讨论】1.一个程序中如果要用到两个栈时，可通过两个栈共享一维数组来实现，即双向栈共享邻接空间。

实验报告课程名称_______数据结构实验__________________ 实验项目___ 栈和队列的基本操作与应用____ 实验仪器_____________________________________系别 ___ 计算机学院_______________ 专业 __________________班级/学号______ _________学生姓名_____________________ __实验日期__________________成绩_______________________指导教师____ __________________一、实验内容：本次实验主要内容是表达式求值，主要通过栈和队列来编写程序，需要实现整数运算其中需要实现的功能有加减乘除以及括号的运用，其中包含优先级的判断。

二、设计思想1.优先级中加减、乘除、小括号、以及其他可以分组讨论优先级2.优先级关系用“>”“<”“=”来表示三种关系3.为实现运算符优先使用两个栈：OPTR 运算符栈与OPND操作符栈4.运用入栈出栈优先级比较等方式完成运算三、主要算法框架1.建立两个栈InitStack(&OPTR);InitStack(&OPND);2.Push“#”到 OPTR3.判断优先级做入栈出栈操作If“<” Push(&OPTR, c);If“=” Pop(&OPTR, &x)If“>” Pop(&OPTR, &theta);Pop(&OPND, &b);Pop(&OPND, &a);Push(&OPND, Operate(a, theta, b));四、调试报告遇到的问题与解决1.C语言不支持取地址符，用*S代替&S来编写代码2.一开始没有计算多位数的功能只能计算一位数，在几个中间不含运算符的数字中间做p = p*10+c运算。

栈和队列的基本操作栈和队列是计算机科学中常用的数据结构，它们分别具有不同的特点和适用场景。

本文将从栈和队列的基本操作入手，介绍它们的定义、特点以及常见应用。

一、栈的基本操作栈是一种遵循“先进后出”（Last In First Out，LIFO）原则的数据结构，类似于我们日常生活中的堆叠物体。

栈的基本操作包括入栈（Push）、出栈（Pop）、判空（Empty）和读取栈顶元素（Top）。

1. 入栈（Push）：将元素插入到栈的顶部，使其成为新的栈顶元素。

该操作在栈中插入元素时发生，栈的大小会增加。

2. 出栈（Pop）：删除栈顶元素，并返回其值。

该操作在栈中删除元素时发生，栈的大小会减少。

3. 判空（Empty）：检查栈是否为空，即栈中是否存在元素。

如果栈为空，则返回True；否则返回False。

4. 读取栈顶元素（Top）：获取栈顶元素的值，但不删除该元素。

该操作可以帮助我们查看栈顶的元素值，但不会影响栈的大小。

栈的特点是插入和删除操作只能在栈顶进行，这种特性使得栈在很多应用中具有重要的作用。

二、栈的应用场景1. 函数调用：在程序中，函数调用时使用栈来存储临时变量、返回地址等信息。

当函数调用结束后，栈会自动弹出函数的帧，返回到上一层函数。

2. 表达式求值：利用栈可以方便地实现中缀表达式到后缀表达式的转换，以及后缀表达式的求值过程。

栈可以保存操作数和运算符，按照一定的规则进行计算。

3. 括号匹配：栈可以用于验证括号是否匹配。

当遇到左括号时，将其入栈；当遇到右括号时，将栈顶元素出栈并进行匹配。

如果最后栈为空，则说明括号匹配成功。

4. 浏览器的前进后退功能：浏览器的前进后退功能可以通过两个栈来实现。

一个栈用于保存浏览历史记录，另一个栈用于保存前进的页面。

通过入栈和出栈操作，可以实现页面的跳转。

三、队列的基本操作队列是一种遵循“先进先出”（First In First Out，FIFO）原则的数据结构，类似于我们日常生活中排队等候的场景。

数据结构栈和队列实验报告数据结构栈和队列实验报告1.实验目的本实验旨在通过设计栈和队列的数据结构，加深对栈和队列的理解，并通过实际操作进一步掌握它们的基本操作及应用。

2.实验内容2.1 栈的实现在本实验中，我们将使用数组和链表两种方式实现栈。

我们将分别实现栈的初始化、入栈、出栈、判断栈是否为空以及获取栈顶元素等基本操作。

通过对这些操作的实现，我们可将其用于解决实际问题中。

2.2 队列的实现同样地，我们将使用数组和链表两种方式实现队列。

我们将实现队列的初始化、入队、出队、判断队列是否为空以及获取队头元素等基本操作。

通过对这些操作的实现，我们可进一步了解队列的特性，并掌握队列在实际问题中的应用。

3.实验步骤3.1 栈的实现步骤3.1.1 数组实现栈（详细介绍数组实现栈的具体步骤）3.1.2 链表实现栈（详细介绍链表实现栈的具体步骤）3.2 队列的实现步骤3.2.1 数组实现队列（详细介绍数组实现队列的具体步骤）3.2.2 链表实现队列（详细介绍链表实现队列的具体步骤）4.实验结果与分析4.1 栈实验结果分析（分析使用数组和链表实现栈的优缺点，以及实际应用场景）4.2 队列实验结果分析（分析使用数组和链表实现队列的优缺点，以及实际应用场景）5.实验总结通过本次实验，我们深入了解了栈和队列这两种基本的数据结构，并利用它们解决了一些实际问题。

我们通过对数组和链表两种方式的实现，进一步加深了对栈和队列的理解。

通过实验的操作过程，我们也学会了如何设计和实现基本的数据结构，这对我们在日后的学习和工作中都具有重要意义。

6.附件6.1 源代码（附上栈和队列的实现代码）6.2 实验报告相关数据（附上实验过程中所产生的数据）7.法律名词及注释7.1 栈栈指的是一种存储数据的线性数据结构，具有后进先出(LIFO)的特点。

栈的操作主要包括入栈和出栈。

7.2 队列队列指的是一种存储数据的线性数据结构，具有先进先出(FIFO)的特点。

《数据结构与算法》实验报告专业班级学号实验项目实验二栈和队列的基本操作。

实验目的1、掌握栈的基本操作：初始化栈、判栈为空、出栈、入栈等运算。

2、掌握队列的基本操作：初始化队列、判队列为空、出队列、入队列等运算。

实验容题目1：进制转换。

利用栈的基本操作实现将任意一个十进制整数转化为R进制整数算法提示：1、定义栈的顺序存取结构2、分别定义栈的基本操作（初始化栈、判栈为空、出栈、入栈等）3、定义一个函数用来实现上面问题：十进制整数X和R作为形参初始化栈只要X不为0重复做下列动作将X%R入栈X=X/R只要栈不为空重复做下列动作栈顶出栈输出栈顶元素题目2：利用队列的方式实现辉三角的输出。

算法设计分析（一）数据结构的定义1、栈的应用实现十进制到其他进制的转换，该计算过程是从低位到高位顺序产生R进制数的各个位数，而打印输出一般从高位到低位进行，恰好与计算过程相反。

因此，运用栈先进后出的性质，即可完成进制转换。

栈抽象数据结构描述typedef struct SqStack /*定义顺序栈*/{int *base; /*栈底指针*/int *top; /*栈顶指针*/int stacksize; /*当前已分配存储空间*/} SqStack;2、队列的应用由于是要打印一个数列，并且由于队列先进先出的性质，肯定要利用已经进队的元素在其出队之前完成辉三角的递归性。

即，利用要出队的元素来不断地构造新的进队的元素，即在第N行出队的同时，来构造辉三角的第N+1行，从而实现打印辉三角的目的。

队列抽象数据结构描述typedef struct SeqQueue{int data[MAXSIZE];int front; /*队头指针*/int rear; /*队尾指针*/}SeqQueue;（二）总体设计1、栈（1）主函数：统筹调用各个函数以实现相应功能int main()（2）空栈建立函数：对栈进行初始化。

int StackInit(SqStack *s)（3）判断栈空函数：对栈进行判断，若栈中有元素则返回1，若栈为空，则返回0。

数据结构实验报告一实验名称:线性表及其实现栈和队列及其应用1 实验目的及实验要求1.线性表目的要求：（1）熟悉线性表的基本运算在两种存储结构（顺序结构和链式结构）上的实现，以线性表的各种操作（建立、插入、删除等）的实现为实验重点；（2）通过本次实验帮助学生加深对顺序表、链表的理解，并加以应用；（3）掌握循环链表和双链表的定义和构造方法2.栈和队列目的要求：（1）掌握栈和队列这两种特殊的线性表，熟悉它们的特性，在实际问题背景下灵活运用它们；（2）本实验训练的要点是“栈”的观点及其典型用法；（3）掌握问题求解的状态表示及其递归算法，以及由递归程序到非递归程序的转化方法。

2实验内容及实验步骤（附运行结果截屏）1.线性表实验内容：（1）编程实现线性表两种存储结构（顺序存储、链式存储）中的基本操作的实现（线性表的创建、插入、删除和查找等），并设计一个菜单调用线性表的基本操作。

（2）建立一个按元素递增有序的单链表L，并编写程序实现：a）将x插入其中后仍保持L的有序性；b）将数据值介于min和max之间的结点删除，并保持L的有序性；c）（选做）将单链表L逆置并输出；（3）编程实现将两个按元素递增有序的单链表合并为一个新的按元素递增的单链表。

注：（1）为必做题，（2）~（3）选做。

2.栈和队列实验内容：（1）编程实现栈在两种存储结构中的基本操作（栈的初始化、判栈空、入栈、出栈等）；（2）应用栈的基本操作，实现数制转换（任意进制）；（3）编程实现队列在两种存储结构中的基本操作（队列的初始化、判队列空、入队列、出队列）；（4）利用栈实现任一个表达式中的语法检查（括号的匹配）。

（5）利用栈实现表达式的求值。

注：（1）～（2）必做，（3）～（5）选做。

实验步骤：先编写线性表和栈和队列的类模板，实现各自的基础结构，之后按照要求编写适当的函数方法（公共接口），最后完成封装。

编写主函数直接调用即可。

核心代码：//LinearList.h 顺序表//类的声明1.template<class T>2.class LinearList3.{4.public:5.LinearList(int sz = default_size);6.~LinearList();7.int Length()const; //length of the linear8.int Search(T x)const; //search x in the linear and return its order number9.T GetData(int i)const; //get i th order's data10.bool SetData(int i,T x); //change i th order's data to x11.bool DeleteData(int i);12.bool InsertData(int i,T x);13.void output(bool a,int b,int c); //print the linear14.void ReSize(int new_size);15.16.private:17.T *data;18.int max_size,last_data;19.};//构造函数1.template<class T>2.LinearList<T>::LinearList(int sz)3.{4.if(sz>0)5.{6.max_size = sz;st_data=-1;8.data=new T[max_size];9.if(data == NULL)10.{11.cerr<<"Memory creat error!"<<endl;12.exit(1);13.}14.}15.else16.{17.cerr<<"Size error!"<<endl;18.exit(1);19.}20.}//Qlist.h 链式表//模板类的声明1.template<class T>2.struct LinkNode3.{4.T data;5.LinkNode<T> *link;6.LinkNode(LinkNode<T> *ptr = NULL)7.{8.link = ptr;9.}10.LinkNode(const T item,LinkNode<T> *ptr = NULL)11.{12.data = item;13.link = ptr;14.}15.};16.17.template<class T>18.class Qlist: public LinkNode<T>19.{20.public:21.Qlist();22.Qlist(const T x);23.Qlist(Qlist<T>&L);24.~Qlist();25.void MakeEmpty();26.int Length()const; //length of the linear27.int Search(T x)const; //search x in the linear and return its order number28.LinkNode<T> *Locate(int i);29.T GetData(int i); //get i th order's data30.bool SetData(int i,T x); //change i th order's data to x31.bool DeleteData(int i);32.bool InsertData(int i,T x);33.void output(bool a,int b,int c); //print the linear34.35.protected:36.LinkNode<T> *first;37.};//构造函数1.template<class T>2.Qlist<T>::Qlist(Qlist<T>&L)3.{4.T value;5.LinkNode<T>*src = L.getHead();6.LinkNode<T>*des = first = new LinkNode<T>;7.while(src->link != NULL)8.{9.value = src->link->data;10.des->link = new LinkNode<T>(value);11.des = des->link;12.src = src->link;13.}14.des->link = NULL;15.}截屏：3 实验体会（实验遇到的问题及解决方法）刚开始的时候本想先写线性表的类模板然后分别进行继承写顺序表和链式表甚至是以后的栈和队列。

实验报告——栈和队列的应用第一篇：实验报告——栈和队列的应用实验5 栈和队列的应用目的和要求：（1）熟练栈和队列的基本操作；（2）能够利用栈与队列进行简单的应用。

一、题目题目1.利用顺序栈和队列，实现一个栈和一个队列，并利用其判断一个字符串是否是回文。

所谓回文，是指从前向后顺读和从后向前倒读都一样的字符串。

例如，a+b&b+a等等。

题目2.假设在周末舞会上，男士们和女士们进入舞厅时，各自排成一队。

跳舞开始时，依次从男队和女队的队头上各出一人配成舞伴。

若两队初始人数不相同，则较长的那一队中未配对者等待下一轮舞曲。

现要求写一算法模拟上述舞伴配对问题，并实现。

题目3.打印机提供的网络共享打印功能采用了缓冲池技术，队列就是实现这个缓冲技术的数据结构支持。

每台打印机具有一个队列（缓冲池），用户提交打印请求被写入到队列尾，当打印机空闲时，系统读取队列中第一个请求，打印并删除之。

请利用队列的先进先出特性，完成打印机网络共享的先来先服务功能。

题目4.假设以数组Q[m]存放循环队列中的元素, 同时设置一个标志tag，以tag == 0和tag == 1来区别在队头指针(front)和队尾指针(rear)相等时，队列状态为“空”还是“满”。

试编写与此结构相应的插入(enqueue)和删除(dlqueue)算法。

题目5.利用循环链队列求解约瑟夫环问题。

请大家从本组未讨论过的五道题中选择一道，参照清华邓俊辉老师MOOC视频及课本相关知识，编写相应程序。

选择题目3：打印机提供的网络共享打印功能采用了缓冲池技术，队列就是实现这个缓冲技术的数据结构支持。

二、程序清单//Ch3.cpp #include #include #include“ch3.h” template void LinkedQueue::makeEmpty()//makeEmpty//函数的实现{ LinkNode*p;while(front!=NULL)//逐个删除队列中的结点{p=front;front=front->link;delete p;} };template bool LinkedQueue::put_in(T&x）{//提交命令函数if(front==NULL){//判断是否为空front=rear=new LinkNode;//如果为空，新结点为对头也为对尾front->data=rear->data=x;if(front==NULL)//分配结点失败return false;} else{rear->link=new LinkNode;//如不为空，在链尾加新的结点rear->link->data=x;if(rear->link==NULL)return false;rear=rear->link;} return true;};template bool LinkedQueue::carry_out()//执行命令函数 { if(IsEmpty()==true)//判断是否为空{return false;} cout<data<LinkNode*p=front;front=front->link;//删除以执行的命令，即对头修改delete p;//释放原结点return true;};void main()//主函数 { LinkedQueue q;//定义类对象char flag='Y';//标志是否输入了命令const int max=30;//一次获取输入命令的最大个数while(flag=='Y')//循环{ int i=0;char str[max];//定义存储屏幕输入的命令的数组gets(str);//获取屏幕输入的命令while(str[i]!=''){q.put_in(str[i]);//调用提交命令函数，将每个命令存入队列中i++;}for(int j=0;j<=i;j++){if(q.IsEmpty()==true)//判断是否为空，为空则说明没有可执行的命令{cout<cin>>flag;continue;//为空跳出for循环为下次输入命令做好准备}q.carry_out();//调用执行命令的函数，将命令打印并删除}三、程序调试过程中所出现的错误无。

栈和队列基本操作实验报告实验二堆栈和队列基本操作的编程实现【实验目的】堆栈和队列基本操作的编程实现要求:堆栈和队列基本操作的编程实现(2学时，验证型)，掌握堆栈和队列的建立、进栈、出栈、进队、出队等基本操作的编程实现，存储结构可以在顺序结构或链接结构中任选，也可以全部实现。

也鼓励学生利用基本操作进行一些应用的程序设计。

【实验性质】验证性实验(学时数:2H)【实验内容】内容:把堆栈和队列的顺序存储(环队)和链表存储的数据进队、出队等运算其中一部分进行程序实现。

可以实验一的结果自己实现数据输入、数据显示的函数。

利用基本功能实现各类应用，如括号匹配、回文判断、事物排队模拟、数据逆序生成、多进制转换等。

【实验分析、说明过程】分析:进栈操作先创建一个以x为值的新结点p，其data域值为x则进栈操作步骤如下: 将新结点p的指针域指向原栈顶S(执行语句p->next=S)。

将栈顶S指向新结点p(执行语句S=p)。

注:进栈操作的?与?语句执行顺序不能颠倒，否则原S指针其后的链表将丢失。

出栈操作先将结点栈顶S数据域中的值赋给指针变量*x，则删除操作步骤如下: 结点p 指针域指向原栈顶S(执行语句p=S)。

栈顶S指向其的下一个结点(执行语句S=S->next)释放p结点空间(执行语句free(p))。

队列分析:用链式存储结构实现的队列称为链队列，一个链队列需要一个队头指针和一个队尾指针才能唯一确定。

队列中元素的结构和前面单链表中的结点的结构一样。

为了操作方便，在队头元素前附加一个头结点，队头指针就指向头结点。

【思考问题】1. 栈的顺序存储和链表存储的差异,答:栈的顺序存储有‘后进先出’的特点，最后进栈的元素必须最先出来，进出栈是有序的，在对编某些需要按顺序操作的程序有很大的作用。

链表存储:通过链表的存储可以实现链表中任意位置的插入元素，删除任意元素，可以实现无序进出。

2. 还会有数据移动吗,为什么,答:栈的顺序存储不会有数据移动，移动的只是指向该数据地址的指针。

实验报告（学科：数据结构）姓名__________________单位_______________________班级______________________实验名称：2.1 栈和队列的基本操作【问题描述】编写一个算法，输出指定栈中的栈底元素，并使得原栈中的元素倒置。

【基本要求】（1）正确理解栈的先进后出的操作特点，建立初始栈，通过相关操作显示栈底元素。

（2）程序中要体现出建栈过程和取出栈底元素后恢复栈的入栈过程，按堆栈的操作规则打印结果栈中的元素。

【实验步骤】（1）建立顺序栈SeqStack，存放测试数据；建立队列SeqQueue存放出栈数据；（2）建立InitStack、StackEmpty、StackFull、Pop、Push、GetTop函数用作顺序栈的基本操作；（3）建立InitQueue、QEmpty、Qfull、InQueue、OutQueue、ReadFront函数用作队列的基本操作；（4）建立主函数依次按序对子函数进行操作：InitStack初始化栈→Push压入数据→InitQueue初始化队列→Pop弹出数据→InQueue存入队列→OutQueue出队列→Push压入栈→Pop弹出数据→free清空栈与队列。

在数据的输入与数据的输出时提供必要的提示信息。

（5）使用Visual Studio C++ 2005语言环境进行调试，源代码P202-2-1.cpp通过编译生成目标文件P202-2-1.obj，运行可执行文件：实验2-2-1.exe测试通过。

【源代码】#include "stdio.h"#include "stdlib.h"#define MaxSize 8typedef int ElemType;/*顺序栈的类型定义*/struct SeqStack{ElemType data[MaxSize];int top;};struct SeqStack * s;/*顺序队列的类型定义*/struct SeqQueue{ElemType data[MaxSize];int front,rear;};struct SeqQueue * sq;/*栈的基本运算*//*初始化栈操作*/void InitStack(struct SeqStack * s){s->top=-1;}/*判断栈空操作*/int StackEmpty(struct SeqStack * s){if(s->top==-1){ return(1);}else{return(0);}}/*判断栈满操作*/int StackFull(struct SeqStack * s){if(s->top==MaxSize-1){ return(1);}else{ return(0);}}/*压栈操作*/void Push(struct SeqStack *s,ElemType x) {if(s->top==MaxSize-1){printf("栈满溢出错误!\n");exit(1);}s->top++;s->data[s->top]=x;}/*弹栈操作*/ElemType Pop(struct SeqStack * s){if(StackEmpty(s)){printf("栈下溢错误!!\n");return(1);}s->top--;return s->data[s->top+1];}/*获取栈顶元素操作*/ElemType GetTop(struct SeqStack * s){if(StackEmpty(s)){printf("栈下溢错误!\n");exit(1);}return s->data[s->top];}/*队列的基本运算*//*初始化队列*/void InitQueue(struct SeqQueue * sq){sq->front=0;sq->rear=0;}/*判队空*/int QEmpty(struct SeqQueue * sq){if(sq->front==sq->rear){printf("队列已空，不能进行出队操作!\n");return(1); /*如果链队为空，则返回*/}else{return(0); /*否则返回*/ };}/*判队满*/int Qfull(struct SeqQueue * sq){if(sq->rear==MaxSize){ /*判队列是否已满*/printf("队列已满!\n");return(1); /*入队失败，退出函数运行*/ }return(0);}/*入队列操作*/void InQueue(struct SeqQueue * sq, int x){if(!Qfull(sq)){sq->data[sq->rear]=x; /*数据送给队尾指针所指单元*/sq->rear++; /*将队尾指针加*/ }}/*出队列操作*/ElemType OutQueue(struct SeqQueue *sq){if(sq->rear==sq->front){ /*判断队列是否为空*/printf("队列已空，不能进行出队操作!!\n");return(1); /*出队失败，退出函数运行*/ }sq->front++;return sq->data[sq->front-1];}/*读队头元素*/void ReadFront(struct SeqQueue * sq,int x){if(!QEmpty(sq)){sq->front++; /*将头指针加,前移*/OutQueue(sq); /*出队列操作*/ }}void main(){int n;struct SeqStack *a=(SeqStack *)malloc(sizeof(struct SeqStack));/*分配栈的内存空间，使结构指针a指向栈地址*/struct SeqQueue *sq=(SeqQueue *)malloc(sizeof(struct SeqQueue));InitStack(a);do{printf("输入栈中的数据:");scanf("%d",&n);Push(a,n);/*把数据压入栈中*/}while(!StackFull(a));InitQueue(sq);do{InQueue(sq,Pop(a)); /*弹出栈数据，把数据放进队列中*/}while(!(StackEmpty(a)&&Qfull(sq)));do{Push(a,OutQueue(sq)); /*从队列输出数据，把数据压入到栈内*/}while(!(QEmpty(sq)&&StackFull(a)));do{printf("输出栈中的数据:%d\n",Pop(a)); /*弹出栈中所有数据*/ }while(!StackEmpty(a));free(a);free(sq);}【实验数据】【结论】由于栈的结构特点决定了栈对数据的操作规则。

Sta temp; printf("本程序用于实现链式结构队列的操作,可以进行入队列、 出队列等操作.\n\n"); InitLQ(LQ); while(F) { printf("请输入需要进行操作的序号:\n\n"); printf("1.显示队列所有元素\n"); printf("2.入队列操作\n"); printf("3.出队列操作\n"); printf("4.求队列的长度\n"); printf("5.退出程序\n"); scanf("%d",&ch); switch(ch) { case 1:DisplayLQ(LQ); break; case 2:printf("提示:请输入要人队的一个整数元素:\n"); scanf("%d",&e); EnLQ(LQ,e);//入队 DisplayLQ(LQ); break; case 3:temp=DeLQ(LQ,e); //出队 if(temp==OK) {
三实验设备及软件计算机microsoftvisualc60软件四设计方案算法设计采用的数据结构本程序栈数据的逻辑结构为线性结构存储结构为顺序存储
大 学 《数据结构》课程 实验报告
实 验 名 称：栈和队列基本操作的实现及应用 实验室(中心)： 学 生 信 息： 专 业 班 级： 指 导 教 师 ： 实验完成时间： 2016 年
printf("提示:出队一个元素:%d\n\n",e); DisplayLQ(LQ); } else printf("提示:队列为空!\n\n"); break; case 4:len=LQLength(LQ); printf("提示:队列的长度为:%d\n\n",len); break; default:F=0; printf("提示:程序运行结束，按任意键退出!\n\n"); getch(); } } } Sta InitLQ(LQ &Q)//队列初始化 { Q.front=Q.rear=(QueuePtr) malloc(sizeof(QNode)); Q.front->next=NULL; return OK; } Sta DesLQ(LQ &Q)//销毁一个队列 { QueuePtr p; Type e;

数据结构实验报告实验名称：实验2——栈和队列1 实验目的通过选择下面五个题目之一进行实现，掌握如下内容：进一步掌握指针、模板类、异常处理的使用掌握栈的操作的实现方法掌握队列的操作的实现方法学习使用栈解决实际问题的能力学习使用队列解决实际问题的能力2 实验内容利用栈结构实现八皇后问题。

八皇后问题19世纪著名的数学家高斯于1850年提出的。

他的问题是：在8*8的棋盘上放置8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列、同一斜线上。

请设计算法打印所有可能的摆放方法。

提示：1、可以使用递归或非递归两种方法实现2、实现一个关键算法：判断任意两个皇后是否在同一行、同一列和同一斜线上2. 程序分析主程序：#include<iostream>using namespace std;const int StackSize=8; //皇后的个数int num=0;template <class T>class SeqStack //定义顺序栈模板类{public:SeqStack(){top=-1;} //构造函数，初始化空栈void Push(T x); //入栈操作void Pop();//出栈操作void PlaceQueen(int row); //放置皇后bool Judgement();//判断是否符合条件void Print();//输出符合条件的皇后排列bool Empty(){if(top==-1) return true;else return false;}; //判断栈是否为空private:T data[StackSize]; //定义数组int top; //栈顶指针};template <class T>void SeqStack<T>::Push(T x) //入栈操作{if(top>=StackSize-1) throw"上溢";top++;//栈顶指针上移data[top]=x;}template <class T>void SeqStack<T>::Pop()//出栈操作{if(Empty()) throw"下溢";top--;//栈顶指针下移}template <class T>bool SeqStack<T>::Judgement()//判断该位置是否合适{for(int i=0;i<top;i++)if(data[top]==data[i]||(abs(data[top]-data[i]))==(top-i))//判断是否满足任意两个皇后不在同列同一斜线return false;return true;}template <class T>void SeqStack<T>::PlaceQueen(int row) //放置皇后{for (int i=0;i<StackSize;i++){Push(i); //入栈if (Judgement())//判断位置是否合适{if (row<StackSize-1)PlaceQueen(row+1); //如果合适满足条件则放置一个皇后,递归调用else{num++;//不满足条件则到下一行Print();//输出符合条件的皇后}}Pop();//出栈}}template <class T>void SeqStack<T>::Print()//输出皇后函数{cout<<"NO."<<num<<":"<<endl; for(int i=0;i<StackSize;i++){for(int j=0;j<data[i];j++){cout<<"□";}cout<<"■";for(int j=StackSize-1;j>data[i];j--){cout<<"□";}cout<<endl;}cout<<endl;}void main(){SeqStack<int> Queen;Queen.PlaceQueen(0);cout<<"总共有"<<num<<"种摆放方法。

数据结构栈和队列实验报告一、实验目的本次实验的主要目的是深入理解和掌握数据结构中的栈和队列的基本概念、操作原理以及实际应用。

通过编程实现栈和队列的相关操作，加深对其特性的认识，并能够运用栈和队列解决实际问题。

二、实验环境本次实验使用的编程语言为C+＋，开发工具为Visual Studio 2019。

三、实验原理（一）栈栈（Stack）是一种特殊的线性表，其操作遵循“后进先出”（Last In First Out，LIFO）的原则。

可以将栈想象成一个只有一端开口的容器，元素只能从开口端进出。

入栈操作（Push）将元素添加到栈顶，出栈操作（Pop）则从栈顶移除元素。

（二）队列队列（Queue）也是一种线性表，但其操作遵循“先进先出”（FirstIn First Out，FIFO）的原则。

队列就像是排队买票的队伍，先到的人先接受服务。

入队操作（Enqueue）将元素添加到队列的末尾，出队操作（Dequeue）则从队列的头部移除元素。

四、实验内容（一）栈的实现与操作1、定义一个栈的数据结构，包含栈顶指针、存储元素的数组以及栈的最大容量等成员变量。

2、实现入栈（Push）操作，当栈未满时，将元素添加到栈顶，并更新栈顶指针。

3、实现出栈（Pop）操作，当栈不为空时，取出栈顶元素，并更新栈顶指针。

4、实现获取栈顶元素（Top）操作，返回栈顶元素但不进行出栈操作。

5、实现判断栈是否为空（IsEmpty）和判断栈是否已满（IsFull）的操作。

（二）队列的实现与操作1、定义一个队列的数据结构，包含队头指针、队尾指针、存储元素的数组以及队列的最大容量等成员变量。

2、实现入队（Enqueue）操作，当队列未满时，将元素添加到队尾，并更新队尾指针。

3、实现出队（Dequeue）操作，当队列不为空时，取出队头元素，并更新队头指针。

4、实现获取队头元素（Front）操作，返回队头元素但不进行出队操作。

5、实现判断队列是否为空（IsEmpty）和判断队列是否已满（IsFull）的操作。

数据结构实验报告（二）实验二堆栈和队列一、实验目的和要求：1、掌握堆栈和队列的基本概念；2、掌握堆栈和队列的基本操作。

二、实验原理：1、堆栈的定义：堆栈是一种只允许在表的一端进行插入和删除运算的特殊的线性表。

允许进行插入和删除运算的一端称为栈顶，另一端称为栈底，当链表中没有元素时，称为空栈。

2、堆栈的插入运算称为入栈或者进栈，删除运算称为出栈或者退栈，栈顶的当前位置是动态的，标识栈顶当前位置的指针称为栈顶指针。

每次进栈的数据元素都放在原当前栈顶元素之前成为新的栈顶元素，每次退栈的数据元素都是原当前栈顶元素，最后进入堆栈的数据元素总是最先退出堆栈。

3、堆栈的存储结构：（1）顺序存储结构：栈的顺序存储结构称为顺序栈。

顺序栈的本质是顺序表的简化。

（2）链式存储结构：栈的链式存储结构称为链栈，通常用单链表示。

链栈的插入和删除操作只需处理栈顶的情况。

4、队列的定义：队列是允许在表的一端进行插入，而在表的另一端进行删除的特殊线性表。

允许进行插入的一端称为队尾，允许进行删除的一端称为队头。

队列的插入运算称为进队或者入队，删除运算称为出队或者离队，因此队列又称为先进先出表。

5、队列的存储结构队列的存储结构同线性表一样，可以分为顺序结构和链式结构。

（1）顺序存储结构：用顺序存储结构存储队列称为顺序队列。

顺序队列会出现假溢出问题，解决办法是用首尾相接的书顺序存储结构，称为循环队列。

在队列中，只要涉及队头或者队尾指针的修改都要对其求模。

（2）链式存储结构：用链式存储结构存储的队列称为链队列。

链队列的基本操作的实现基本上也是单链表操作的简化。

通常附设头结点，并设置队头指针指向头结点，队尾指针指向终端结点。

插入数据时只考虑在链队列的尾部进行，删除数据时只考虑在链队列的头部进行。

三、实验内容：1、试编写一个算法，建立一个学生成绩栈，要求从键盘上输入N个整数，按照下列要求分别进入不同的栈。

（1）若输入的整数X小于60，则进入第一个栈；（2）若输入的整数x大于等于60并小于100，则进入第二个栈；（3）若输入的整数x大于100，则进入第三个栈；（4）分别输出每个栈的内容。

实验二栈与队列的基本操作与实现一、实验目的：利用高级程序设计语言来实现抽象数据类型栈与队列，进一步熟悉其表示和实现方法，用已经实现的操作来组合新的操作，为以后的利用栈和队列分析和解决问题打下基础。

1、掌握栈和队列的顺序存储结构和链式存储结构，以便在实际中灵活应用。

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

3、掌握栈和队列的基本运算，如：入栈与出栈，入队与出队等运算在顺序存储结构和链式存储结构上的实现。

二、实验要求：1、定义栈的抽象数据类型，并用顺序栈或链栈实现其基本操作：初始化，判断栈空、栈满，出栈、入栈，取栈顶元素等2、定义队列的抽象数据类型，构造循环队列实现其基本操作：初始化，判断队空、队满，出队、入队等3、编写和调试完成程序4、保存和打印程序的运行结果三、测试数据字符的序列为ABCDEFG执行进出栈的次序为：XXYXXYYXXXY（其中X表示进栈，Y表示出栈）栈中的元素为：AEF执行进出队的次序为：XXYXXYYXXXY（其中X表示进队，Y表示出队）栈中的元素为：EFG四、实现提示：1、栈与队列可以用数组进行存储，并定义为全局变量，以减少函数调用时参数的传递。

（即在函数体外面定义变量，全局变量可以为本文件中其他函数所共用，其有效范围为从定义变量的位置开始到本源文件结束）栈：#define MAXN 26char stack[MAXN];int top=0;队列：#define MAXN 26char q[MAXN];int head = 0, tail = 0;2、主控函数示例：void main(){int n,x1,x2,select;char x,y;printf("input a stack length(1<=n<=26)):\n");scanf("%d",&n);printf("select 1:Display()\n");//显示栈中的元素printf("select 2:Push()\n");//进栈printf("select 3:Pop()\n");//出栈printf("select 4:StackTop()\n");//取出栈顶的元素，但并不出栈printf("select 0:exit\n");//退出printf("input a your select(0-4):\n");scanf("%d",&select);while(select!=0){switch(select){ case 1: Display();break;case 2: printf("input a push a value:\n");scanf("%c",&x);scanf("%c",&y);Push(x);break;case 3: x1=Pop();printf("x1->%d\n",x1);break;case 4: x2=StackTop();printf("x2->%d",x2);break;}printf("select 1:Display()\n");printf("select 2:Push()\n");printf("select 3:Pop()\n");printf("select 4:StackTop()\n");printf("select 0:exit");printf("input a your select(0-4):\n");scanf("%d",&select);}}3、队列基本操作的实现与栈类似，可以分开写，也可以写在一个主函数中。

栈和队列的应用实验报告
《栈和队列的应用实验报告》
一、实验目的
本实验旨在通过实际操作，掌握栈和队列的基本概念、操作及应用，加深对数
据结构的理解和应用能力。

二、实验内容
1. 栈的基本操作：包括入栈、出栈、获取栈顶元素等。

2. 队列的基本操作：包括入队、出队、获取队首元素等。

3. 栈和队列的应用：通过实际案例，探讨栈和队列在实际生活中的应用场景。

三、实验步骤
1. 学习栈和队列的基本概念和操作。

2. 编写栈和队列的基本操作代码，并进行调试验证。

3. 分析并实现栈和队列在实际应用中的案例，如表达式求值、迷宫问题等。

4. 进行实际应用案例的测试和验证。

四、实验结果
1. 成功实现了栈和队列的基本操作，并通过实际案例验证了其正确性和可靠性。

2. 通过栈和队列在实际应用中的案例，加深了对数据结构的理解和应用能力。

五、实验总结
通过本次实验，我深刻理解了栈和队列的基本概念和操作，并掌握了它们在实
际应用中的重要性和作用。

栈和队列作为数据结构中的重要内容，对于解决实
际问题具有重要意义，希望通过不断的实践和学习，能够更加熟练地运用栈和
队列解决实际问题，提高自己的编程能力和应用能力。

六、感想与展望
本次实验让我对栈和队列有了更深入的了解，也让我对数据结构有了更加深刻的认识。

我将继续学习和探索更多的数据结构知识，提高自己的编程能力和解决问题的能力，为将来的学习和工作打下坚实的基础。

同时，我也希望能够将所学知识应用到实际工程中，为社会做出更大的贡献。

实验2 栈和队列的基本操作和应用1实验目的(1)熟练掌握顺序栈的基本操作。

(2)掌握顺序栈的应用。

(3)掌握顺序循环队列的基本操作。

(4)掌握链式队列的基本操作。

2实验内容(1)设计一个顺序栈的基本操作的演示程序；(2)利用顺序栈，进行整数的不同进制之间的转换；(3)设计一个顺序循环队列的基本操作演示程序；(4)设计一个链式队列的基本操作演示程序。

【基本要求】I.实验内容(1)的基本要求：编写一个程序，将一个顺序栈的元素依次取出，并打印其元素值。

II.实验内容(2)的基本要求：编写一个程序，将一个非负的十进制整数转换成二进制。

III.实验内容(3)的基本要求：编写一个程序，将一个顺序队列的元素依次取出，并打印其元素值。

IV.实验内容(4)的基本要求：编写一个程序，将一个链式队列的元素依次取出，并打印其元素值。

【测试数据】自定3实验结果按照学校实验格式要求撰写实验报告，内容主要包括1）实验目的；2）实验内容；3）实验环境和方法；4）实验过程描述；5）实验心得体会参考程序如下：实验内容（1）参考程序/*sqStack.h文件*/#define INIT_SIZE 100#define INCREMENT 10typedef int ElemType;//typedef char ElemType;typedef struct SqStack {ElemType *base;ElemType *top;int stacksize;}SqStack;enum Status{OK,ERROR,OVERFLOW};/*sqStackOp.h文件*/#include "sqStack.h"Status InitStack(SqStack &S) ;Status GetTop(SqStack S,ElemType &e);Status Push(SqStack &S,ElemType e);Status Pop(SqStack &S,ElemType &e);bool StackEmpty(SqStack &S);/*sqStackOp.cpp文件*/#include <malloc.h>#include <stdlib.h>#include "sqStackOp.h"Status InitStack(SqStack &S) {//构造一个空的栈S.base=(ElemType*)malloc(INIT_SIZE*sizeof(ElemType));if(! S.base) exit(OVERFLOW); //存储分配失败S.top=S.base;S.stacksize=INIT_SIZE;return OK;} //InitStackStatus GetTop(SqStack S,ElemType &e){//若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR if(S.top==S.base) return ERROR;e=*(S.top-1);return OK;} //GetTopStatus Push(SqStack &S,ElemType e){//插入元素e为新的栈顶元素if(S.top-S.base>=S.stacksize){ //栈满，追加存储空间S.base=(ElemType *)realloc(S.base,(S.stacksize+INCREMENT)*sizeof(ElemType));if(!S.base)exit(OVERFLOW); //存储分配失败S.top=S.base+S.stacksize;S.stacksize+=INCREMENT;}*S.top++=e;return OK;} //PushStatus Pop(SqStack &S,ElemType &e){//若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERRORif(S.top==S.base) return ERROR;e=*(--S.top);return OK;} //Push//判断栈是否为空bool StackEmpty(SqStack &S){if(S.top == S.base)return true;elsereturn false;}/*main.cpp文件*/#include <stdio.h>#include <stdlib.h>#include "sqStackOp.h"void main(){printf("Hellow stack \n");SqStack S; //定义顺序栈Sif(OK != InitStack(S)) {printf("顺序栈初始化出错，退出....\n");exit(-1);}Push(S, 1);Push(S,2);Push(S,3);int e;Pop(S, e);printf("出栈元素= %d \n",e);Push(S,4);Push(S,5);while(!StackEmpty(S)){Pop(S, e);printf("出栈元素= %d \n",e);}/*SqStack S; char x,y;InitStack(S); x='c';y='k';Push(S,x); Push(S,'a'); Push(S,y);Pop(S,x); Push(S,'t'); Push(S,x);Pop(S,x); Push(S,'s');while(!StackEmpty(S)){ Pop(S,y);printf("%c ",y); };printf("%c ",x);*/getchar();}实验内容（2）参考程序/*sqStack.h文件*/#define INIT_SIZE 100#define INCREMENT 10typedef int ElemType;typedef struct SqStack {ElemType *base;ElemType *top;int stacksize;}SqStack;enum Status{OK,ERROR,OVERFLOW};/*sqStackOp.h文件*/#include "sqStack.h"Status InitStack(SqStack &S) ;Status GetTop(SqStack S,ElemType &e);Status Push(SqStack &S,ElemType e);Status Pop(SqStack &S,ElemType &e);bool StackEmpty(SqStack &S);/*sqStackOp.cpp文件*/#include <malloc.h>#include <stdlib.h>#include "sqStackOp.h"Status InitStack(SqStack &S) {//构造一个空的栈S.base=(ElemType*)malloc(INIT_SIZE*sizeof(ElemType));if(! S.base) exit(OVERFLOW); //存储分配失败S.top=S.base;S.stacksize=INIT_SIZE;return OK;} //InitStackStatus GetTop(SqStack S,ElemType &e){//若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERRORif(S.top==S.base) return ERROR;e=*(S.top-1);return OK;} //GetTopStatus Push(SqStack &S,ElemType e){//插入元素e为新的栈顶元素if(S.top-S.base>=S.stacksize){ //栈满，追加存储空间S.base=(ElemType *)realloc(S.base,(S.stacksize+INCREMENT)*sizeof(ElemType));if(!S.base)exit(OVERFLOW); //存储分配失败S.top=S.base+S.stacksize;S.stacksize+=INCREMENT;}*S.top++=e;return OK;} //PushStatus Pop(SqStack &S,ElemType &e){//若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERRORif(S.top==S.base) return ERROR;e=*(--S.top);return OK;} //Push//判断栈是否为空bool StackEmpty(SqStack &S){if(S.top == S.base)return true;elsereturn false;}/*main.cpp文件*/#include <stdio.h>#include <stdlib.h>#include "sqStackOp.h"void main(){SqStack s;int x;InitStack(s);scanf("%d",&x); //%d--十进制输入；%O--八进制输入；%x--十六进制输入//修改这里输入进制和下面整除和余数计算，就可以获得其他进制的转换while(x!=0){Push(s,x%8);x=x/8;}while(!StackEmpty(s)){Pop(s,x);printf("%d ",x);}printf("\n");getchar();}实验内容（3）参考程序/*sqQueue.h 文件*/#define MAXQSIZE 100typedef int QElemType;typedef struct SqQueue {QElemType *base;int front;int rear;}SqQueue;enum Status{OK,ERROR,OVERFLOW};/*sqQueueOp.h 文件*/#include "sqQueue.h"Status InitQueue (SqQueue &Q) ;Status EnQueue (SqQueue &Q, QElemType e);Status DeQueue (SqQueue &Q, QElemType &e) ;bool QueueEmpty(SqQueue &Q);int QueueLength(SqQueue Q);/*sqQueueOp.cpp 文件*/#include <malloc.h>#include <stdlib.h>#include "sqQueueOp.h"Status InitQueue (SqQueue &Q) {// 构造一个空队列QQ.base = (QElemType *) malloc(MAXQSIZE *sizeof (QElemType));if (!Q.base) exit (OVERFLOW);// 存储分配失败Q.front = Q.rear = 0;return OK;}Status EnQueue (SqQueue &Q, QElemType e) { // 插入元素e为Q的新的队尾元素if ((Q.rear+1) % MAXQSIZE == Q.front)return ERROR; //队列满Q.base[Q.rear] = e;Q.rear = (Q.rear+1) % MAXQSIZE;return OK;}Status DeQueue (SqQueue &Q, QElemType &e) { // 若队列不空，则删除Q的队头元素，// 用e返回其值，并返回OK; 否则返回ERRORif (Q.front == Q.rear) return ERROR;e = Q.base[Q.front];Q.front = (Q.front+1) % MAXQSIZE;return OK;}//判断队列是否为空bool QueueEmpty(SqQueue &Q){if(Q.front== Q.rear)return true;elsereturn false;}//计算循环队列长度int QueueLength(SqQueue Q){return (Q.rear - Q.front + MAXQSIZE) % MAXQSIZE;}/*main.cpp 文件*/#include <stdio.h>#include <stdlib.h>#include "sqQueueOp.h"void main(){printf("Hello Queue \n");SqQueue Q; //定义顺序队列QQElemType e;if(OK != InitQueue(Q)) {printf("顺序队列初始化出错，退出....\n");exit(-1);}EnQueue(Q,1);EnQueue(Q,3);EnQueue(Q,5);EnQueue(Q,7);printf("当前队列长度= %d \n",QueueLength(Q));DeQueue(Q,e);printf("队首元素%d出队，当前队列长度=%d\n",e,QueueLength(Q));EnQueue(Q,9);EnQueue(Q,11);while(!QueueEmpty(Q)){DeQueue(Q,e);printf("队首元素%d出队，当前队列长度=%d\n",e,QueueLength(Q));}getchar();}实验内容（4）参考程序/*linkQueue.h 文件*/typedef int QElemType;typedef struct QNode {// 结点类型QElemType data;struct QNode *next;} QNode, *QueuePtr;typedef struct { // 链队列类型QueuePtr front; // 队头指针QueuePtr rear; // 队尾指针} LinkQueue;enum Status{OK,ERROR,OVERFLOW};/*linkQueueOp.h 文件*/#include "linkQueue.h"Status InitQueue (LinkQueue &Q) ;Status EnQueue (LinkQueue &Q, QElemType e); Status DeQueue (LinkQueue &Q, QElemType &e) ; bool QueueEmpty(LinkQueue &Q);/*linkQueueOp.cpp 文件*/#include <malloc.h>#include <stdlib.h>#include "linkQueueOp.h"Status InitQueue (LinkQueue &Q) {// 构造一个空队列QQ.front = Q.rear = (QueuePtr)malloc(sizeof(QNode));if (!Q.front) exit (OVERFLOW);//存储分配失败Q.front->next = NULL;return OK;}Status EnQueue (LinkQueue &Q, QElemType e) { // 插入元素e为Q的新的队尾元素QueuePtr p = (QueuePtr) malloc (sizeof (QNode));if (!p) exit (OVERFLOW); //存储分配失败p->data = e;p->next = NULL;Q.rear->next = p;Q.rear = p;return OK;}Status DeQueue (LinkQueue &Q, QElemType &e) { // 若队列不空，则删除Q的队头元素，//用e 返回其值，并返回OK；否则返回ERROR if (Q.front == Q.rear) return ERROR;QueuePtr p = Q.front->next;e = p->data;Q.front->next = p->next;if (Q.rear == p) Q.rear = Q.front;free (p);return OK;}//判断队列是否为空bool QueueEmpty(LinkQueue &Q){if(Q.front == Q.rear)return true;elsereturn false;}/*main.cpp 文件*/#include <stdio.h>#include <stdlib.h>#include "linkQueueOp.h"void main(){printf("Hello LinkQueue \n");LinkQueue Q; //定义顺序队列QQElemType e;if(OK != InitQueue(Q)) {printf("顺序队列初始化出错，退出....\n");exit(-1);}EnQueue(Q,1);EnQueue(Q,3);EnQueue(Q,5);EnQueue(Q,7);DeQueue(Q,e);printf("队首元素%d出队，\n",e);EnQueue(Q,9);EnQueue(Q,11);while(!QueueEmpty(Q)){DeQueue(Q,e);printf("队首元素%d出队，\n",e);}getchar();}。

实验二：栈与队列的应用学时：4学时实验目的：掌握栈与队列的基本结构和操作方法，并能利用其解决实际问题。

实验内容： (任选一题，有能力的同学可以两题都做)一、输入一个表达式(4+2*4#),利用栈求表达式的值。

（只对整数求值，目前只考虑操作数为个位数的情况，即24+34*34这种情况不考虑）提示：1，先实现栈的基本操作：初始化，入栈，出栈等。

2，首先将一个中缀式变成后缀式，然后，对后缀式求值。

3，可用顺序栈或者链栈实现。

二、编写一个程序，反映病人到医院看病排队看医生的情况，在病人排队过程中，主要重复两件事：（1）病人到达诊室，将病历交给护士，排到等待队列中侯诊（2）护士从等待队列中取出下一位病人的病历，改病人进入诊室就诊要求：模拟病人等待就诊这一过程，程序采用菜单式，其选项和功能说明如下：（1）排队——输入排队病人的病历号，加入到病人排队队列中（2）就诊——病人排队队列中最前面的病人就诊，将其从队列中删除（3）查看排队——从队首到队尾理出所有的排队病人的病历号（4）不在排队，余下依次就诊——从队首到队尾列出所有的排队病人的病历号，并退出运行（5）下班——退出运行（6）上班——初始化排队队列。

提示：1，先实现队列的基本操作：初始化，入队，出队等。

2，在main（）程序中，模拟病人看病这个过程。

给出菜单选择，进行相应的操作3，可用顺序队列或者链队列实现。

可参考如下代码：顺序栈的实现ch32_sstack.c#include "stdio.h"#define StackSize 100typedef int ElemType;typedef struct {ElemType elem[StackSize];int top;}SqStack;InitStack(SqStack *pS){pS->top=0; /* top指向栈顶的上一个元素*/}int Push(SqStack *pS,ElemType e){if (pS->top==StackSize-1) /* 栈满*/return 0;pS->elem[pS->top]=e;pS->top=pS->top+1;return 1;}int Pop(SqStack *pS,ElemType* pe){if (pS->top==0) /* 栈空*/return 0;pS->top = pS->top - 1;*pe = pS->elem[pS->top];return 1;}main(){SqStack S;ElemType e;int N;InitStack(&S);N=1348;while(N){e = N % 8;Push(&S,e);N = N/8;}while(Pop(&S,&e)){printf("%d",e);}getch();}链栈的实现ch3_lstack.c #include "stdio.h"/* 数据元素的类型*/typedef int ElemType;/* 节点的类型（包括头节点）*/typedef struct Node{ElemType elem;struct Node *next;}SNode;/* 初始化，头节点*/InitStack(SNode* pS){pS->next=NULL;}/* 入栈：在头节点之后插入一个新节点*/Push(SNode* pS,ElemType e){SNode* node;node = (SNode*)malloc(sizeof(SNode));node->elem = e;node->next = pS->next;pS->next = node;}int Pop(SNode* pS,ElemType* pe){SNode* node;if (pS->next==NULL){return 0;}*pe = pS->next->elem;node=pS->next;pS->next=node->next;free(node);return 1;}main(){SNode S; ElemType e;int N;InitStack(&S);N=1348;while(N){e = N % 8;Push(&S,e);N = N/8;}while(Pop(&S,&e)){printf("%d",e);}getch();}队列的顺序实现（循环队列）ch3_squeue.c/*队列的顺序实现（循环队列）author: Shirleydate: 2011.3*/#define MaxSize 100typedef int ElemType;typedef struct {ElemType elem[MaxSize];int front,rear;}SqQueue;InitQueue(SqQueue* pQ){pQ->front=pQ->rear=0;}int EnQueue(SqQueue* pQ,ElemType e){if ((pQ->rear+1)%MaxSize == pQ->front) /* 队满*/ return 0;pQ->elem[pQ->rear] = e;pQ->rear = (pQ->rear+1)%MaxSize;return 1;}int DeQueue(SqQueue* pQ,ElemType* pe){if (pQ->rear == pQ->front) /* 队空*/return 0;*pe = pQ->elem[pQ->front];pQ->front = (pQ->front+1)%MaxSize;return 1;}main(){SqQueue Q;ElemType e;InitQueue(&Q);e=2;EnQueue(&Q,e);e=5;EnQueue(&Q,e);e=3;EnQueue(&Q,e);while(DeQueue(&Q,&e)){printf("\n%d",e);}getch();}队列的链式实现ch3_lqueue.c /*队列的链式实现author: Shirleydate: 2011.3*/#include "stdio.h"#define MaxSize 100typedef int ElemType;typedef struct QNode{ElemType elem;struct QNode * next;}QNode;typedef struct {QNode* front;QNode* rear;}LinkQueue;InitQueue(LinkQueue* pQ){QNode* node;node=(QNode*)malloc(sizeof(QNode)); /*分配一个头节点*/ node->next = NULL;pQ->front=pQ->rear=node;}int EnQueue(LinkQueue* pQ,ElemType e){QNode* node;node=(QNode*)malloc(sizeof(QNode));node->elem = e;node->next = NULL;pQ->rear->next = node;pQ->rear = node;return 1;}int DeQueue(LinkQueue* pQ,ElemType* pe){QNode* node;if (pQ->rear == pQ->front) /* 队空*/return 0;node = pQ->front->next;*pe = node->elem;pQ->front->next = node->next;/* 注意有个头节点，当最后一个元素出队时，记得更新尾指针*/ if (pQ->rear==node)pQ->rear=pQ->front;free(node);return 1;}DestoryQueue(LinkQueue* pQ){while(pQ->front){pQ->rear=pQ->front->next;free(pQ->front);pQ->front = pQ->rear;}}main(){LinkQueue Q;ElemType e;InitQueue(&Q);e=2;EnQueue(&Q,e);e=5;EnQueue(&Q,e);e=3;EnQueue(&Q,e);while(DeQueue(&Q,&e)){printf("\n%d",e);}DestoryQueue(&Q);getch();}。