实验二、栈和队列的应用

实验日期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.一个程序中如果要用到两个栈时，可通过两个栈共享一维数组来实现，即双向栈共享邻接空间。

栈与队列的应用栈(Stack)和队列(Queue)是计算机科学中常见的数据结构，它们分别具有先进后出（Last-In-First-Out, LIFO）和先进先出（First-In-First-Out, FIFO）的特性。

这两种数据结构在计算机领域有着广泛的应用，本文将介绍一些栈与队列的常见应用场景。

一、栈的应用1. 括号匹配栈常被用于判断表达式中的括号是否匹配。

通过遍历表达式中的每个字符，将左括号入栈，当遇到右括号时，检查栈顶元素与右括号是否匹配。

若匹配，则出栈；若不匹配，则说明括号不匹配。

2. 浏览器的前进与后退功能在浏览器中，我们可以通过点击前进和后退按钮来在不同的网页之间切换。

这种功能可以使用两个栈来实现：一个栈用于存储用户浏览的历史页面，另一个栈用于存储用户后退的页面。

当用户点击前进按钮时，从后退栈中弹出页面并推入历史页面栈；当用户点击后退按钮时，从历史页面栈中取出页面并推入后退页面栈。

3. 函数调用与递归在程序中，函数的调用是通过栈来实现的。

当一个函数被调用时，系统会将该函数的返回地址和参数等信息压入栈中；当函数执行完毕后，从栈中弹出返回地址，继续执行调用函数的下一条指令。

4. 表达式求值中缀表达式求值通常需要借助栈来实现。

通过将表达式转换成后缀表达式，并使用栈存储运算符和操作数，可以按照规定的优先级进行计算，得到最终的结果。

二、队列的应用1. 打印任务队列在计算机系统中，多个用户同时提交打印任务时，可以使用队列来管理这些任务。

每当有新的任务到达时，将其加入队列尾部，打印机则从队列头部取出任务进行打印。

这样可以保证任务的顺序性，并避免多个任务之间的冲突。

2. 消息队列在分布式系统中，消息队列通常用于解耦不同模块之间的通信。

一个模块可以将消息发送到队列中，而其他模块可以异步地从队列中获取消息并进行相应的处理。

这种方式提高了系统的可伸缩性和稳定性。

3. 广度优先搜索在图论中，广度优先搜索（Breadth-First Search, BFS）可以借助队列来实现。

实验二栈和队列的基本操作实现及其应用一_一、实验目的1、熟练掌握栈和队列的基本操作在两种存储结构上的实现。

一_二、实验内容题目一、试写一个算法，判断依次读入的一个以为结束符的字符序列，是否为回文。

所谓“回文“是指正向读和反向读都一样的一字符串,如“321123”或“ableelba”。

相关常量及结构定义：#define STACK_INIT_SIZE 100#define STACKINCREMENT 10typedef int SElemType;typedef struct SqStack{ SElemType *base;SElemType *top;int stacksize;}SqStack;设计相关函数声明：判断函数：int IsReverse()栈：int InitStack(SqStack &S )int Push(SqStack &S, SElemType e )int Pop(SqStack &S,SElemType &e)int StackEmpty(s)一_三、数据结构与核心算法的设计描述1、初始化栈/* 函数功能：对栈进行初始化。

参数：栈(SqStack S)。

成功初始化返回0,否则返回-1 */int InitStack(SqStack &S){S.base=(SElemType *)malloc(10*sizeof(SElemType));if(!S.base) //判断有无申请到空间return -1; //没有申请到内存,参数失败返回-1S.top=S.base;S.stacksize=STACK_INIT_SIZE;S.base=new SElemType;return 0;}2、判断栈是否是空/*函数功能:判断栈是否为空。

参数; 栈(SqStack S)。

栈为空时返回-1,不为空返回0*/int StackEmpty(SqStack S){if(S.top==S.base) return -1;else return 0;}3、入栈/*函数功能:向栈中插入元素。

栈和队列的应用(10003809389j)一实验目的使学生掌握栈的特点及其逻辑结构和物理结构的实现；使学生掌握队列的特点及其逻辑结构和物理结构的实现；使学生掌握链栈和顺序栈结构的插入、删除等基本运算的实现；使学生掌握链队列和顺序队列结构的插入、删除等基本运算的实现；使学生熟练运用栈结构解决常见实际应用问题；使学生熟练运用队列结构解决常见实际应用问题；二实验环境所需硬件环境为微机；所需软件环境为 Microsoft Visual C++ 6.0 ；三实验内容链栈:#include "LinkList0.c"/*详见实验1*/LinkList InitStack_Sl() {LinkList S;S=InitList_Sl();return S; }Status DestroyStack_Sl(LinkList S) {if(!S) return ERROR;/*链栈不存在*/DestroyList_Sl(S);return OK; }Status StackEmpty_Sl(LinkList S) {if(!S) return ERROR;/*链栈不存在*/if(S->next==NULL)return TRUE;elsereturn FALSE; }/*若链栈S存在，则当S非空时返回栈顶元素e */Status StackGetTop_Sl(LinkList S) {if(!S) return ERROR;/*链栈不存在*/if(S->next==NULL) return FALSE;/*栈空*/elsereturn (S->next->elem); }/*若链栈S存在，则当S非空时，删除栈顶元素并用e保存删除的栈顶元素*/ Status StackPop_Sl(LinkList S,ElemType *e) {if(!S) return ERROR;/*链栈不存在*/ListDelete_Sl(S,e);return OK; }/*若链栈S存在时，插入元素e为新的栈顶元素*/Status StackPush_Sl(LinkList S,ElemType e) {if(!S) return ERROR;/*链栈不存在*/ListInsert_Sl(S,e);return OK; }/*若链栈S存在，返回链栈中元素个数*/int StackLength_Sl(LinkList S) {if(!S) return ERROR;/*链栈不存在*/return ListLength_Sl(S); }/*若链栈S存在，遍历链栈S，对每个元素执行操作void(*operate)(ElemType*)*/Status StackTraverse_Sl(LinkList S,void(*operate)(ElemType*)) { if(!S) return ERROR;/*链栈不存在*/return(ListTraverse_Sl(S,operate)); }链队列#include "LinkList0.c"/*详见实验1*/typedef struct Qode{ElemType elem;struct Qode *next;} Qode,*Queue;typedef struct {Queue front;Queue rear;}Linkqueue, *LinkQueue;/*InitQueue_Sq()构造一个空的队列*/LinkQueue InitQueue_Sl() {LinkQueue Q;Q->front=Q->rear=(Queue)malloc(sizeof(Qode));if(!Q->front) return NULL;/*存储分配失败*/Q->front->next=NULL;return Q; }/*若队列Q存在，销毁链队列Q*/Status DestroyQueue_Sl(LinkQueue Q) {Queue p;if(!Q) return ERROR;/*链队列不存在*/do{ /*释放单向线性链表空间*/p=Q->front;Q->front=Q->front->next;free(p);}while(Q->front);return OK; }/*若链队列Q存在，则当Q为空时返回TRUE，否则返回FALSE*/Status QueueEmpty_Sl(LinkQueue Q) {if(!Q) return ERROR;/*链队列不存在*/if(Q->front==Q->rear)return TRUE;elsereturn FALSE; }/*若链队列Q存在，则当Q非空时，返回队头元素e */Status QueueGetTop_Sl(LinkQueue Q,ElemType e) {if(!Q) return ERROR;/*链队列不存在*/if(QueueEmpty_Sl(Q)==TRUE) return FALSE;/*队列空*/else return (Q->front->next->elem); }/*若链队列Q存在，则当Q非空时，删除队头元素并用e保存删除的队头元素*/ Status DeQueue_Sl(LinkQueue Q,ElemType *e) {Queue p;if(!Q) return ERROR;/*顺序队列不存在*/if(QueueEmpty_Sl(Q)==TRUE) return FALSE;/*队列空*/else{p=Q->front->next;*e=p->elem;Q->front->next=p->next;if(Q->front->next==NULL) Q->rear=Q->front;free(p);return OK; } }/*若链队列Q存在时，插入元素e为新的队头元素*/ Status EnQueue_Sl(LinkQueue Q,ElemType e) {Queue p;if(!Q) return ERROR;/*单向线性链表结点L不存在*/ p=(Queue)malloc(sizeof(Qode));if(!p) exit(OVERFLOW); /*存储空间增加失败*/p->next=NULL;p->elem=e;Q->rear->next=p;Q->rear=p;return OK; }/*若链队列Q存在，返回链队列元素个数*/int QueueLength_Sl(LinkQueue Q) {int i=0;Queue p;if(!Q) return ERROR;/*链队列不存在*/p=Q->front;while(p!=Q->rear){ i++;p=p->next; }return (i); }/*若链队列Q存在，遍历链队列Q，对每个元素执行操作void(*operate)(ElemType*)*/ Status QueueTraverse_Sl(LinkQueue Q,void(*operate)(ElemType*)) {Queue p;if(!Q) return ERROR;/*链队列不存在*/p=Q->front->next;while(p!=NULL){ operate(&p->elem);p=p->next; }return(OK); }表达式求解#include "LinkStack.c"//用链栈实现中缀表达式求解。

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

二、设计思想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运算。

《数据结构》第五次实验报告学生姓名学生班级学生学号指导老师雷大江重庆邮电大学计算机学院一、实验内容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）。

栈和队列应用案例栈和队列是计算机科学中常用的数据结构，它们具有各自独特的特性和应用场景。

栈是一种后进先出（LIFO）的数据结构，而队列则是一种先进先出（FIFO）的数据结构。

本文将介绍栈和队列的应用案例，并分析它们在实际问题中的使用。

一、栈的应用案例1. 后退和前进功能在浏览器中，我们经常使用后退和前进按钮来切换网页。

这种功能可以通过一个栈来实现。

每当我们访问一个新的网页时，将当前的网页URL压入栈中。

当我们点击后退按钮时，可以从栈中弹出上一个URL，实现后退功能。

当我们点击前进按钮时，可以从另一个栈中弹出下一个URL，实现前进功能。

2. 括号匹配在编程语言中，括号匹配是一种常见的问题。

我们可以使用栈来解决括号匹配的问题。

遍历字符串，当遇到左括号时，将其压入栈中；当遇到右括号时，从栈中弹出一个元素，并判断是否与当前右括号匹配。

如果栈为空或出现不匹配的情况，则说明括号不匹配。

3. 逆波兰表达式逆波兰表达式是一种将运算符号放在操作数之后的数学表达式表示方式。

使用栈可以轻松计算逆波兰表达式。

遍历逆波兰表达式，当遇到数字时，将其压入栈中；当遇到运算符时，从栈中弹出两个数字进行计算，并将结果压入栈中。

最终，栈中剩下的数字即为逆波兰表达式的计算结果。

二、队列的应用案例1. 银行排队在银行办理业务时，通常需要排队等待。

这可以通过队列来实现。

当顾客到达银行时，将其加入队列的末尾。

当柜台有空余时，从队列的头部取出一个顾客进行业务办理。

这种方式可以保证先来的顾客先办理业务，实现公平的排队系统。

2. 多线程任务调度在多线程编程中，任务调度是一个重要的问题。

队列可以用于实现任务的调度和执行。

将需要执行的任务加入队列中，每个线程从队列中取出一个任务进行处理。

这种方式可以充分利用系统资源，实现高效的任务并行处理。

3. 数据缓存队列还可用于数据缓存。

当有大量数据需要处理时，可以将数据加入队列中，然后由单独的线程从队列中取出数据进行处理。

中国计量学院实验报告实验课程：《算法与数据结构》实验名称：栈与队列的一个应用班级： 14计算机1 实验日期：实验目的及要求：一、实验目的1、了解栈和队列的特性2. 掌握栈和队列的顺序表示及实现3. 掌握栈和队列的链式表示及实现4、学会利用栈或队列去求解实际问题二、实验要求从键盘输入包括任意三种括号（即，圆括号()、方括号[]和花括号{}）的四则运算（+、-、*、/）表达式，编程判断该表达式的括号是否匹配。

若匹配则计算出表达式的值；若不匹配，则输出“此表达式括号不匹配”。

实验中，假设:(1) 除括号不匹配外，不存在其它非法表达式的情况(2) 表达式中只出现数值常量，不出现变量或符号常量三、实验角色1、Document Writer: ADT设计及实验所涉资料的整理、录入及排版2、Programmer: 算法设计及实现3、Tester: 确定测试用例并负责程序测试，测试用例不少于15种数据结构及关键算法说明这一部分描述解决问题所用到的数据结构及关键算法，可用伪代码、代码或框图表示，目的是让读者在短时间内清楚地理解作者解决问题的整体思路。

因此，表达方式必须比源代码更通俗易懂。

typedef struct SqStack //栈的顺序存储结构{SElemType *base;SElemType *top;int stacksize;}SqStack;char Precede(char a1 ,char a2)//判定运算符的优先级。

{char r;switch(a2){case'+': //此处由于加减几乎优先级一样，故放在一起case'-':if(a1=='('||a1=='['||a1=='{'||a1=='#')r='<';elser='>';break;case'(':if(a1==')'){cout<<"括号匹配错误!"<<endl;exit(-1);}elser='<';break;}//这里只列举加减，左括号。

栈与队列实验报告总结实验报告总结：栈与队列一、实验目的本次实验旨在深入理解栈（Stack）和队列（Queue）这两种基本的数据结构，并掌握其基本操作。

通过实验，我们希望提高自身的编程能力和对数据结构的认识。

二、实验内容1.栈的实现：我们首先使用Python语言实现了一个简单的栈。

栈是一种后进先出（LIFO）的数据结构，支持元素的插入和删除操作。

在本次实验中，我们实现了两个基本的栈操作：push（插入元素）和pop（删除元素）。

2.队列的实现：然后，我们实现了一个简单的队列。

队列是一种先进先出（FIFO）的数据结构，支持元素的插入和删除操作。

在本次实验中，我们实现了两个基本的队列操作：enqueue（在队尾插入元素）和dequeue（从队头删除元素）。

3.栈与队列的应用：最后，我们使用所实现的栈和队列来解决一些实际问题。

例如，我们使用栈来实现一个算术表达式的求值，使用队列来实现一个简单的文本行编辑器。

三、实验过程与问题解决在实现栈和队列的过程中，我们遇到了一些问题。

例如，在实现栈的过程中，我们遇到了一个“空栈”的错误。

经过仔细检查，我们发现是因为在创建栈的过程中没有正确初始化栈的元素列表。

通过添加一个简单的初始化函数，我们解决了这个问题。

在实现队列的过程中，我们遇到了一个“队列溢出”的问题。

这是因为在实现队列时，我们没有考虑到队列的容量限制。

通过添加一个检查队列长度的条件语句，我们避免了这个问题。

四、实验总结与反思通过本次实验，我们对栈和队列这两种基本的数据结构有了更深入的理解。

我们掌握了如何使用Python语言实现这两种数据结构，并了解了它们的基本操作和实际应用。

在实现栈和队列的过程中，我们也学到了很多关于编程的技巧和方法。

例如，如何调试代码、如何设计数据结构、如何优化算法等。

这些技巧和方法将对我们今后的学习和工作产生积极的影响。

然而，在实验过程中我们也发现了一些不足之处。

例如，在实现栈和队列时，我们没有考虑到异常处理和性能优化等方面的问题。