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

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

2、会用栈和队列解决简单的实际问题。

二、实验内容（可任选或全做）题目一、试写一个算法，判断依次读入的一个以@为结束符的字符序列，是否为回文。

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

相关常量及结构定义：# define STACK_INIT_SIZE 100# define STACKINCREMENT 10# define OK 1# define ERROR 0typedef 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)题目二、编程模拟队列的管理，主要包括：出队列、入队、统计队列的长度、查找队列某个元素e、及输出队列中元素。

[实现提示]：参考教材循环队列的有关算法，其中后两个算法参考顺序表的实现。

题目三、RailsDescriptionThere is a famous railway station in PopPush City. Country there is incredibly hilly. The station was built in last century. Unfortunately, funds were extremely limited thattime. It was possible to establish only a surface track. Moreover, it turned out that the station could be only a dead-end one (see picture) and due to lack of available space it could have only one track.The local tradition is that every train arriving from the direction A continues in the direction B with coaches reorganized in some way. Assume that the train arriving from the direction A has N <= 1000 coaches numbered in increasing order 1, 2, ..., N. The chief for train reorganizations must know whether it is possible to marshal coaches continuing in the direction B so that their order will be a1, a2, ..., aN. Help him and write a program that decides whether it is possible to get the required order of coaches. You can assume that single coaches can be disconnected from the train before they enter the station and that they can move themselves until they are on the track in the direction B. You can also suppose that at any time there can be located as many coaches as necessary in the station. But once a coach has entered the station it cannot return to the track in the direction A and also once it has left the station in the direction B it cannot return back to the station.InputThe input consists of blocks of lines. Each block except the last describes one train and possibly more requirements for its reorganization. In the first line of the block there is the integer N described above. In each of the next lines of the block there is a permutation of 1, 2, ..., N. The last line of the block contains just 0.The last block consists of just one line containing 0.OutputThe output contains the lines corresponding to the lines with permutations in the input.A line of the output contains Yes if it is possible to marshal the coaches in the order required on the corresponding line of the input. Otherwise it contains No. In addition,there is one empty line after the lines corresponding to one block of the input. There is no line in the output corresponding to the last ``null'' block of the input. Sample Input51 2 3 4 55 4 1 2 366 5 4 3 2 1Sample OutputYesNoYes题目四、Sliding WindowDescriptionAn array of size n≤ 106 is given to you. There is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves rightwards by one position. Following is an example:The array is [1 3 -1 -3 5 3 6 7], and k is 3.Window position Minimum value Maximum value[1 3 -1] -3 5 3 6 7 -131 [3 -1 -3] 5 3 6 7 -331 3 [-1 -3 5] 3 6 7 -351 3 -1 [-3 5 3] 6 7 -351 3 -1 -3 [5 3 6] 7 361 3 -1 -3 5 [3 6 7]37Your task is to determine the maximum and minimum values in the sliding window at each position.InputThe input consists of two lines. The first line contains two integers n and k which are the lengths of the array and the sliding window. There are n integers in the second line.OutputThere are two lines in the output. The first line gives the minimum values in the window at each position, from left to right, respectively. The second line gives the maximum values.Sample Input8 31 3 -1 -3 5 3 6 7Sample Output-1 -3 -3 -3 3 33 3 5 5 6 7题目五（选作考查串知识）DNA Evolution【Description】Evolution is a seemingly random process which works in a way which resembles certain approaches we use to get approximate solutions to hard combinatorial problems. You are now to do something completely different.Given a DNA string S from the alphabet {A,C,G,T}, find the minimal number of copy operations needed to create another string T. You may reverse the strings you copy, and copy both from S and the pieces of your partial T. You may put these pieces together at any time. You may only copy contiguous parts of your partial T, and all copied strings must be used in your final T.Example: From S= “ACTG” create T= “GTACTAATAAT”1.Get GT......... by copying and reversing "TG" from S.2.Get GT AC... by copying "AC" from S.3.Get GTAC TA….. by copying "TA" from the partial T.4.Get GTACTA AT by copying and reversing "TA" from the partial T.5.Get GTACTAAT AAT by copying "AAT" from the partial T.【Input】The first line of input gives a single integer, 1 ≤k≤10, the number of test cases. Then follow, for each test case, a line with the string S , length of S is less then 19, and a line with the string T , length of T is less then 19.【Output】Output for each test case the number of copy operations needed to create T from S, or "impossible" if it cannot be done.【Sample Input】4ACGTTGCAACACGTTCGATCGAAAAAAAAAAAAAAAAAAAA【Sample output】1impossible46题目六（选作考查数组知识）Magic Squares描述Following the success of the magic cube, Mr. Rubik invented its planar version, called magic squares. This is a sheet composed of 8 equal-sized squares:1 2 3 48 7 6 5In this task we consider the version where each square has a different color. Colors are denoted by the first 8 positive integers. A sheet configuration is given by the sequence of colors obtained by reading the colors of the squares starting at the upper left corner and going in clockwise direction. For instance, the configuration of Figure 3 is given by the sequence (1,2,3,4,5,6,7,8). This configuration is the initial configuration.Three basic transformations, identified by the letters `A', `B' and `C', can be applied to a sheet:∙'A': exchange the top and bottom row,∙'B': single right circular shifting of the rectangle,∙'C': single clockwise rotation of the middle four squares.Below is a demonstration of applying the transformations to the initial squares given above:A:8 7 6 51 2 3 4B:4 1 2 35 8 7 6C:1 72 48 6 3 5All possible configurations are available using the three basic transformations.You are to write a program that computes a minimal sequence of basic transformations that transforms the initial configuration above to a specific target configuration.输入A single line with eight space-separated integers (a permutation of (1..8)) that are the target configuration.输出样例输入2 6 8 4 5 73 1样例输出7BCABCCB三、实验步骤㈠、数据结构与核心算法的设计描述㈡、函数调用及主函数设计（可用函数的调用关系图说明）㈢程序调试及运行结果分析㈣实验总结四、主要算法流程图及程序清单1、主要算法流程图：2、程序清单（程序过长，可附主要部分）//int IsReverse(){ ….while( (e=getchar())!='@'){e 依次入栈、入队 //push(S,e);EnQueue(Q,e);……..}While(!StackEmpty(S)) { pop(S,a);DeQueue(Q,b);If(a!=b) return 0;}return 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）。

数据结构栈和队列实验报告数据结构栈和队列实验报告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)的特点。

西安邮电大学（计算机学院）课实验报告实验名称:栈和队列的应用专业名称:班级:学生:学号（8位）:指导教师: 实验时间:一. 实验目的及实验环境1.实验目的（1）熟练使用栈和队列解决实际问题；（2）了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；（3）初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；（4）提高综合运用所学的理论知识和方法独立分析和解决问题的能力；2.实验环境Dev-C++二. 实验容设计一个国际象棋的马踏棋盘的演示过程。

基本要求:将马随机放在国际象棋的8*8棋盘Board[8][8]的某个方格中，马按走棋规则进行移动，要求每个方格只进行一次，走遍整个棋盘的全部64个方格。

编制非递归程序，求出马的行走路线，并按求出的行走路线，将数字1，2，…，64依次填入一个8*8的方阵，输出之。

测试数据：可自行制定一个马的初始位置（i，j），0<=I,j<=7。

三．方案设计第1步：实现提示一般来说，当马位于位置（i,j）时，可以走到下列8个位置之一：（i-2，j+1），(i-1，j+2)（i+1，j+2），(i+2，j+1)（i+2，j-1），(i+1，j-2)（i-1，j-2），(i-2，j-1)但是，如果（i，j）靠近棋盘的边缘，上述有些位置可能要超出棋盘位置，成为不允许的位置。

8个可能位置可以用一位数组HTry1[0…7]和HTry2[0…7]来表示：0 1 2 3 4 5 6 7位于（i，j）的马可以走到新位置是在棋盘围的（i+HTry1[h],j+HTry2[h]），其中h=0…7。

第2步：需求分析（1）输入的形式和输入值的围：输入马的初始行坐标X和列坐标Y，X和Y的围都是[1,8]。

（2）输出形式：以数组下表的形式输入，i为行标，j为列标，用空格符号隔开。

以棋盘形式输出，每一格打印马走的步数，这种方式比较直观（3）程序所能达到的功能：让马从任意起点出发都能够遍历整个8*8的棋盘。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

实验作业二：栈（顺序栈）和队列（循环队列）1. 将编号为0和1的两个栈存放于一个数组空间V[m]中，栈底分别处于数组的两端。

当第0号栈的栈顶指针top[0]等于-1时该栈为空，当第1号栈的栈顶指针top[1]等于m时该栈为空。

两个栈均从两端向中间增长。

当向第0号栈插入一个新元素时，使top[0]增1得到新的栈顶位置，当向第1号栈插入一个新元素时，使top[1]减1得到新的栈顶位置。

当top[0]+1 == top[1]时或top[0] == top[1]-1时，栈空间满，此时不能再向任一栈加入新的元素。

试定义这种双栈(Double Stack)结构的类定义，并实现判栈空、判栈满、插入、删除算法。

2. 求fibonacci数列算法，并比较。

（递归+非递归）（非递归方法可查阅其他资料）编写实习报告要求：一、需求分析二、概要设计1.抽象数据类型2.算法三、详细设计程序代码（注释）四、调试分析调试过程中所做的工作，时间复杂度等五、测试结果输入数据和输出数据示例六、说明（如果有）编程语言：C语言或C++语言实习报告提交方式：下次上机前，将实习报告(.doc)和源程序(.cpp)压缩成一个rar 文件，文件名称为学号_班级_姓名_第几次作业。

例如：3010216155_六班_张三_第二次作业.rar。

实习报告作为本课程的平时成绩。

抄袭、雷同，双方均为0分。

第一题：一、需求分析程序要求建立一个共享栈，分配一个存储空间，两个栈分别位于两头。

并实现对两个栈的插入，删除，和判断栈满和栈空。

栈的位置不同，所以要求对不同栈的插入和删除采用不同的算法。

二、概要设计1.抽象数据类型typedef struct {int *base;int *top;int stacksize;}stack;2.算法1.建立栈。

int instack(stack &s,stack &w,int length){s.base=(int *)malloc(length*sizeof(length));w.base=s.base+length;if(!s.base||!w.base) return 0;else{s.top=s.base;w.top=w.base;s.stacksize=length;w.stacksize=length;}return 1;}2.判断栈空。

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