实验二栈、队列的实现及应用讲解

栈和队列的实验报告栈和队列的实验报告引言：栈和队列是计算机科学中常用的数据结构，它们在算法设计和程序开发中起着重要的作用。

本实验旨在通过实际操作和观察，深入理解栈和队列的概念、特点以及它们在实际应用中的作用。

一、栈的实验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）1实验题目: 栈和队列的应用2实验内容: 迷宫问题3实验目的: 掌握栈和队列的概念及工作原理，运用其原理完成 实验题目中的内容。

4实验要求: 为了使学生更好的掌握与理解课堂上老师所讲的概 念与原理，实验前每个学生要认真预习所做的实验 内容及编写源程序代码（写在纸上与盘中均可），以 便在实验课中完成老师所布置的实验内容5设计原理:6程序清单及注释说明:#include<stdio.h>#include<stdlib.h>#define M 15#define N 15定义迷宫内点的坐标类型struct mark //{int x;int y;};恋"栈元素，嘿嘿。

struct Element //"{行,y列int x,y; //x下一步的方向int d; //d};链栈typedef struct LStack //{Element elem;struct LStack *next;}*PLStack;/*************栈函数****************/构造空栈int InitStack(PLStack &S)//{S=NULL;return 1;}int StackEmpty(PLStack S)//判断栈是否为空{if(S==NULL)return 1;elsereturn 0;}int Push(PLStack &S, Element e)//压入新数据元素 {PLStack p;p=(PLStack)malloc(sizeof(LStack));p->elem=e;p->next=S;S=p;return 1;}int Pop(PLStack &S,Element &e) //栈顶元素出栈 {PLStack p;if(!StackEmpty(S)){e=S->elem;p=S;S=S->next;free(p);return 1;}elsereturn 0;}/***************求迷宫路径函数***********************/void MazePath(struct mark start,struct mark end,int maze[M][N],int diradd[4][2]) {int i,j,d;int a,b;Element elem,e;PLStack S1, S2;InitStack(S1);InitStack(S2);入口点作上标记maze[start.x][start.y]=2; //elem.x=start.x;elem.y=start.y;elem.d=-1; //开始为-1Push(S1,elem);栈不为空 有路径可走while(!StackEmpty(S1)) //{Pop(S1,elem);i=elem.x;j=elem.y;d=elem.d+1; //下一个方向试探东南西北各个方向while(d<4) //{a=i+diradd[d][0];b=j+diradd[d][1];如果到了出口if(a==end.x && b==end.y && maze[a][b]==0) //{elem.x=i;elem.y=j;elem.d=d;Push(S1,elem);elem.x=a;elem.y=b;elem.d=886; //方向输出为-1 判断是否到了出口Push(S1,elem);东 1=南 2=西 3=北 886为则走出迷宫\n\n通路为:(行坐标,列坐标,方向)\n"); printf("\n0=逆置序列 并输出迷宫路径序列while(S1) //{Pop(S1,e);Push(S2,e);}while(S2){Pop(S2,e);printf("-->(%d,%d,%d)",e.x,e.y,e.d);}跳出两层循环，本来用break,但发现出错，exit又会结束程序，选用return还是不return; //错滴o(∩_∩)o...}if(maze[a][b]==0) //找到可以前进的非出口的点{标记走过此点maze[a][b]=2; //elem.x=i;elem.y=j;elem.d=d;Push(S1,elem); //当前位置入栈下一点转化为当前点i=a; //j=b;d=-1;}d++;}}没有找到可以走出此迷宫的路径\n");printf("}建立迷宫*******************//*************void initmaze(int maze[M][N]){int i,j;迷宫行,列int m,n; //请输入迷宫的行数 m=");printf("scanf("%d",&m);请输入迷宫的列数 n=");printf("scanf("%d",&n);请输入迷宫的各行各列:\n用空格隔开,0代表路,1代表墙\n",m,n);printf("\nfor(i=1;i<=m;i++)for(j=1;j<=n;j++)scanf("%d",&maze[i][j]);printf("\n");你建立的迷宫为o(∩_∩)o...加一圈围墙for(i=0;i<=m+1;i++) //{maze[i][0]=1;maze[i][n+1]=1;}for(j=0;j<=n+1;j++){maze[0][j]=1;maze[m+1][j]=1;}输出迷宫for(i=0;i<=m+1;i++) //{for(j=0;j<=n+1;j++)printf("%d ",maze[i][j]);printf("\n");}}void main(){int sto[M][N];入口和出口的坐标struct mark start,end; //start,end行增量和列增量 方向依次为东西南北 int add[4][2]={{0,1},{1,0},{0,-1},{-1,0}};//建立迷宫initmaze(sto);//输入入口的横坐标,纵坐标[逗号隔开]\n");printf("scanf("%d,%d",&start.x,&start.y);输入出口的横坐标,纵坐标[逗号隔开]\n");printf("scanf("%d,%d",&end.x,&end.y);MazePath(start,end,sto,add); //find pathsystem("PAUSE");}7.运行与测试及结果。

实验二栈和队列的基本操作实现及其应用一_一、实验目的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、入栈/*函数功能:向栈中插入元素。

实验二栈和队列1、实验目的：（1）熟悉栈的特点（先进后出)及栈的基本操作,如入栈、出栈等,掌握栈的基本操作在栈的顺序存储结构和链式存储结构上的实现；（2）熟悉队列的特点（先进先出）及队列的基本操作，如入队、出队等，掌握队列的基本操作在队列的顺序存储结构和链式存储结构上的实现。

2、实验要求：（1）复习课本中有关栈和队列的知识；（2）用C语言完成算法和程序设计并上机调试通过;（3）撰写实验报告，给出算法思路或流程图和具体实现（源程序）、算法分析结果（包括时间复杂度、空间复杂度以及算法优化设想)、输入数据及程序运行结果（必要时给出多种可能的输入数据和运行结果）。

3、实验内容［实验1] 栈的顺序表示和实现实验内容与要求:编写一个程序实现顺序栈的各种基本运算，并在此基础上设计一个主程序,完成如下功能：（1）初始化顺序栈（2）插入元素(3）删除栈顶元素（4）取栈顶元素(5）遍历顺序栈(6）置空顺序栈分析：栈的顺序存储结构简称为顺序栈,它是运算受限的顺序表。

对于顺序栈，入栈时，首先判断栈是否为满，栈满的条件为：p—〉top= =MAXNUM-1,栈满时，不能入栈；否则出现空间溢出，引起错误，这种现象称为上溢。

出栈和读栈顶元素操作，先判栈是否为空,为空时不能操作,否则产生错误.通常栈空作为一种控制转移的条件。

注意:（1)顺序栈中元素用向量存放（2)栈底位置是固定不变的，可设置在向量两端的任意一个端点（3）栈顶位置是随着进栈和退栈操作而变化的，用一个整型量top（通常称top为栈顶指针)来指示当前栈顶位置#include <stdio.h>＃include 〈malloc。

h>typedef int SElemType；typedef int Status;＃define INIT_SIZE 100#define STACKINCREMENT 10#define Ok 1#define Error 0#define True 1#define False 0typedef struct｛SElemType *base;SElemType ＊top;int stacksize；}SqStack；//初始化栈Status InitStack（SqStack *s)｛s->base = （SElemType *）malloc(INIT_SIZE * sizeof(SElemType））；if（!s->base）｛puts（"存储空间分配失败！”）；return Error；}s-〉top = s—>base;s->stacksize = INIT_SIZE；return Ok;}//清空栈Status ClearStack(SqStack ＊s）｛s-〉top = s—〉base；return Ok;}//栈是否为空Status StackEmpty（SqStack ＊s)｛if（s-〉top == s->base）return True;elsereturn False;}//销毁栈Status Destroy(SqStack *s）free(s->base);s—>base = NULL；s->top = NULL;s-〉stacksize=0；return Ok；}//获得栈顶元素Status GetTop(SqStack ＊s，SElemType &e)｛if(s—〉top == s—>base）return Error；e = *（s—〉top - 1)；return Ok;}//压栈Status 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){puts("存储空间分配失败!"）；return Error；｝s-〉top = s—>base + s—>stacksize;s->stacksize += STACKINCREMENT；}＊s->top++ = e;return Ok；}//弹栈Status Pop（SqStack ＊s, SElemType *e）{if（s—〉top == s—>base）return Error；-—s-〉top；*e = ＊（s—〉top)；return Ok;}//遍历栈Status StackTraverse(SqStack *s,Status(＊visit)(SElemType）) ｛SElemType *b = s—>base;SElemType *t = s—>top；while(t 〉b)visit(＊b++）；printf（"\n"）;return Ok；}Status visit(SElemType c）｛printf（"％d ",c);return Ok;｝int main（){SqStack a;SqStack ＊s = ＆a；SElemType e；InitStack（s);int n;puts（"请输入要进栈的个数:”）;scanf("%d"，&n)；while（n—-)｛int m；scanf("%d", ＆m）；Push（s, m）；｝StackTraverse（s，visit)；puts("”)；Pop（s，＆e)；printf（”%d\n”, e)；printf（"%d\n”, ＊s—>top);Destroy（s）;return 0；｝［实验2] 栈的链式表示和实现实验内容与要求：编写一个程序实现链栈的各种基本运算，并在此基础上设计一个主程序,完成如下功能：（1）初始化链栈(2)链栈置空（3)入栈（4）出栈（5)取栈顶元素（6）遍历链栈分析:链栈是没有附加头结点的运算受限的单链表.栈顶指针就是链表的头指针。

实验二栈和队列的操作一、实验目的1．熟悉栈和队列的存储结构；2．熟悉栈和队列的相关操作；3．利用栈和队列求解一些常见问题。

二、实验内容1、表达式求值任何一个算术表达式都是由操作数(operand) 、运算符(operator) 和界限符(edlimiter) 组成的。

为了简化问题．这里假设算术表达式中的操作数为单个数字表示的变量：运算符有加“ + ”、减“—”、乘“ * ”、除“／”和括号，表达式以“#”结束。

运算法则是括号优先级最高，先乘除，后加减，同级运算自左至右。

程序设计时需设置两个工作栈。

一个称为运算符栈，用OP 表示，用于存放表达式中的运算符：另一个称为操作数栈，用S 表示，用于存放操作数或运算结果。

这两个栈的初始状态均为空。

计算机从左至右扫描表达式，凡遇操作数一律进S 栈；若遇运算符，则要把它的优先数和栈顶运算符的优先数进行比较：若前者大，则该运算符进OP 栈；否则，栈顶运算符退栈、并进行计算，运算对象为S 栈顶上的两个元素，且先退栈的元素在运算量的右侧，后退栈的在运算量的左侧。

试编写一程序，先输入一个表达式，再求表达式的值。

2、数制转换假设现要编制一个满足下列要求的程序：对于输入的任意一个非负十进制整数，打印输出与其等值的八进制数。

从计算过程可见，这八进制的各个数位产生的顺序是从低位到高位的，而打印输出的顺序，一般来说应从高位到低位，这恰好和计算过程相反。

因此，需要先保存在计算过程中得到的八进制数的各位，然后逆序输出，因为它是按“后进先出”的规律进行的，所以用栈最合适。

试编写一个程序，实现将十进制数转换成八进制数并输出。

三、主要任务1、完成算法设计和程序设计，并分析算法时间复杂度和空间复杂度；2、写出程序运行情况，写出输入数据及运行结果；3、撰写实验报告，写出算法设计小结和心得。

四、思考题1、为什么说栈是一种特殊线性表？它的操作与线性表有什么不同？2、对于数制转换算法，如果不用栈如何实现？。

实验2：栈和队列的应用
一、实验目的
1.掌握栈的表示与实现
2.掌握队列的表示与实现
3.掌握栈的入栈、出栈等基本操作
4.掌握队列的入队、出队等基本操作
二、实验内容
1.实现顺序栈各种基本运算的算法，具体操作要求如下：
（1）初始化栈，并判断栈是否为空；
（2）对a,b,c,d,f五个字符元素模拟进栈操作；并判断栈是否为空；
（3）取出栈顶元素；
（4）对a,b,c,d,f五个字符元素做依次出栈操作，并判断栈是否为空；
（5）释放栈。

具体效果如下：
注：若sqstack.cpp文件中的方法不合适，可以作修改。

2.实现链栈各种基本运算的算法
（1）初始化栈，并判断栈是否为空；
（2）对a,b,c,d,f五个字符元素模拟进栈操作；并判断栈是否为空；
（3）取出栈顶元素；
（4）对a,b,c,d,f五个字符元素做依次出栈操作，并判断栈是否为空；
（5）释放栈。

注：若listack.cpp文件中的方法不合适，可以作修改。

三、实验要求
1.独立完成实验程序的编写与调试；
2.实验完成后填写实验报告，学习委员按学号从小到大的顺序提交。

四、思考题
1.读入一个有限大小的整数n，然后按输入次序的相反次序输出各元素的值。

(用顺序栈
实现)
2.利用栈完成数制转换。

任意输入一个十进制数，将其转换成八进制数。

(用顺序栈实
现)。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

实验报告——栈和队列的应用第一篇：实验报告——栈和队列的应用实验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();//调用执行命令的函数，将命令打印并删除}三、程序调试过程中所出现的错误无。

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

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

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

栈有两个基本操作：压栈（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<<"种摆放方法。

栈和队列实验报告引言：计算机科学中的数据结构是解决问题的关键。

栈和队列这两种常用的数据结构，无疑在许多实际应用中起着重要的作用。

本篇报告旨在探讨栈和队列的实验结果，并展示它们的实际应用。

一、栈的实验结果及应用1. 栈的实验结果在实验中，我们设计了一个基于栈的简单计算器，用于实现基本的四则运算。

通过栈的先进后出（Last In First Out）特性，我们成功实现了表达式的逆波兰表示法，并进行了正确的计算。

实验结果表明，栈作为一个非常有效的数据结构，可以很好地处理栈内数据的存储和检索。

2. 栈的应用栈在计算机科学中有许多实际应用。

其中之一是程序调用的存储方式。

在程序调用过程中，每个函数的返回地址都可以通过栈来保存和恢复。

另一个应用是浏览器的历史记录。

浏览器中每个访问网页的URL都可以通过栈来存储，以便用户能够追溯他们之前访问的网页。

二、队列的实验结果及应用1. 队列的实验结果在实验中，我们模拟了一个简单的出租车调度系统，利用队列的先进先出（First In First Out）特性实现乘客的排队和叫车。

实验结果表明，队列作为一个具有高效性和可靠性的数据结构，能够很好地处理排队问题。

2. 队列的应用队列在许多方面都有应用。

一个常见的应用是消息队列。

在网络通信中，消息队列可以用于存储和传递信息，确保按照特定的顺序进行处理。

另一个应用是操作系统的进程调度。

操作系统使用队列来管理各个进程的执行顺序，以实现公平和高效的资源分配。

三、栈和队列的比较及选择1. 效率比较栈和队列在实际应用中的效率取决于具体问题的需求。

栈的操作更简单，仅涉及栈顶元素的插入和删除，因此具有更高的执行速度。

而队列涉及到队头和队尾元素的操作，稍复杂一些。

但是，队列在某些问题中的应用更为广泛，例如调度问题和消息传递问题。

2. 如何选择在选择栈和队列时，需要根据实际问题的性质和需求进行综合考虑。

如果问题需要追溯历史记录或按照特定顺序进行处理，则应选择栈作为数据结构。

一、实验目的1. 理解栈和队列的基本概念、特点及逻辑结构。

2. 掌握栈和队列的存储结构，包括顺序存储结构和链式存储结构。

3. 熟练掌握栈和队列的基本操作，如入栈、出栈、入队、出队等。

4. 分析栈和队列在实际问题中的应用，提高解决实际问题的能力。

二、实验内容1. 栈和队列的定义及特点2. 栈和队列的存储结构3. 栈和队列的基本操作4. 栈和队列的实际应用案例分析三、实验过程1. 栈和队列的定义及特点栈（Stack）是一种后进先出（Last In First Out，LIFO）的数据结构，它只允许在一端进行插入和删除操作。

栈的典型应用场景有函数调用、递归算法等。

队列（Queue）是一种先进先出（First In First Out，FIFO）的数据结构，它允许在两端进行插入和删除操作。

队列的典型应用场景有打印队列、任务队列等。

2. 栈和队列的存储结构（1）顺序存储结构栈和队列的顺序存储结构使用数组来实现。

对于栈，通常使用数组的一端作为栈顶，入栈操作在栈顶进行，出栈操作也在栈顶进行。

对于队列，通常使用数组的一端作为队首，入队操作在队尾进行，出队操作在队首进行。

（2）链式存储结构栈和队列的链式存储结构使用链表来实现。

对于栈，每个元素节点包含数据和指向下一个节点的指针。

入栈操作在链表头部进行，出栈操作在链表头部进行。

对于队列，每个元素节点包含数据和指向下一个节点的指针。

入队操作在链表尾部进行，出队操作在链表头部进行。

3. 栈和队列的基本操作（1）栈的基本操作- 入栈（push）：将元素添加到栈顶。

- 出栈（pop）：从栈顶删除元素。

- 获取栈顶元素（peek）：获取栈顶元素，但不删除它。

- 判断栈空（isEmpty）：判断栈是否为空。

（2）队列的基本操作- 入队（enqueue）：将元素添加到队列尾部。

- 出队（dequeue）：从队列头部删除元素。

- 获取队首元素（peek）：获取队首元素，但不删除它。

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

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

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

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

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

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

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

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

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

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

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

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

（1）源代码：#include#include#define STACK_INIT_SIZE 100#define STACKINCREMENT 10# define OK 1# define ERROR 0typedef char SElemType;/* 顺序栈的存储类型 */typedef struct//define structure SqStack()SElemType *base;SElemType *top;int stacksize;}SqStack;/*构造空顺序栈*/int InitStack(SqStack *S) //InitStack() sub-function{S->base = (SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if (!S->base){printf("分配空间失败!\n");return (ERROR);}S->top = S->base;S->stacksize = STACK_INIT_SIZE;printf("栈初始化成功！\n");return (OK);} //InitStack() end/*取顺序栈顶元素*/int GetTop(SqStack *S, SElemType *e) //GetTop() sub-function{if (S->top == S->base){printf("栈为空!\n"); //if empty SqStackreturn (ERROR);}*e = *(S->top - 1);return (OK);} //GetTop() end/*将元素压⼊顺序栈*/int Push(SqStack *S) //Push() sub-function{SElemType e;if (S->top - S->base>S->stacksize)S->base = (SElemType *)realloc(S->base, (S->stacksize + STACKINCREMENT*sizeof(SElemType)));if (!S->base){printf("存储空间分配失败!\n");return (ERROR);}S->top = S->base + S->stacksize;S->stacksize += STACKINCREMENT;}fflush(stdin);//清除输⼊缓冲区，否则原来的输⼊会默认送给变量x printf("请输⼊要⼊栈的元素的值:");e = getchar();*S->top++ = e;return (OK);} //Push() end/* 将元素弹出顺序栈*/int Pop(SqStack *S, SElemType *e) //Pop() sub-function {if (S->top == S->base){printf("栈为空!\n");return (ERROR);}*e = *--S->top;return (OK);} //Pop() endvoid display(SqStack *s){if (s->top == s->base)printf("栈为空!\n");else{while (s->top != s->base){s->top = s->top - 1;}}printf("\n");}int main(){int choice;SElemType e;SqStack s;do{printf("===============================\n");printf(" 0:退出\n");printf(" 1:初始化栈\n");printf(" 2:⼊栈\n");printf(" 3:出栈\n");printf(" 4:读取栈顶元素\n");printf(" 5:显⽰栈中元素\n");printf("===============================\n");printf("输⼊操作选择代码(0-5):");scanf("%d", &choice);while(choice<0 || choice>5) { printf("输⼊有误，请重新输⼊(0-5):"); scanf("%d", &choice); } switch (choice){case 0:exit(1);case 1:InitStack(&s); break;case 2:printf("2\n"); Push(&s); break;case 3:Pop(&s, &e); printf("出栈元素的值是:%c\n", e); break;case 4:GetTop(&s, &e); printf("栈顶元素的值是:%c\n", e); break;case 5: printf("栈中元素的值是为：\n"); display(&s); break;}} while (choice);return 0;}（3）结果分析2.任务⼀（2）：完成下列程序，该程序实现栈的链式存储结构，构建链栈（栈中的元素依次为China，Japan，France，India，Australia），依次进⾏进栈和出栈操作，判断栈空和栈满操作，返回栈顶元素操作。

实验二栈和队列其应用题目：利用栈的深度优化进行迷宫求解一、需求分析1、进一步理解和掌握课堂上所学各种基本抽象数据类型的逻辑结构、存储结构和操作实现算法，以及它们在程序中的使用方法。

2、掌握软件设计的基本内容和设计方法，并培养学生进行规范化软件设计的能力。

3、掌握使用各种计算机资料和有关参考资料，提高学生进行程序设计的基本能力。

1、使学生进一步理解和掌握课堂上所学各种基本抽象数据类型的逻辑结构、存储结构和操作实现算法，以及它们在程序中的使用方法。

2、使学生掌握软件设计的基本内容和设计方法，并培养学生进行规范化软件设计的能力。

3、使学生掌握使用各种计算机资料和有关参考资料，提高学生进行程序设计的基本能力。

栈和队列其应用目的在于使读者深入了解栈和队列的特性，以便在实际问题背景下灵活运用他们；同时还将巩固对这两种结构的构造方法的掌握，接触较复杂问题的递归算法设计。

（1）：算术表达式转波兰表达式和逆波兰表达式（2）：栈列操作的验证（建栈、入栈、出栈、销毁栈）（3）：判断表达式中括弧是否正确配对（4）：队列元素倒置（5）：判断字符串是否回文（6）：字符串的基本操作（5个基本函数实现）二、概要设计栈和队列及其应用目的在于使读者深入了解栈和队列的特性，以便在实际问题背景下灵活运用他们；同时还将巩固对这两种结构的构造方法的掌握，接触较复杂问题的递归算法设计ADT Stack 的表示和实现#include<malloc.h>#define STACK_INIT_SIZE 30#define STACKINCREMENT 5typedef struct {char * base;char* top;int stacksize;}sqstack;void InitStack(sqstack &s) {s.base=(char *)malloc(STACK_INIT_SIZE*sizeof(char));// if(!s.base) exit(OVERFLOW);s.top=s.base;s.stacksize=STACK_INIT_SIZE;}void push(sqstack &s,char &c) {if(s.top-s.base>=s.stacksize) {s.base=(char *) realloc(s.base,(s.stacksize+STACKINCREMENT)*sizeof(char));// if(!s.base) exit(OVERFLOW);s.top=s.base+s.stacksize;s.stacksize+=STACKINCREMENT;}*s.top++=c;}void pop(sqstack &s,char &c){if(!(s.top==s.base))c=*--s.top;int stackEmpty(sqstack s){if(s.base==s.top) return(1);return(0);}算术表达式转波兰表达式和逆波兰表达式#include <stdio.h>#include <ctype.h>void transform(char *str,int a[][2],int *n) {int i;*n=1;a[0][0]=1;a[0][1]='(';for (i=0;str[i];){if (isdigit(str[i])){a[*n][0]=0;a[*n][1]=0;while (isdigit(str[i])){a[*n][1]=a[*n][1]*10+str[i]-'0';i++;}}else{if (str[i]=='(') a[*n][0]=1;else if (str[i]==')') a[*n][0]=2;else if (str[i]=='*') a[*n][0]=3;else if (str[i]=='/') a[*n][0]=4;else if (str[i]=='+' || str[i]=='-'){if (i==0 || (!isdigit(str[i-1]) && str[i-1]!=')'))a[*n][0]=0;a[*n][1]=0;(*n)++;}if (str[i]=='+') a[*n][0]=5;else a[*n][0]=6;}a[*n][1]=str[i];i++;}(*n)++;}a[*n][0]=2;a[*n][1]=')';(*n)++;}void poland(int a[][2],int n,int p[][2],int *m) { int i;int stack[1000];//转化所用的栈int depth;//栈的深度depth=0;*m=0;for (i=0;i<n;i++){if (a[i][0]==0) stack[depth++]=i;else if (a[i][0]==1) stack[depth++]=i;else if (a[i][0]==2){while (a[stack[depth-1]][0]!=1){depth--;p[*m][0]=a[stack[depth]][0];p[*m][1]=a[stack[depth]][1];(*m)++;}depth--;}else if (a[i][0]==3 || a[i][0]==4){while (a[stack[depth-1]][0]==0 || a[stack[depth-1]][0]==3 || a[stack[depth-1]][0]==4){depth--;p[*m][0]=a[stack[depth]][0];p[*m][1]=a[stack[depth]][1];(*m)++;}stack[depth++]=i;}else if (a[i][0]==5 || a[i][0]==6){while (a[stack[depth-1]][0]!=1){depth--;p[*m][0]=a[stack[depth]][0];p[*m][1]=a[stack[depth]][1];(*m)++;}stack[depth++]=i;}}}void print_poland(int p[][2],int m) {int i;for (i=0;i<m;i++){if (p[i][0]==0) printf("%d",p[i][1]);else printf("%c",p[i][1]);}putchar('\n');}double evaluate(int p[][2],int m) {double stack[1000];//求值所用的栈int depth;//栈的深度int i;depth=0;for (i=0;i<m;i++){if (p[i][0]==0) stack[depth++]=p[i][1];else{double a,b;b=stack[--depth];a=stack[--depth];if (p[i][0]==3) stack[depth++]=a*b;else if (p[i][0]==4) stack[depth++]=a/b;else if (p[i][0]==5) stack[depth++]=a+b;else stack[depth++]=a-b;}}return stack[0];}int a[1000][2];int n;int p[1000][2];int m;main(){printf("5*(8-2)+9\n");transform("5*(8-2)+9",a,&n);poland(a,n,p,&m);print_poland(p,m);printf("The result of the expression is %lf\n",evaluate(p,m)); return;}判断表达式中括弧是否正确配对#include<iostream.h>#include"sqstack.h"void cmp(sqstack &s,char y,int &state1,int &state2){char x;pop(s,x); //cout<<x;if(s.top==s.base) state1=0;if(x==y) state2=1;else if(x!=y) state2=0;}void main() {sqstack s;InitStack(s);int state1=1,state2;int j=0,flag=1;char n,d[15];for(int i=0;i<15&& state1;i++) {cin>>n;if(int(n)==19) { flag=0;break;}else d[i]=n;char c=d[i];switch(c){case'<': push(s,c);break;case'{': push(s,c);break;case'[': push(s,c);break;case'(': push(s,c);break;case'>': cmp(s,'<',state1,state2); break;case'}': cmp(s,'{',state1,state2); break;case')': cmp(s,'(',state1,state2); break;case']': cmp(s,'[',state1,state2); break;}}if(state2==1) cout<<"good match\n";else cout<<"error match\n";}判断字符串是否回文#include<iostream.h>#include<string.h>#include"qnode.h"#include"sqstack.h"int n=0;void scan(linkqueue &q,sqstack &s){ char k;cin>>k;while(k!='#'){enqueue(q,k);push(s,k);cin>>k;n=n+1;}}void ko(linkqueue &q,sqstack &s){ char c,d;int a,i=1;for(n;n>0;n--){a=daqueue(q,c);pop(s,d);if(c!=d) i=0;}if(i==0) cout<<"no"<<endl;else cout<<"yes"<<endl;}void main(){linkqueue q;sqstack s;initqueue(q);initstack(s);scan(q,s);ko(q,s);}字符串的基本操作#include<stdio.h>#include <string.h>void main (){char s[200];char left[200],right[200];int L,i,j;int N,m=0;char cc[2];printf("Please enter the string\n");fgets(s,199,stdin);L = strlen(s);printf("string L=%d\n",L);printf("Please enter N \n");scanf("%d",&N);if (N < L){strncpy(left,s,N); left[N]='\0';strncpy(right, &s[L-N-1],N); right[N]='\0';printf("left: %s\n",left);printf("right: %s\n",right);} else {printf("left,right: %s\n",s);}printf("Please enter begin location m and N\n");scanf("%d %d",&m,&N);if (m>L) m=0;strncpy(right, &s[m],N); right[N]='\0';printf("mid: %s\n",right);printf("enter a letter:\n");scanf("%s",&cc[0]);printf("Locations: ");for (i=0;i<L;i++) if (s[i]==cc[0]) printf("%d ",i+1);printf("\n");for(i=L-1;i>=0;i--) printf("%c",s[i]);printf("\n");for (i=0;i<L;i++) if (s[i] >= 'a' && s[i] <= 'z') s[i]=s[i]-'a'+'A'; printf("%s\n",s);}栈列操作的验证#include <iostream.h>#include <stdlib.h>typedef int priority;typedef int Status;#define TRUE 1;#define FALSE 0;typedef char elemtype;/*栈元素类型,用链表连接*/ typedef struct node{elemtype chdata;struct node *next;}*pnode;/*定义栈*/typedef struct stack{pnode top;int length;}chstack;/*初始化栈*/void InitStack(stack &s){s.top=NULL; s.length=0;}/*栈不为空,出*/Status Push(stack &s,elemtype e){pnode tem;tem=new node;if(!tem)return FALSE;tem->chdata=e;tem->next=s.top;s.top=tem;s.length++;return TRUE;}/*栈不为空,入*/Status Pop(stack &s,elemtype &e){pnode del;e=s.top->chdata;del=s.top;s.top=s.top->next;delete del;s.length--;return TRUE;}/*做第一个'#'*/void Fstack(stack &s){elemtype e;e='#';if(!Push(s,e))exit(0);}/*取得栈顶元素,e带回*/bool Gettop(stack &s,elemtype &e){ if(s.length>=1) {e=s.top->chdata;return true;} return false;}/*定义优先级,返回*/priority chpri(char e){switch (e) {case '(': return 0;case ')': return 0; case '+': return 1;case '-': return 1;case '*': return 2;case '#': return -1;case '/': return 2;}}bool IsOperator(char e){switch (e) {case '(': break;case ')': break;case '+': break;case '-': break;case '*': break;case '/': break;default: return false;} return true;}/*返回a>=b为真*/bool PriCom(char a,char b){int ai;int bi;ai=chpri(a);bi=chpri(b);return (ai>=bi? true:false);}/*不包括空格,主要转换部分*/void conver(char suff[],char chconver[]){ stack s;char *p;char *psuff;char stacktop;char stackout;InitStack(s);Fstack(s);psuff=suff;p=chconver;while(p!='\0') {if(!IsOperator(*p))*psuff++=*p;else {switch (*p){ case'(': Push(s,*p); break;case')': do{ Gettop(s,stackout);*psuff++=stackout;}while(stacktop!='(');Gettop(s,stackout);*psuff++=stackout;break;default: Gettop(s,stacktop);if( PriCom(*p,stacktop ) )Push(s,*p);while( !PriCom(*p,stacktop) ){ Pop(s,stackout);*psuff++=stackout; }Push(s,*p);}//endswitch}//endelsep++; }//endwhilewhile(stackout!='#') {Gettop(s,stackout);*psuff++=stackout;}}三、详细设计任务：可以输入一个任意大小的迷宫数据，用非递归的方法求出一条走出迷宫的路径，并将路径输出；#include <iostream>#include <fstream>#include <conio.h>using namespace std;struct step //定义一个栈{int x,y,n; //x，y表示步子坐标，n表示步数};void change(char **maze,int hang,int lie){for(int i=0;i<hang+2;i++){for(int j=0;j<lie+2;j++)switch(maze[i][j]){case '1': maze[i][j]='#';break;case '+':case '0':case '.': maze[i][j]=' ';break;}}}void step_to_step(char **maze,step *Step,int hang,int lie,int n){ //单步输出for(int k=0;k<=n;k++){for(int i=0;i<hang+2;i++){for(int j=0;j<lie+2;j++){if(Step[k].x==i&&Step[k].y==j)cout<<"."<<" ";else cout<<maze[i][j]<<" ";}cout<<endl;}cout<<"这是第"<<k+1<<"步"<<endl<<endl;getch();}}void out(char **maze,int hang,int lie,int i,int j) //输出所走的路程{if(i==1&&j==1) //若回到原点则表明无出路{cout<<endl;cout<<"************************************************************" <<endl;cout<<"|-------------此迷宫没有出路，所走路线如下图---------------|"<<endl;cout<<"************************************************************" <<endl;}else //否则有出路{cout<<endl;cout<<"************************************************************" <<endl;cout<<"|----------------找到迷宫出路，如图所示--------------------|"<<endl;cout<<"************************************************************" <<endl;}for(i=0;i<hang+2;i++) //输出步子{for(j=0;j<lie+2;j++)cout<<maze[i][j]<<" ";cout<<endl;}}void cure(char **maze,int hang,int lie){int i=1,j=0,n=-1;char Q;step *Step; //定义一个存储路程的栈Step=new step [hang*lie]; //事先给其分配一定的空间，[hang*lie]表示空间足够if(maze[1][1]=='1'){cout<<"555..我进不去!!!"<<endl<<endl;getch();exit(0);}else while(maze[hang][lie]!='.') //由右、下、左、上的顺序判断是否走通{ //'1'表示走不通，'+'表示已经走过但不通又回来的步子，'.'表示已经走过并通了的步子if(maze[i][j+1]!='1'&&maze[i][j+1]!='.'&&maze[i][j+1]!='+'){if(i==1&&j==0){cout<<"入口"<<endl;}elsecout<<"右"<<endl;maze[i][j+1]='.';j=j+1;n++;Step[n].x=i;Step[n].y=j;cout<<i<<","<<j;}else if(maze[i+1][j]!='1'&&maze[i+1][j]!='.'&&maze[i+1][j]!='+'){cout<<"下"<<endl;maze[i+1][j]='.';i=i+1;n++;Step[n].x=i;Step[n].y=j;cout<<i<<","<<j;}else if(maze[i][j-1]!='1'&&maze[i][j-1]!='.'&&maze[i][j-1]!='+'){cout<<"左"<<endl;maze[i][j-1]='.';j=j-1;n++;Step[n].x=i;Step[n].y=j;cout<<i<<","<<j;}else if(maze[i-1][j]!='1'&&maze[i-1][j]!='.'&&maze[i-1][j]!='+') {cout<<"上"<<endl;maze[i-1][j]='.';i=i-1;n++;Step[n].x=i;Step[n].y=j;cout<<i<<","<<j;}else //若走不通则返回上一步{if(i==1&&j==1) //当回到入口时，说明无通路，结束循环break;else{maze[i][j]='+'; //将走不通的点置为+n--;i=Step[n].x; //返回上一个点j=Step[n].y;cout<<"返回"<<endl<<i<<","<<j; //输出返回信息}}if(i==hang&&j==lie)cout<<"(出口)"<<" "<<"(共"<<n+1<<"步"<<")";}out(maze,hang,lie,i,j);cout<<endl<<endl<<endl;cout<<"是否单步输出(y/n):";cin>>Q;cout<<endl<<endl;if(Q=='y'){change(maze,hang,lie);step_to_step(maze,Step,hang,lie,n);}}int main(){char **maze; //定义一个迷宫，空间可动态int hang,lie,i,j;char Q;cout<<"希望手动输入还是文件读入(s:手动输入,w:文件读入):";cin>>Q;cout<<endl<<endl;if(Q=='s'){cout<<"请输入矩阵的行列"<<endl;cout<<"行数:";cin>>hang;cout<<"列数:";cin>>lie;cout<<endl;maze=new char *[hang+2]; //分配连续空间给迷宫for(i=0;i<hang+2;i++)maze[i]=new char [lie+2];cout<<"请输入迷宫，0表示通路，1表示墙"<<endl;for(i=1;i<=hang;i++)for(j=1;j<=lie;j++)cin>>maze[i][j];}else if(Q=='w'){ifstream infile("F:\\migong.txt",ios::in); //可用文件外部输入infile>>hang;infile>>lie;maze=new char *[hang+2]; //分配连续空间给迷宫for(i=0;i<hang+2;i++)maze[i]=new char [lie+2];for(i=1;i<=hang;i++)for(j=1;j<=lie;j++)infile>>maze[i][j];cout<<"文件读取成功！"<<endl;}for(i=0;i<hang+2;i++) maze[i][0]='1';for(i=0;i<lie+2;i++) maze[0][i]='1';for(i=0;i<lie+2;i++) maze[hang+1][i]='1';for(i=0;i<hang+2;i++) maze[i][lie+1]='1';cout<<endl<<endl;cout<<"********************您输入的迷宫为******************************"<<endl;cout<<"行数："<<hang<<" "<<"列数："<<lie;cout<<" "<<"入口："<<"1,1"<<" "<<"出口："<<hang<<","<<lie<<endl;for(i=0;i<hang+2;i++){for(j=0;j<lie+2;j++)cout<<maze[i][j]<<" ";cout<<endl;}cout<<endl<<endl<<"所走的步骤如下:"<<endl;cure(maze,hang,lie);cout<<endl<<endl<<endl; getch();return 0;}四、运行结果图1运行程序，可以选择输入迷宫的方式：有手动输入和文件输入两种方法可供选择。

2007级数据结构实验报告实验名称：实验二栈和队列日期：2008年11月15日1．实验要求实验目的通过选择下面五个题目之一进行实现，掌握如下内容：进一步掌握指针、模板类、异常处理的使用掌握栈的操作的实现方法掌握队列的操作的实现方法学习使用栈解决实际问题的能力学习使用队列解决实际问题的能力实验内容2.1题目1根据栈和队列的抽象数据类型的定义，按要求实现一个栈或一个队列。

要求：1、实现一个共享栈2、实现一个链栈3、实现一个循环队列4、实现一个链队列编写测试main()函数测试线性表的正确性。

2. 程序分析2.1 存储结构存储结构：特殊线性表：栈，队列栈顶 栈底 链栈2.2 关键算法分析共享栈的入栈算法伪码（Push ）： 1．如果栈满，抛出上溢异常。

2．判断是插在栈1还是栈2：2.1如果在栈1插入，则栈顶指针top1加1，在top1处填入元素x ； 2.2如果在栈2插入，则栈顶指针top2加1，在top2处填入元素x 。

共享栈的出栈算法伪码（Pop ）：1. 判断是在栈1删除还是在栈2删除。

2. 若是在栈1删除，则2.1 若栈1为空栈，抛出下溢异常； 2.2 删除并返回栈1的栈顶元素；3. 若是在栈2删除，则3.1 若栈2为空栈，抛出下溢异常； 3.2 删除并返回栈2的栈顶元素。

非空链队列 空链队列共享栈的取栈顶元素算法伪码（GetTop）：1．判断是在栈1取还是栈2取；2．如果在栈1取，则2.1 若栈1不空，返回栈顶元素的值，不删除；2.2 若栈1空，返回0；3．如果在栈2取，则3.1 若栈2不空，返回栈顶元素的值，不删除；3.2 若栈2空，返回0。

链栈的入栈算法伪码（Push）：1．申请一个新的结点，数据域为x；2．将新结点插在栈顶；3．栈顶指针重新指向栈顶元素。

链栈的出栈算法伪码（Pop）：1．如果栈空，抛出下溢异常；2．暂存栈顶元素；3．将栈顶结点摘链；4．删除该结点，返回该元素的值。

链栈的取栈顶元素算法的伪码（GetTop）：1．如果栈非空，返回栈顶元素的值，不删除。

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

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. 熟练掌握循环队列和链队列的基本操作实现算法。

二、实验内容用队列求解迷宫问题[ 问题描述 ]以一个M*N 的长方阵表示迷宫，0和1分别表示迷宫中的通路和墙壁。

设计 一个程序， 对任意设定的迷宫， 求出一条从入口到出口的通路， 或得出没有通路 的结论。

[ 基本要求 ]实现一个以顺序存储结构的队列类型， 然后编写一个求解迷宫的非递归程序。

求得的通 路以三元组（i ，j ，pre ）的形式输出，其中：（i ，j ）指示迷宫中的一个坐标,径中上一个方块在队列中的下标。

三、源代码# include <stdio.h>{1,1,1,1,1,1,1}, {1,0,0,0,0,0,1}, {1,0,1,0,0,1,1},pre 表示本路[ 测试数据 ] 由学生任意指定。

#define M 5// #define N 5// 行数 列数 #define MaxSize 100// int mg[M+2][N+2]={// 队最多元素个数 一个迷宫 , 其四周要加上均为 1 的外框 {1,1,{1,0,1,0,0,1,1}, {1,0,1,0,1,0,1}, {1,0,0,0,0,0,1},{1,1,1,1,1,1,1} }; typedef struct {inti,j;int pre;}Box; typedef struct{Boxdata[MaxSize];int front, rear;}QuType;void mgpath1(int xi,int yi,intxe,int ye) // ->(xe,ye) { void print (QuType qu, int front );搜索路径为：（ xi ，yi ） inti,j,find=0,di; QuType qu;qu.front=qu.rear=-1; //定义顺序队qu.rear++; qu.data[qu.rear].i=xi; //(xi,yi) 进队qu.data[qu.rear].j=yi;qu.data[qu.rear].pre=-1;mg[xi][yi]=-1;while(qu.front!=qu.rear&&!find){qu.front++;i=qu.data[qu.front].i;j=qu.data[qu.front].j; if(i==xe&&j==ye){find=1;print(qu,qu.front);} for(di=0;di<4;di++) switch(di) case0 :i=qu.data[qu.front].i-1;j=qu.data[qu.front].j;break;case1:i=qu.data[qu.front].i;j=qu.data[qu.front].j+1;break;case2:i=qu.data[qu.front].i+1;j=qu.data[qu.front].j+1;break;case3:i=qu.data[qu.front].i;j=qu.data[qu.front].j-1;break;}if(mg[i][j]==0){find=1;qu.rear++;qu.data[qu.rear].i=i; qu.data[qu.rear].j=j;qu.data[qu.rear].pre=qu.front;mg[i][j]=-1;}void print (QuType qu, int front ){int k=front,j,ns=0; printf("\n");do{j=k;k=qu.data[k].pre;qu.data[j].pre=-1;}while (k!=0);printf(" 迷宫路径如下：\n");k=0;while(k<MaxSize){if(qu.data[k].pre==-1){ns++;printf("\t(%d,%d)",qu.data[k].i,qu.data[k].j);if(ns%5==0)printf("\n");}k++;} printf("\n");}void main(){ mgpath1(1,1,M,N);printf(" 迷宫所有路径如下:\n");四、测试结果：文档来源为：从网络收集整理.word 版本可编辑.欢迎下载支持.做实验首先要掌握大量的理论知识，大的困难，这就要需要我们的毅力。