下载文档原格式
实验日期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.1 栈的定义和特点栈是一种具有特殊操作约束的线性数据结构，它的特点是“先进后出”（Last-In-First-Out，LIFO）。
栈的操作包括入栈（push）和出栈（pop），入栈操作将元素放入栈顶，出栈操作将栈顶元素移除。
1.2 实验步骤在本次实验中，我们使用编程语言实现了一个栈的数据结构，并进行了以下实验步骤：1.2.1 创建一个空栈1.2.2 向栈中依次压入若干元素1.2.3 查看栈顶元素1.2.4 弹出栈顶元素1.2.5 再次查看栈顶元素1.3 实验结果通过实验，我们观察到栈的特点：最后入栈的元素最先出栈。
在实验步骤1.2.2中，我们依次压入了元素A、B和C，栈顶元素为C。
在实验步骤1.2.4中，我们弹出了栈顶元素C，此时栈顶元素变为B。
二、队列的实验2.1 队列的定义和特点队列是一种具有特殊操作约束的线性数据结构，它的特点是“先进先出”（First-In-First-Out，FIFO）。
队列的操作包括入队（enqueue）和出队（dequeue），入队操作将元素放入队尾，出队操作将队头元素移除。
2.2 实验步骤在本次实验中，我们使用编程语言实现了一个队列的数据结构，并进行了以下实验步骤：2.2.1 创建一个空队列2.2.2 向队列中依次插入若干元素2.2.3 查看队头元素2.2.4 删除队头元素2.2.5 再次查看队头元素2.3 实验结果通过实验，我们观察到队列的特点：最先入队的元素最先出队。
在实验步骤2.2.2中，我们依次插入了元素X、Y和Z，队头元素为X。
在实验步骤2.2.4中，我们删除了队头元素X，此时队头元素变为Y。
三、栈和队列的应用栈和队列在实际应用中有广泛的应用场景，下面简要介绍一些常见的应用：3.1 栈的应用3.1.1 表达式求值：通过栈可以实现对表达式的求值，如中缀表达式转换为后缀表达式，并计算结果。
数据结构栈和队列实验报告实验报告：数据结构栈和队列一、实验目的1.了解栈和队列的基本概念和特点；2.掌握栈和队列的基本操作；3.掌握使用栈和队列解决实际问题的方法。
二、实验内容1.栈的基本操作实现；2.队列的基本操作实现；3.使用栈和队列解决实际问题。
三、实验原理1.栈的定义和特点：栈是一种具有后进先出(LIFO)特性的线性数据结构，不同于线性表，栈只能在表尾进行插入和删除操作，称为入栈和出栈操作。
2.队列的定义和特点：队列是一种具有先进先出(FIFO)特性的线性数据结构，不同于线性表，队列在表头删除元素，在表尾插入元素，称为出队和入队操作。
3.栈的基本操作：a.初始化：建立一个空栈；b.入栈：将元素插入栈的表尾；c.出栈：删除栈表尾的元素，并返回该元素；d.取栈顶元素：返回栈表尾的元素，不删除。
4.队列的基本操作：a.初始化：建立一个空队列；b.入队：将元素插入队列的表尾；c.出队：删除队列表头的元素，并返回该元素；d.取队头元素：返回队列表头的元素，不删除。
四、实验步骤1.栈的实现：a.使用数组定义栈，设置栈的大小和栈顶指针；b.实现栈的初始化、入栈、出栈和取栈顶元素等操作。
2.队列的实现：a.使用数组定义队列，设置队列的大小、队头和队尾指针；b.实现队列的初始化、入队、出队和取队头元素等操作。
3.使用栈解决实际问题：a.以括号匹配问题为例，判断一个表达式中的括号是否匹配；b.使用栈来实现括号匹配，遍历表达式中的每个字符，遇到左括号入栈，遇到右括号时将栈顶元素出栈，并判断左右括号是否匹配。
4.使用队列解决实际问题：a.以模拟银行排队问题为例，实现一个简单的银行排队系统；b.使用队列来模拟银行排队过程，顾客到达银行时入队，处理完业务后出队，每个顾客的业务处理时间可以随机确定。
五、实验结果与分析1.栈和队列的基本操作实现：a.栈和队列的初始化、入栈/队、出栈/队以及取栈顶/队头元素等操作均能正常运行；b.栈和队列的时间复杂度均为O(1)，操作效率很高。
《数据结构》第五次实验报告学生姓名学生班级学生学号指导老师雷大江重庆邮电大学计算机学院一、实验内容1) 利用栈深度优先进行迷宫求解。
用数组表示迷宫建立栈，利用栈实现深度优先搜索2) 利用队列宽度优先进行迷宫求解。
用数组表示迷宫建立队列，利用队列实现宽度优先搜索二、需求分析利用栈的结构，走过的路入栈，如果不能走出栈，采用遍历法，因此栈内存储的数据就是寻一条路径。
当到达了某点而无路可走时需返回前一点，再从前一点开始向下一个方向继续试探。
因此，压入栈中的不仅是顺序到达的各点的坐标，而且还要有从前一点到达本点的方向，即每走一步栈中记下的内容为(行，列，来的方向)。
三、详细设计（1）基本代码struct item{int x ; //行int y ; //列} ;item move[4] ;（2）代码栈构造函数：void seqstack::Push(int x,int y,int d) //入栈{if(top>=StackSize-1)throw"上溢";top++;data[top].d=d;data[top].x=x;data[top].y=y;}寻找路径：int seqstack::findpath(int a,int b){item move[4]={{0,1},{1,0},{0,-1},{-1,0}};//定义移动结构int x, y, d, i, j ;Push(a,b,-1); //起点坐标入栈while(top!=-1){d=data[top].d+1;x=data[top].x;y=data[top].y;Pop(); //出栈while (d<4) //方向是否可以移动{i=x+move[d].x ; j=y+move[d].y ; //移动后坐标if(Map[i][j]==0) //是否能移动 {Push(x,y,d); //移动前坐标入栈x=i;y=j;Map[x][y]= -1 ;if(x==m&&y==n) //判断是否为终点坐标 {Push(x,y,-1);return 1 ;}else d=0 ;}else d++ ;}}return 0;}（3）伪代码a)栈初始化;b)将入口点坐标及到达该点的方向（设为-1）入栈c)while (栈不空){栈顶元素＝（x , y , d）出栈 ;求出下一个要试探的方向d++ ;while （还有剩余试探方向时）{ if （d方向可走）则 { （x , y , d）入栈 ;求新点坐标 (i, j ) ;将新点（i , j）切换为当前点（x , y） ;if ( (x ,ｙ)= =(ｍ,n) ) 结束 ;else 重置 d=0 ;}else d++ ;}}（4）时间复杂程度时间复杂程度为O（1）2.3 其他在运行时可选择是否自己构造地图，实现函数如下：void creatmap() //自创地图函数{for(int i=1;i<9;i++){for(int j=1;j<9;j++)Map[i][j]=0;}Map[8][9]=1;printmap();cout<<"请设置障碍物位置:（x,y）。
数据结构栈与队列的实验报告实验概述本次实验的目的是通过对栈和队列进行实现和应用，加深对数据结构中的栈和队列的理解和巩固操作技能。
栈和队列作为常见的数据结构在程序开发中得到了广泛的应用，本次实验通过 C++ 语言编写程序，实现了栈和队列的基本操作，并对两种数据结构进行了应用。
实验内容1. 栈的实现栈是一种先进后出的数据结构，具有后进先出的特点。
通过使用数组来实现栈，实现入栈、出栈、输出栈顶元素和清空栈等操作。
对于入栈操作，将元素插入到数组的栈顶位置；对于出栈操作，先将数组的栈顶元素弹出，再使其下移，即将后面的元素全部向上移动一个位置；输出栈顶元素则直接输出数组的栈顶元素；清空栈则将栈中所有元素全部清除即可。
3. 栈和队列的应用利用栈和队列实现八皇后问题的求解。
八皇后问题，是指在8×8 的国际象棋盘上放置八个皇后，使得任意两个皇后都不能在同一行、同一列或者同一对角线上。
通过使用栈来保存当前八皇后的位置，逐个放置皇后并检查是否有冲突。
如果当前位置符合要求，则将位置保存到栈中，并继续查询下一个皇后的位置。
通过使用队列来进行八数码问题的求解。
八数码问题，是指在3×3 的矩阵中给出 1 至 8 的数字和一个空格，通过移动数字，最终将其变为 1 2 3 4 5 6 7 8 空的排列。
通过使用队列，从初始状态出发，枚举每种情况，利用队列进行广度遍历，逐一枚举状态转移，找到对应的状态后进行更新，周而复始直到找到正确的答案。
实验结果通过使用 C++ 语言编写程序，实现了栈和队列的基本操作，并对八皇后和八数码问题进行了求解。
程序执行结果如下：栈和队列实现的基本操作都能够正常进行，并且运行效率较高。
栈和队列的实现方便了程序编写并加速了程序运行。
2. 八皇后问题的求解通过使用栈来求解八皇后问题，可以得到一组成立的解集。
图中展示了求解某一种八皇后问题的过程。
从左到右是棋盘的列数，从上到下是棋盘的行数，通过栈的操作，求出了在棋盘上符合不同要求（不在同一行、同一列和斜线上）的八皇后位置。
数据结构栈和队列实验报告数据结构栈和队列实验报告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)的特点。
数据结构实验三栈和队列的应用数据结构实验三：栈和队列的应用在计算机科学领域中，数据结构是组织和存储数据的重要方式，而栈和队列作为两种常见的数据结构，具有广泛的应用场景。
本次实验旨在深入探讨栈和队列在实际问题中的应用，加深对它们特性和操作的理解。
一、栈的应用栈是一种“后进先出”（Last In First Out，LIFO）的数据结构。
这意味着最后进入栈的元素将首先被取出。
1、表达式求值在算术表达式的求值过程中，栈发挥着重要作用。
例如，对于表达式“2 ＋ 3 4”，我们可以通过将操作数压入栈，操作符按照优先级进行处理，实现表达式的正确求值。
当遇到数字时，将其压入操作数栈；遇到操作符时，从操作数栈中弹出相应数量的操作数进行计算，将结果压回操作数栈。
最终，操作数栈中的唯一值就是表达式的结果。
2、括号匹配在程序代码中，检查括号是否匹配是常见的任务。
可以使用栈来实现。
遍历输入的字符串，当遇到左括号时，将其压入栈；当遇到右括号时，弹出栈顶元素，如果弹出的左括号与当前右括号类型匹配，则继续，否则表示括号不匹配。
3、函数调用和递归在程序执行过程中，函数的调用和递归都依赖于栈。
当调用一个函数时，当前的执行环境（包括局部变量、返回地址等）被压入栈中。
当函数返回时，从栈中弹出之前保存的环境，继续之前的执行。
递归函数的执行也是通过栈来实现的，每次递归调用都会在栈中保存当前的状态，直到递归结束，依次从栈中恢复状态。
二、队列的应用队列是一种“先进先出”（First In First Out，FIFO）的数据结构。
1、排队系统在现实生活中的各种排队场景，如银行排队、餐厅叫号等，可以用队列来模拟。
新到达的顾客加入队列尾部，服务完成的顾客从队列头部离开。
通过这种方式，保证了先来的顾客先得到服务，体现了公平性。
2、广度优先搜索在图的遍历算法中，广度优先搜索（BreadthFirst Search，BFS）常使用队列。
从起始节点开始，将其放入队列。
【精品】数据结构栈和队列实验报告实验目的：1.了解栈和队列的概念和基本操作。
2.熟练掌握按顺序存储、链式存储、循环存储结构。
3.掌握栈和队列的应用。
实验环境：操作系统：Windows 7编程软件：Dev-C++实验内容：1.用数组作为栈的存储结构，并以学生管理系统为例，实现“进栈”、“出栈”等基本操作。
先用 typedef struct 学生信息实现一个结构体类型，包含了学号、姓名、性别、出生日期、专业等成员。
typedef struct student{char num[10]; //学号char name[10]; //姓名char sex[2]; //性别int year; //出生年份int major; //专业}StuType;定义一个常量 MAXSIZE 来代表栈的最大空间，建立一个顺序栈。
初始化栈：void init_seqstack(SeqStack &p){p.top = -1;}判断是否为空：进栈操作：bool push_seqstack(SeqStack &p,StuType e){if(p.top==MAXSIZE-1)return 0;p.top++;p.data[p.top]=e;return 1;}定义一个链表结构体类型以存放队列，包含首节点指针和尾结点指针。
typedef struct link_queue{ComType data;struct QueueNode *next;}QueueNode;出队操作：bool de_queue(queue &q,ComType &qdata){QueueNode *p=q.front->next;if(q.front==q.rear)return false;qdata=p->data;q.front->next=p->next;if(q.rear==p)q.rear=q.front;free(p);return true;}实验结果：通过本次实验，我可以熟练掌握栈和队列的基本概念和操作，并能够在相应的程序设计中熟练操作，达到掌握栈和队列的目标。
实验报告——栈和队列的应用第一篇：实验报告——栈和队列的应用实验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();//调用执行命令的函数，将命令打印并删除}三、程序调试过程中所出现的错误无。
