栈和队列的实验报告

栈和队列的实验报告

栈和队列的实验报告

引言：

栈和队列是计算机科学中常用的数据结构，它们在算法设计和程序开发中起着重要的作用。本实验旨在通过实际操作和观察，深入理解栈和队列的概念、特点以及它们在实际应用中的作用。

一、栈的实验

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 表达式求值：通过栈可以实现对表达式的求值，如中缀表达式转换为后缀

表达式，并计算结果。

3.1.2 函数调用：函数调用时，系统会使用栈来保存函数的返回地址、局部变量等信息。

3.1.3 括号匹配：栈可以用于检查括号是否匹配，如编译器的语法分析阶段。

3.2 队列的应用

3.2.1 任务调度：在操作系统中，队列可以用于实现任务的调度，保证任务按照一定的顺序执行。

3.2.2 缓冲区管理：队列可以用于管理缓冲区，如网络数据包的传输、打印任务的排队等。

3.2.3 广度优先搜索：在图算法中，队列可以用于实现广度优先搜索，探索图的连通性。

结论：

通过本次实验，我们对栈和队列的概念、特点以及应用有了更深入的理解。栈和队列作为常用的数据结构，对于算法设计和程序开发具有重要的意义。我们将继续学习和探索更多的数据结构和算法，为解决实际问题提供更有效的解决方案。

栈和队列的实验报告

栈和队列的实验报告 栈和队列的实验报告 引言： 栈和队列是计算机科学中常用的数据结构，它们在算法设计和程序开发中起着重要的作用。本实验旨在通过实际操作和观察，深入理解栈和队列的概念、特点以及它们在实际应用中的作用。 一、栈的实验 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.实验内容 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)的特点。队列的操作主要包括入队和出队。 7.3 数组 数组是一种线性表的数据结构，用连续的存储空间来存储相同 类型的元素。数组的特点是可以通过下标来访问元素。

数据结构栈和队列实验报告

一、实验目的和要求 (1)理解栈和队列的特征以及它们之间的差异，知道在何时使用那种数据结构。 (2)重点掌握在顺序栈上和链栈上实现栈的基本运算算法，注意栈满和栈空的条件。 (3)重点掌握在顺序队上和链队上实现队列的基本运算算法，注意循环队队列满和队空的 条件。 (4)灵便运用栈和队列这两种数据结构解决一些综合应用问题。 二、实验环境和方法 实验方法： (一)综合运用课本所学的知识，用不同的算法实现在不同的程序功能。 (二)结合指导老师的指导，解决程序中的问题，正确解决实际中存在的异常情况，逐步改善功能。 (三)根据实验内容，编译程序。 实验环境： 三、实验内容及过程描述 实验步骤： ①进入Visual C++ 6.0 集成环境。 ②输入自己编好的程序。 ③ 检查一遍已输入的程序是否有错 (包括输入时输错的和编程中的错误)，如发现有 错，及时改正。 ④进行编译和连接。如果在编译和连接过程中发现错误，频幕上会浮现“报错信息”， 根据提示找到出错位置和原因，加以改正。再进行编译，如此反复直到不出错为止。 ⑤ 运行程序并分析运行结果是否合理。在运行是要注意当输入不同的数据时所得结果 是否正确，应运行多次，分别检查在不同情况下结果是否正确。 实验内容：编译以下题目的程序并调试运行。 1)、编写一个程序algo3- 1.cpp，实现顺的各种基本运算，并在此基础上设计一程序并完成如下功能： (1) 初始化栈s； (2) 判断栈s 是否非空；序栈个主

(3)挨次进栈元素a,b,c,d,e； (4)判断栈s 是否非空； (5)输出出栈序列； (6)判断栈s 是否非空； (7)释放栈。图3.1 Proj3_1 工程组成 本工程Proj3_1 的组成结构如图3.1 所示。本工程的模块结构如图3.2 所示。图中方框表示函数，方框中指出函数名，箭头方向表示函数间的调用关系。 图3.2 Proj3_ 1 工程的程序结构图 其中包含如下函数： InitStack(SqStack *&s) //初始化栈S DestroyStack(SqStack *&s) //销毁栈s StackEmpty(SqStack *s) //判断栈空 Push(SqStack *&s,ElemType e) //进栈 Pop(SqStack *&s,ElemType &e) //出栈 GetTop(SqStack *s,ElemType &e) //取栈顶元素 对应的程序如下： //文件名:algo3-1.cpp #include #include #define MaxSize 100 typedef char ElemType; typedef struct {

栈和队列实验报告

栈的顺序表示和实现 一、实验目的 1. 了解栈和队列的特性。 2. 掌握栈的顺序表示和实现。 3. 掌握栈的链式表示和实现。 4. 掌握队列的顺序表示和实现。 5. 掌握队列的链式表示和实现。 6. 掌握栈和队列在实际问题中的应用。 二、实验要求 1.认真阅读和掌握本实验的程序。 2. 上机运行本程序。 3. 保存和打印出程序的运行结果，并结合程序进行分析。 4. 按照对顺序表和单链表的操作需要，重新改写主程序并运行，打印出文件清单和运行结果。 三、实验内容 编写一个程序实现顺序栈的各种基本运算，并在此基础上设计一个主程序完成如下功能： （1）初始化顺序栈。 （2）插入元素。 （3）删除栈顶元素。 （4）取栈顶元素。 （5）遍历顺序栈。 （6）置空顺序栈。 四，解题思路 五、程序清单 #include #include #define MAXNUM 20 #define ElemType int /*定义顺序栈的存储结构*/ typedef struct { ElemType stack[MAXNUM]; int top; }SqStack; /*初始化顺序栈*/ void InitStack(SqStack *p) { if(! p) printf("内存分配失败！"); p->top=-1; } /*入栈*/ void Push(SqStack *p,ElemType x)

{ if(p->toptop=p->top+1; p->stack[p->top]=x; } else printf("Overflow!\n"); } /*出栈*/ ElemType Pop(SqStack *p) { ElemType x; if(p->top>=0) { x=p->stack[p->top]; printf("以前的栈顶数据元素%d已经被删除！\n",p->stack[p->top]); p->top=p->top-1; return(x); } else { printf("Underflow!\n"); return(0); } } /*获取栈顶元素*/ ElemType GetTop(SqStack *p) { ElemType x; if(p->top>=0) { x=p->stack[p->top]; printf("\n栈顶元素喂：%d\n",x); return(x); } else { printf("Underflow!\n"); return(0); } } /*遍历顺序栈*/ void OutStack(SqStack *p) { int i; printf("\n"); if(p->top<0) printf("这是一个空栈！"); printf("\n"); for(i=p->top;i>=0;i--) printf("第%d个数据元素是：%6d\n",i,p->stack[i]); } /*置空顺序栈*/

栈和队列的基本操作 实验报告

邢台学院信科系实验报告 课程名称：《计算机软件基础》 实验类型：设计型(验证型、创新型、综合型、设计型) 实验项目名称：栈和队列的基本操作 学生姓名：专业：教育技术学学号： 指导老师： 实验地点：软件实验室实验学时： 2 学时 一、实验目的和要求 1．掌握栈和队列的顺序存储和链式存储结构 2.掌握栈和队列的特点。 3.掌握栈和队列的基本运算。 二、主要仪器设备或者软件 1.软件：操作系统和C语言系统。 2.硬件：一台微型计算机 三、操作方法与实验步骤 操作方法： 1.确定存储结构后，上机调试实现栈和队列的基本运算。 2.写出栈的入栈和出栈的算法 3. 写出队列的入队和出队算法。 实验步骤： (1)建立顺序栈SeqStack，存放测试数据；建立队列SeqQueue存放出栈数 据； (2)建立InitStack、StackEmpty、StackFull、Pop、Push、GetTop函数用 作顺序栈的基本操作； (3)建立InitQueue、QEmpty、QFull、OutQueue、ReadFront函数用作队列 的基本操作； (4)建立主函数依次按次序对子函数进行操作：InitStack初始化栈->Push 压入数据->InitQueue初始化队列->Pop弹出数据->InQueue存入队列->OutQueue出队列->Push压入栈->Pop弹出数据->free清空栈与队列。 在数据的的输入与数据的输出时提供必要的提示信息。 (5)使用Visual Studio C++ 2005语言环境进行调试，源代码P202-2-1.cpp

通过编译生成目标文件,运行可执行文件：测试通过。 四、讨论或心得 通过对栈的上机，我知道栈其实也还是一种特殊的线性表，了解了栈指针的位置意义，以及栈的入栈、出栈的原理，知道了先入先出的基本规则。队列执行原则初始化时线性表为空，当有用户程序来到时，将该用户程序加入到线性表的末尾进行等待；当计算机系统执行完当前的用户程序后，就从线性表的头部取出一个用户程序执行。

栈与队列 实验报告

栈与队列 一，问题的提出 在这次的实验当中，我选的题目是用队列的知识解决停车场问题。停车场问题的具体描述是：假设停车场是一个可停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由南向北排列（大门在最南端，最先到达的第一辆车停放在车场的最北端），若车场内停满n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车可以开入；当停车场的某辆车要离开时，在它之后进入的车辆必须先退出车场为它让路，待这辆车开出大门之后，其他车再按原来的次序进入车场，每辆停放在车场的车在它离开停车场的时候必须按它停留的时间长短交纳费用。 二,需求分析 总体来说这个程序主要包括三个部分：车辆到达，车辆离开，列表显示。 1,在这个程序当中,要完成这个任务:从键盘上输入车的车编号和而且车的编号是两位数然后通过程序可以得出一个具体的结果,这就需要创建一个栈，用大写A表示,然后再选择是进站还是出站，这就又需要创建一个栈,用大写B表示,这就完成了这个任务的前一半.剩下的就对这个栈的操作了.这个值得注意的问题是注意输入完车的编号的时候，应该通过程序先检查停车场内是否已经满了，还有就是停车场内的车辆如果要是出站的话，应该再为便道上的车辆创建一个栈。还有就是车如果要出站的话，离开停车场的时候必须按照它在停车场停留的时间交纳相应的费用，这个相对来说比较简单。 2,演示程序以用户和计算机的对话方式进行的,即在计算机终端显示”提示信息”之后,由用户在键盘上输入演示程序中规定的运算命令,相应的输入数据和显示结果显示在其后. 3，其中比较重要的操作就是需另设一个栈，临时停放为给要离去的汽车让路而从停车场退出来的汽车，也用顺序存储结构实现。输入数据按到达或离去的时刻有序。栈中每个元素表示一辆汽车，包含两个数据项：汽车的牌照号码和进入停车场的时刻 3,程序执行的命令包括: 1)．编写栈的初始化、进栈和出栈算法。 2)．编写队列的初始化、进队和出队算法。 3)．编写处理车辆到达和车辆离开情况的函数。 4)．编写一个主函数，将上面函数连在一起，构成一个完整的程序。主函数中输入车辆的编号，到达和离开时间。 5)将实验源程序调试并运行，写出输入、输出结果。 4，一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码以及到达或离去的时刻。对每一组输入数据进行操作后的输出信息为：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车辆离去，则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费）。栈以顺序结构实现，队列以链表结构实现

栈和队列实验报告

栈和队列实验报告 引言： 计算机科学中的数据结构是解决问题的关键。栈和队列这两种常用的数据结构，无疑在许多实际应用中起着重要的作用。本篇报告旨在探讨栈和队列的实验结果，并展示它们的实际应用。 一、栈的实验结果及应用 1. 栈的实验结果 在实验中，我们设计了一个基于栈的简单计算器，用于实现基本的四则运算。通过栈的先进后出（Last In First Out）特性，我们成功实现了表达式的逆波兰表示法，并进行了正确的计算。实验结果表明，栈作为一个非常有效的数据结构，可以很好地处理栈内数据的存储和检索。 2. 栈的应用

栈在计算机科学中有许多实际应用。其中之一是程序调用的存储方式。在程序调用过程中，每个函数的返回地址都可以通过栈来保存和恢复。另一个应用是浏览器的历史记录。浏览器中每个访问网页的URL都可以通过栈来存储，以便用户能够追溯他们之前访问的网页。 二、队列的实验结果及应用 1. 队列的实验结果 在实验中，我们模拟了一个简单的出租车调度系统，利用队列的先进先出（First In First Out）特性实现乘客的排队和叫车。实验结果表明，队列作为一个具有高效性和可靠性的数据结构，能够很好地处理排队问题。 2. 队列的应用 队列在许多方面都有应用。一个常见的应用是消息队列。在网络通信中，消息队列可以用于存储和传递信息，确保按照特定的顺序进行处理。另一个应用是操作系统的进程调度。操作系统使

用队列来管理各个进程的执行顺序，以实现公平和高效的资源分配。 三、栈和队列的比较及选择 1. 效率比较 栈和队列在实际应用中的效率取决于具体问题的需求。栈的操 作更简单，仅涉及栈顶元素的插入和删除，因此具有更高的执行 速度。而队列涉及到队头和队尾元素的操作，稍复杂一些。但是，队列在某些问题中的应用更为广泛，例如调度问题和消息传递问题。 2. 如何选择 在选择栈和队列时，需要根据实际问题的性质和需求进行综合 考虑。如果问题需要追溯历史记录或按照特定顺序进行处理，则 应选择栈作为数据结构。如果问题涉及到排队、调度或消息传递等，队列更适合处理。此外，程序设计师还需根据自己的编程经 验和对数据结构的理解来选择合适的数据结构。

栈和队列实验报告总结

栈和队列实验报告 背景 栈（Stack）和队列（Queue）是常用的数据结构，它们在计算机科学中具有广泛的应用。栈和队列虽然在逻辑上都是线性结构，但其特点和操作有很大的差别。 栈是一种后进先出（Last In First Out，LIFO）的数据结构。在栈中，最后插入的元素最先被访问。类似于现实生活中的堆栈，最先放入的物品最后需要取出。栈的主要操作有入栈（Push），将元素放入栈顶；出栈（Pop），将栈顶元素取出；以及获取栈顶元素（Top）等。 队列是一种先进先出（First In First Out，FIFO）的数据结构。在队列中，最先插入的元素最先被访问。类似于现实生活中的排队，最先排队的人最先被服务。队列的主要操作有入队（Enqueue），将元素放入队尾；出队（Dequeue），将队首元素取出；以及获取队首元素（Front）等。 本次实验的目的是加深对栈和队列的理解，并实现相关的操作。 分析 栈的实现 栈的实现可以有多种方式，常见的有基于数组和基于链表。基于数组的栈实现相对简单，可以使用固定大小的数组，通过一个变量来记录栈顶指针。基于链表的栈实现更加灵活，可以动态地分配内存。 基于数组的栈实现主要需要考虑的问题是栈的大小限制和溢出处理。当栈已满时，继续入栈会导致溢出；当栈为空时，进行出栈操作会导致栈错误。因此，需要对入栈和出栈操作进行边界检查。 队列的实现 队列的实现也可以有多种方式，常见的有基于数组和基于链表。基于数组的队列实现可以使用固定大小的数组，通过两个变量来记录队首和队尾的位置。基于链表的队列实现可以使用链表节点表示队列中的元素。

在实现队列的过程中，需要注意队列的大小限制和溢出处理。当队列已满时，继续入队会导致溢出；当队列为空时，进行出队操作会导致队列错误。因此，需要对入队和出队操作进行边界检查。 实验过程 栈的实现 本次实验选择使用基于数组的栈实现。首先定义一个固定大小的数组，以及一个整数变量来记录栈顶元素的位置。 1.初始化栈：将栈顶指针设为-1，表示栈为空。 2.入栈操作：将元素放入栈顶，栈顶指针加一。 3.出栈操作：将栈顶元素取出，栈顶指针减一。 4.获取栈顶元素：返回栈顶指针对应的元素。 在实现入栈和出栈操作时，需要注意边界条件的判断。当栈已满时，继续入栈会导致溢出；当栈为空时，进行出栈操作会导致栈错误。 队列的实现 本次实验选择使用基于链表的队列实现。首先定义一个链表节点的结构体，包含一个数据字段和一个指向下一个节点的指针。 1.初始化队列：将队首和队尾指针都设为NULL，表示队列为空。 2.入队操作：创建一个新的节点，将数据放入节点中，将节点放入队尾。 3.出队操作：将队首元素取出，更新队首指针。 4.获取队首元素：返回队首指针对应的元素。 在实现入队和出队操作时，需要注意边界条件的判断。当队列已满时，继续入队会导致溢出；当队列为空时，进行出队操作会导致队列错误。 结果 栈的测试结果 针对栈的不同操作，进行了如下测试： 1.初始化栈：栈顶指针被正确初始化为-1，表示栈为空。

栈和队列实验报告

实验4 栈和队列基本操作实验 一、实验目的 1 熟悉栈、队列这种特殊线性结构的特性； 2 熟练掌握栈、队列在顺序存储结构和链表存储结构下的基本操作。 二、实验内容与要求 题目1：利用栈结构，编程实现十进制数转换为二进制数。 题目2：构造一个顺序循环队列，编程实现入队、出队操作，运行程序，观察分析运行结果，体会顺序循环队列的特征。(也可以是顺序队列) 要求： 同学们可参考指导书实验4程序、教材算法及其他资料编程实现相关操作。必须完成题目1和题目2。 说明：报告可写在同一文档中。写报告时，按要求写好题目1报告，再按要求写好题目2报告，然后可写题目3报告，总结放在一起即可。 三、 算法分析与设计。 1. (1)入栈示意图：

(2)出栈示意图： 2.循环队列的入队与出队 ... Q.front ② ... ③ Queue.rear=(Queue.rear+1)%MaxSize 循环队列的头指针Q.front 一直指向队首位置，而Q.rear 在循环体中通过语句Queue.rear=(Queue.rear+1)%MaxSize ，实现在队列中的移动，特别是队尾到队首的移动，从而实现了队列的循环，这样可以有效的利用队列的存储空间，更方便查找队列中的元素。在入队、出对的函数中都需要判断队满、对空，满足条件之后才可以继续执行。 四、 运行结果

1.利用栈的存储，十进制转化二进制 2.循环队列的输出顺序，先进先出 3.栈的输出顺序，后进先出 五、实验体会 在做栈的顺序存储实验时，因为栈的最大长度需要提前给定，不方便而且浪费存储空间，如果在栈满之后可不可以根据实际需要增加栈的长度。 通过本次实验认识到栈和循环队列都可以应用于实际生活中，如行编辑程序、迷宫的求解、离散事件的模拟，希望可以把所学的知识应用于实际。多了解一些书中的算法，多思考，才会取得进步。

数据结构用栈和队列创建停车场管理系统实验报告

数据结构用栈和队列创建停车场管理系统实验报告 一、实验背景及目的 随着城市化进程的不断加速，车辆数量急剧增长，停车难成为了城市发展中的一个重要问题。为了解决这一问题，需要建立高效的停车场管理系统。数据结构中的栈和队列是常用的数据结构，可以用来创建停车场管理系统。本次实验旨在通过使用栈和队列来创建一个停车场管理系统，并测试其功能。 二、实验原理及方法 1. 停车场管理系统基本原理 停车场管理系统主要包括三个部分：入口、出口和停车位。当车辆到达入口时，需要检查是否有空余的停车位；如果有，则将其分配一个位置并记录下来；否则，需要让其等待直到有空余位置。当车辆离开时，需要释放该位置并更新记录。 2. 使用栈和队列创建停车场管理系统 （1）使用栈来模拟停车位 由于每个停车位只能容纳一辆汽车，可以使用栈来模拟每个停车位。当有新的汽车进入时，将其压入栈中；当汽车离开时，则将其从栈中弹出。

（2）使用队列来模拟等待区 由于等待区可以容纳多辆汽车，可以使用队列来模拟等待区。当有新的汽车到达时，将其加入队列尾部；当有车位空余时，则从队列头部取出一辆汽车进入停车场。 3. 实验步骤 （1）创建停车场管理系统的数据结构：使用栈和队列分别来模拟停车位和等待区。 （2）实现停车场管理系统的基本操作：包括汽车进入、离开、查询空余停车位等操作。 （3）测试停车场管理系统的功能：模拟多辆汽车进出停车场，检查系统是否能够正确地分配和释放停车位，并且能够正确地记录空余停车位数。 三、实验结果与分析 本次实验使用栈和队列创建了一个简单的停车场管理系统，并测试了其基本功能。在测试过程中，我们模拟了多辆汽车进出停车场，并检查了系统能否正确地分配和释放停车位。实验结果表明，该系统可以正常工作，并且能够正确地记录空余停车位数。 四、实验总结

数据结构实验2——栈和队列实验报告

数据结构实验报告 实验名称：实验2——栈和队列 1 实验目的 通过选择下面五个题目之一进行实现，掌握如下内容： 进一步掌握指针、模板类、异常处理的使用 掌握栈的操作的实现方法 掌握队列的操作的实现方法 学习使用栈解决实际问题的能力 学习使用队列解决实际问题的能力 2 实验内容 利用栈结构实现八皇后问题。 八皇后问题19世纪著名的数学家高斯于1850年提出的。他的问题是：在8*8的棋盘上放置8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列、同一斜线上。请设计算法打印所有可能的摆放方法。 提示： 1、可以使用递归或非递归两种方法实现 2、实现一个关键算法：判断任意两个皇后是否在同一行、同一列和同一斜 线上 2. 程序分析 主程序： #include using namespace std; const int StackSize=8; //皇后的个数 int num=0; template 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 void SeqStack::Push(T x) //入栈操作 { if(top>=StackSize-1) throw"上溢"; top++;//栈顶指针上移 data[top]=x; } template void SeqStack::Pop()//出栈操作 { if(Empty()) throw"下溢"; top--;//栈顶指针下移 } template bool SeqStack::Judgement()//判断该位置是否合适 { for(int i=0;i void SeqStack::PlaceQueen(int row) //放置皇后 { for (int i=0;i

栈和队列实验报告

栈和队列实验报告 实验名称：栈和队列的实验研究 摘要： 本实验旨在通过设计并实现基于栈和队列的算法，探索其在数据结构和算法中的应用。通过实验比较栈和队列的性能差异和适用场景，加深对栈和队列的理解和应用。实验结果表明，栈和队列在不同的问题场景中具有不同的优势和适用性。 关键词：栈、队列、数据结构、算法、应用 一、引言 栈和队列是数据结构中常见且重要的两种数据结构，它们分别以LIFO（Last In First Out，后进先出）和FIFO（First In First Out，先进先出）的方式操作数据，广泛应用于各领域的编程和算法设计中。本实验通过实现栈和队列相关操作的算法，探索它们在实际应用中的效率和优势。 二、实验设计与实现 1.实验设计 本实验采用C++语言来实现栈和队列的操作，并编写相应的算法来解决一些典型问题。实验将比较栈和队列在以下几个方面的性能差异： a)插入操作的性能 b)删除操作的性能 c)查询操作的性能

d)栈和队列的空间占用情况 2.实验步骤 a)设计栈的数据结构和相关操作的算法。 b)设计队列的数据结构和相关操作的算法。 c)分别使用栈和队列来解决一个典型问题，并比较它们的效率。 d)分析实验结果，总结栈和队列的适用场景和优势。 三、实验结果与分析 1.栈的性能比较 在本次实验中，我们使用栈来解决斐波那契数列问题。首先，我们设计了一个栈的数据结构，并实现了如下操作： a) 入栈（push）：将元素添加到栈顶。 b) 出栈（pop）：将栈顶元素移出栈。 c) 查询栈顶元素（top）：返回栈顶元素。 对比使用数组和链表实现栈的性能，我们发现使用链表实现的栈在插入和删除操作上有更好的性能表现，而使用数组实现的栈在查询操作上更高效。这是因为使用链表实现的栈不需要移动大量元素，而使用数组实现的栈可以通过索引直接访问任意位置的元素。 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') //循环 {

栈和队列123

实验报告

填写内容时，可把表格扩大。实验的源程序代码（要有注释）附在表后。题目一程序代码： #include"stdio.h" #include"malloc.h" #define MAXSIZE 100 typedef char elemtype; typedef struct { elemtype data[MAXSIZE]; int top; }SeqStack; typedef struct { elemtype data[MAXSIZE]; int front,rear; }SeqQueue; SeqStack *InitStack(SeqStack *S) { S=(SeqStack *)malloc(sizeof(SeqStack)); S->top=-1; return(S); } int Push(SeqStack *S,int item) { if(S->top==MAXSIZE-1) { printf("Stack overflow\n"); return 0; } else { S->data[++S->top]=item; return 1; } } elemtype Pop(SeqStack *S) { if(S->top==-1)

{ printf("Stack is empty.\n"); return 0; } else { S->top--; return(S->data[S->top+1]); } } SeqQueue *InitQueue(SeqQueue *Q) { Q=(SeqQueue *)malloc(sizeof(SeqQueue)); Q->front=Q->rear=0; return(Q); } int EnQueue(SeqQueue *Q,elemtype item) { if((Q->rear+1)%MAXSIZE==Q->front) { printf("Queue overflow"); return(0); } else { Q->data[Q->rear]=item; Q->rear=(Q->rear+1)%MAXSIZE; return(1); } } elemtype DeQueue(SeqQueue *Q) { elemtype item; if(Q->rear==Q->front) { printf("Queue is emtype"); return(0); } else { item=Q->data[Q->front]; Q->front=(Q->front+1)%MAXSIZE; return(item); }

栈和队列实验报告

西安邮电大学 （计算机学院） 课实验报告 实验名称:栈和队列的应用 专业名称: 班级: 学生: 学号（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的棋盘。 （4）测试数据，包括正确输入及输出结果和含有错误的输入及其输出结果。数据可以任定，只要1<=x,y<=8就可以了。 正确的输出结果为一个二维数组，每个元素的值表示马行走的第几 步，若输入有错，则程序会显示：“输入有误！请重新输入……” 并且要求用户重新输入数据，直至输入正确为止。

栈和队列及其应用实验报告

数据结构实验报告 实验名称：栈和队列及其应用 班级：12级电气本2 学号：2012081227 姓名：赵雪磊 指导教师：梁海丽 日期：2013年9月23日 数学与信息技术学院 一、实验目的

1. 掌握栈和队列的概念。 2．掌握栈和队列的基本操作（插入、删除、取栈顶元素、出队、入队等）。 3．理解栈和队列的顺序、链式存储。 二、实验要求 利用顺序栈将任意一个给定的十进制数转换成二进制、八进制、十六进制数并输出。 三、算法描述 #include "stdafx.h" #include "iomanip.h" void D10to2_8_16(int i,char radix) { char m; if(i>=radix) D10to2_8_16(i/radix,radix); if((m=i%radix+'0')>0x39) m+=7; cout << m; } void main(void) { int nDec; cout << "请输入一个十进制正整数...\n" << "nDec="; cin >> nDec; cout << "转换为二进制是:"; D10to2_8_16(nDec,2); cout << endl; cout << "转换为八进制是:0"; D10to2_8_16(nDec,8); cout << endl; cout << "转换为十六进制是:0x"; D10to2_8_16(nDec,16); cout << endl; } 四、程序清单 #include #include #define N 2 //可以控制进制转换 using namespace std; typedef struct{ int *top; int *base; int stacksize; }stack;

简易计算器栈与队列实验报告

第三组专题二栈与队列实验报告 --------简易计算器 一.（1）问题描述 通过模拟一个简单的计算器来进行+、-、*、/、%、^（乘方）等运算，从键盘上输入一算术表达式（一般为中缀表达式），计算出表达式的值。 （2）基本要求 编写程序，要求可对一实数算术表达式进行简单的数学运算。 可以识别带加减乘除等运算符及括号的中缀表达式。 a. 按照四则运算规则，求表达式的值。一般规则如下： 1）先括号，再括号外。 2）先乘方，再乘除，后加减。 b. 同级运算从左到右顺序执行。 c．如表达式有误，应给出相应的提示信息。 （3）数据结构与算法分析 解决表达式求值问题的方法之一是：第一步将中缀表达式转换为后缀表达式，第二步按后缀表达式求值。解题时可以结合字符串的相关知识。 （4）测试 4.5+5+6.5*1.06=16.39 二.（1）问题分析： 计算机要计算一个式子，不能像我们一样计算，它需要把表达式由中缀表达式转换成后缀表达式，即逆波兰表达式。 将一般中缀表达式转换为逆波兰表达式有如下转换过程： (1)首先构造一个运算符栈，此运算符在栈遵循越往栈顶优先级越高的原则。 (2)读入一个用中缀表示的简单算术表达式，为方便起见,设该简单算术表达式的右端多加上了优先级最低的特殊符号“=”。 (3)从左至右扫描该算术表达式，从第一个字符开始判断，如果该字符是数字，则分析到该数字串的结束并将该数字串直接输出。 (4)如果不是数字，该字符则是运算符，此时需比较优先关系。 做法如下：将该字符与运算符栈顶的运算符的优先关系相比较。如果，该字符优先关系高于此运算符栈顶的运算符，则将该运算符入栈。倘若不是的话，则将栈顶的运算符从栈中弹出，直到栈顶运算符的优先级低于当前运算符，将该字符入栈。 (5)重复上述操作(3)-(4)直至扫描完整个简单算术表达式，确定所有字符都得到正确处理，我们便可以将中缀式表示的简单算术表达式转化为逆波兰表示的简单算术表达式。 （2）问题实现及代码。 1.菜单函数：使用switch函数根据输入的数字选择是否进入计算器

栈和队列的应用的实验报告

栈和队列的应用的实验报告 一、实验目的 1.掌握队列和栈的顺序存储结构和链式存储结构，并初步学会在实际背景下灵 活运用； 2.掌握栈和队列的基本运算在两种存储结构上的实现方法； 3.掌握栈和队列的特点，即FILO 及FIFO的原则。 二、实验内容 1.停车场管理的模拟； 2.迷宫问题的模拟。 三、实验要求 1.“停车场管理的模拟”部分 [问题说明] 设有一个可以停放n辆汽车的狭长停车场，它只有一个大门可以供车辆进出。车辆按到达停车场时间的早晚依次从停车场最里面向大门口处停放（最先到达的第一辆车放在停车场的最里面）。如果停车场已放满n辆车，则后到达的车辆只能在停车场大门外的便道上等待，一旦停车场内有车开走，则排在便道上的第一辆车就进入停车场。停车场内如果有某辆车要开走，在它之后进入停车场的车辆都必须先退出停车场(进入规避所)为它让道，待其开出停车场后，这些车辆再依原来的次序进场。每辆车在离开停车场时，都应根据它在停车场内停留的时间长短交纳停车费。如果停留在便道上的车辆没有进入停车场就要离去，则允许其离去，不收停车费，并且仍然保持在便道上等待车辆的次序。编制一程序模拟停车场的管理。 [基本要求] 程序能输出每辆车到达后的停车位置（停车场/便道），每辆车离开停车场时应交纳的费用。 1.编译并运行： 输入数据：'A'/'D',车牌号，到达时间/离开时间 E---退出。 输入数据：'A'/'D',车牌号，到达时间/离开时间 E---退出。 A,2120,6 <回车> 第2120号车停在停车场的第1号车位上 Press any key to continue...<回车> 输入数据：'A'/'D',车牌号，到达时间/离开时间 E---退出。 A,8761,11<回车> Stack Overflow! 第8761号车停在便道的第1号车位上 Press any key to continue...