数据结构课程实验实训报告--堆栈和队列的基本操作。

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

数据结构栈与队列的实验报告实验概述本次实验的目的是通过对栈和队列进行实现和应用，加深对数据结构中的栈和队列的理解和巩固操作技能。

栈和队列作为常见的数据结构在程序开发中得到了广泛的应用，本次实验通过 C++ 语言编写程序，实现了栈和队列的基本操作，并对两种数据结构进行了应用。

实验内容1. 栈的实现栈是一种先进后出的数据结构，具有后进先出的特点。

通过使用数组来实现栈，实现入栈、出栈、输出栈顶元素和清空栈等操作。

对于入栈操作，将元素插入到数组的栈顶位置；对于出栈操作，先将数组的栈顶元素弹出，再使其下移，即将后面的元素全部向上移动一个位置；输出栈顶元素则直接输出数组的栈顶元素；清空栈则将栈中所有元素全部清除即可。

3. 栈和队列的应用利用栈和队列实现八皇后问题的求解。

八皇后问题，是指在8×8 的国际象棋盘上放置八个皇后，使得任意两个皇后都不能在同一行、同一列或者同一对角线上。

通过使用栈来保存当前八皇后的位置，逐个放置皇后并检查是否有冲突。

如果当前位置符合要求，则将位置保存到栈中，并继续查询下一个皇后的位置。

通过使用队列来进行八数码问题的求解。

八数码问题，是指在3×3 的矩阵中给出 1 至 8 的数字和一个空格，通过移动数字，最终将其变为 1 2 3 4 5 6 7 8 空的排列。

通过使用队列，从初始状态出发，枚举每种情况，利用队列进行广度遍历，逐一枚举状态转移，找到对应的状态后进行更新，周而复始直到找到正确的答案。

实验结果通过使用 C++ 语言编写程序，实现了栈和队列的基本操作，并对八皇后和八数码问题进行了求解。

程序执行结果如下：栈和队列实现的基本操作都能够正常进行，并且运行效率较高。

栈和队列的实现方便了程序编写并加速了程序运行。

2. 八皇后问题的求解通过使用栈来求解八皇后问题，可以得到一组成立的解集。

图中展示了求解某一种八皇后问题的过程。

从左到右是棋盘的列数，从上到下是棋盘的行数，通过栈的操作，求出了在棋盘上符合不同要求（不在同一行、同一列和斜线上）的八皇后位置。

栈和队列的操作实验小结一、实验目的本次实验旨在深入理解和掌握栈和队列这两种基本数据结构的基本操作，包括插入、删除、查找等操作，并通过实际操作加深对这两种数据结构特性的理解。

二、实验原理栈（Stack）：栈是一种后进先出（Last In First Out，LIFO）的数据结构，即最后一个进入栈的元素总是第一个出栈。

在计算机程序中，栈常常被用来实现函数调用和递归等操作。

队列（Queue）：队列是一种先进先出（First In First Out，FIFO）的数据结构，即第一个进入队列的元素总是第一个出队。

在计算机程序中，队列常常被用来实现任务的调度和缓冲等操作。

三、实验步骤与结果创建一个空栈和一个空队列。

对栈进行入栈（push）和出栈（pop）操作，观察并记录结果。

可以发现，栈的出栈顺序与入栈顺序相反，体现了后进先出的特性。

对队列进行入队（enqueue）和出队（dequeue）操作，观察并记录结果。

可以发现，队列的出队顺序与入队顺序相同，体现了先进先出的特性。

尝试在栈和队列中查找元素，记录查找效率和准确性。

由于栈和队列的特性，查找操作并不像在其他数据结构（如二叉搜索树或哈希表）中那样高效。

四、实验总结与讨论通过本次实验，我更深入地理解了栈和队列这两种数据结构的基本特性和操作。

在实际编程中，我可以根据需求选择合适的数据结构来提高程序的效率。

我注意到，虽然栈和队列在某些操作上可能不如其他数据结构高效（如查找），但它们在某些特定场景下具有无可替代的优势。

例如，在实现函数调用和递归时，栈的特性使得它成为最自然的选择；在实现任务调度和缓冲时，队列的特性使得它成为最佳选择。

我也认识到，不同的数据结构适用于解决不同的问题。

在选择数据结构时，我需要考虑数据的特性、操作的频率以及对时间和空间复杂度的需求等因素。

通过实际操作，我对栈和队列的实现方式有了更深入的理解。

例如，我了解到栈可以通过数组或链表来实现，而队列则可以通过链表或循环数组来实现。

数据结构栈和队列实验报告C语言源码（程序在C-Free下通过）课程名称数据结构实验项目名称栈和队列(一)实验目的和要求;熟练掌握栈及队列基本操作的实现(二)实验主要内容;(1) 建立栈并进行元素(8，9，5，4)入栈，实现链栈的建立及入栈的基本操作;(2) 实现元素(9，5)的出栈，实现链栈的出栈的操作;(3) 建立链队列，并实现元素(4,5,7,6,8)入队，实现链队列的建立，和入队的基本操作;(4) 实现元素(4,5,7,6,8)出队，实现链队列的出队的基本操作 (三)主要仪器设备计算机，VC++高级程序语言(四)实验原理栈的修改时按照先进后出的原则进行的，试验中用到构造空栈，及入栈出栈操作。

队列是一种先进先出的线性表，只允许在表的一端插入，而在另一端删除元素，试验中构造队并且入队出队。

(五)实验步骤及调试分析;根据课本基本操作写好源程序，基本操作在书本中已经给出，写出主函数，调试分析程序，找出错误，并修改后程序能够运行并得出正确输出。

试验中，有些小错误经常犯，比如符号，函数声明等。

(六)实验结果及分析;实验结果如下:能够按照实验要求得出正确结果(七)附录:源程序#include<stdio.h>#include<malloc.h> #define OK 1#define ERROR 0#define OVERFLOW -2 typedef int elemtype; typedef int status; typedef struct QNode{elemtype data;struct QNode *next; }QNode,*QueuePtr;typedef struct {QueuePtr front;QueuePtr rear;}LinkQueue;typedef struct lnode {elemtype data;struct lnode *next; }stacknode, *linkstack; status initstack(linkstack top) {top->next = NULL; }status isempty(linkstack top) {if(top->next == NULL) return OK;return ERROR;}status push(linkstack top, elemtype e) {stacknode *p;p= (stacknode *)malloc(sizeof(stacknode));if(p == NULL) return ERROR;p->data = e;p->next = top->next;top->next = p;return OK;}status pop(linkstack top, elemtype *e) {if(isempty(top)) return ERROR;stacknode *p = top->next;*e = p->data;top->next = p->next;free(p);return OK;}status shstack(linkstack top){stacknode *p;p= (stacknode *)malloc(sizeof(stacknode));p->next=top->next;while(p->next!=NULL){printf("%d ",p->next->data);p->next=p->next->next;}return OK;}status initqueue(LinkQueue *q){(*q).front=(*q).rear=(QueuePtr)malloc(sizeof(QNode)); if (!(*q).front) exit(OVERFLOW);(*q).front->next=NULL;return OK;}status enqueue(LinkQueue *q,elemtype e){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,elemtype *e){ if((*q).front==(*q).rear) return ERROR; QueuePtr p;p=(*q).front->next;*e=p->data;//注意(*q).front->next=p->next;if((*q).rear==p) (*q).rear==(*q).front; free(p);return OK;}void main(){linkstack s;s=(linkstack)malloc(sizeof(stacknode)); initstack(s);printf("进入栈的4个元素依次为:\n");for (int i=0;i<4;i++){elemtype a;scanf("%d",&a);push(s,a);}printf("\n栈顶到栈底的元素依次为;\n"); shstack(s);elemtype b,c,d;pop(s,&b);pop(s,&c);pop(s,&d);push(s,b);printf("\n\n出栈的元素为:");printf("%d",c);printf(" %d\n",d);printf("\n现在栈中的元素为:");shstack(s);LinkQueue q;initqueue(&q);elemtype a;printf("\n\n\n请输入5个进队的元素:\n"); for(int i=0;i<5;i++){scanf("%d",&a);enqueue(&q,a);}printf("\n元素的出列为:\n");for(int i=0;i<5;i++){elemtype e; dequeue(&q,&e); printf(" %d",e); }}。

栈和队列实验报告总结一、实验目的本次实验的主要目的是掌握栈和队列这两种数据结构的基本概念和操作方法，以及了解它们在计算机程序设计中的应用。

二、实验原理1. 栈栈是一种后进先出（LIFO）的数据结构，它可以看作是一种线性表。

栈顶指针指向栈顶元素，每次插入或删除元素时，都会改变栈顶指针的位置。

常见的操作有入栈（push）、出栈（pop）、取栈顶元素（top）等。

2. 队列队列是一种先进先出（FIFO）的数据结构，它也可以看作是一种线性表。

队头指针指向队头元素，队尾指针指向队尾元素。

常见的操作有入队（enqueue）、出队（dequeue）、取队头元素（front）等。

三、实验内容与步骤1. 栈本次实验中我们需要完成以下操作：① 初始化一个空栈；② 将10个整数依次压入栈中；③ 弹出3个整数并输出；④ 将5个整数依次压入栈中；⑤ 弹出所有整数并输出。

具体步骤如下：Step 1：定义一个Stack类，并在其中定义初始化、入栈、出栈、取栈顶元素等方法；Step 2：在主函数中创建一个Stack对象，并调用初始化方法；Step 3：使用循环将10个整数依次压入栈中；Step 4：使用循环弹出3个整数并输出；Step 5：使用循环将5个整数依次压入栈中；Step 6：调用出栈方法弹出所有整数并输出。

2. 队列本次实验中我们需要完成以下操作：① 初始化一个空队列；② 将10个整数依次加入队列中；③ 弹出3个整数并输出；④ 将5个整数依次加入队列中；⑤ 弹出所有整数并输出。

具体步骤如下：Step 1：定义一个Queue类，并在其中定义初始化、入队、出队、取队头元素等方法；Step 2：在主函数中创建一个Queue对象，并调用初始化方法；Step 3：使用循环将10个整数依次加入队列中；Step 4：使用循环弹出3个整数并输出；Step 5：使用循环将5个整数依次加入队列中；Step 6：调用出队方法弹出所有整数并输出。

堆栈和队列的基本操作一、堆栈（Stack）堆栈是一种具有特殊插入和删除规则的线性数据结构。

它按照“后进先出”（Last-In-First-Out, LIFO）原则管理数据。

1.堆栈的初始化堆栈的初始化即创建一个空堆栈。

2. 入栈（Push）入栈是将数据插入到堆栈顶部的操作。

数据插入后，堆栈的长度加1、插入的数据成为新的堆栈顶部。

3. 出栈（Pop）出栈是将堆栈顶部的数据删除的操作。

删除后，堆栈的长度减1、删除的数据为原堆栈的顶部。

4. 取栈顶元素（Top）取栈顶元素是获取当前堆栈顶部的数据，而不进行删除操作。

5. 判断堆栈是否为空（IsEmpty）判断堆栈是否为空，即判断堆栈的长度是否为0。

6. 获取堆栈长度（GetSize）获取堆栈的长度，即当前堆栈中元素的数量。

堆栈可以使用数组或链表来实现。

数组实现的堆栈称为顺序堆栈，链表实现的堆栈称为链式堆栈。

堆栈的应用：-递归函数的调用和返回-表达式求值-括号匹配-浏览器前进后退功能二、队列（Queue）队列也是一种具有特定插入和删除规则的线性数据结构。

它按照“先进先出”（First-In-First-Out, FIFO）原则管理数据。

1.队列的初始化队列的初始化即创建一个空队列。

2. 入队（Enqueue）入队是将数据插入到队列尾部的操作。

数据插入后，队列的长度加1、插入的数据成为新的队列尾部。

3. 出队（Dequeue）出队是将队列头部的数据删除的操作。

删除后，队列的长度减1、删除的数据为原队列的头部。

4. 获取队首元素（Peek）获取队列头部的数据，而不进行删除操作。

5. 判断队列是否为空（IsEmpty）判断队列是否为空，即判断队列的长度是否为0。

6. 获取队列长度（GetSize）获取队列的长度，即当前队列中元素的数量。

队列也可以使用数组或链表来实现。

数组实现的队列称为顺序队列，链表实现的队列称为链式队列。

还有一种特殊的队列称为优先队列，它根据元素的优先级进行排序。

栈和队列的应用实验报告栈和队列的应用实验报告引言：栈和队列是计算机科学中常用的数据结构，它们在各种算法和应用中都有广泛的应用。

本实验报告旨在探讨栈和队列的基本概念、特性以及它们在实际应用中的具体使用。

一、栈的基本概念和特性栈是一种特殊的数据结构，它遵循“先进后出”的原则。

栈有两个基本操作：压栈（push）和弹栈（pop）。

压栈将元素添加到栈的顶部，弹栈则将栈顶元素移除。

栈还具有一个重要的特性，即它的访问方式是受限的，只能访问栈顶元素。

在实际应用中，栈可以用于实现递归算法、表达式求值、括号匹配等。

例如，在递归算法中，当函数调用自身时，需要将当前状态保存到栈中，以便在递归结束后能够恢复到正确的状态。

另外，栈还可以用于实现浏览器的“后退”功能，每次浏览新页面时，将当前页面的URL压入栈中，当用户点击“后退”按钮时，再从栈中弹出最近访问的URL。

二、队列的基本概念和特性队列是另一种常见的数据结构，它遵循“先进先出”的原则。

队列有两个基本操作：入队（enqueue）和出队（dequeue）。

入队将元素添加到队列的尾部，出队则将队列头部的元素移除。

与栈不同的是，队列可以访问头部和尾部的元素。

在实际应用中，队列经常用于任务调度、消息传递等场景。

例如，在操作系统中，任务调度器使用队列来管理待执行的任务，每当一个任务执行完毕后，从队列中取出下一个任务进行执行。

另外，消息队列也是一种常见的应用，它用于在分布式系统中传递消息，保证消息的顺序性和可靠性。

三、栈和队列在实际应用中的具体使用1. 栈的应用栈在计算机科学中有广泛的应用。

其中一个典型的应用是表达式求值。

当计算机遇到一个复杂的表达式时，需要将其转化为逆波兰表达式，然后使用栈来进行求值。

栈的特性使得它非常适合处理这种情况，可以方便地保存运算符和操作数的顺序，并按照正确的顺序进行计算。

另一个常见的应用是括号匹配。

在编程语言中，括号是一种常见的语法结构，需要保证括号的匹配性。

数据结构实验报告实验名称：实验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<<"种摆放方法。