实习04_循环队列

实验四循环队列的基本操作实验目的：1、熟悉将算法转换成程序代码的过程。

2、了解单循环队列的逻辑结构特性，熟练掌握循环队列顺序存储结构的C 语言描述方法。

3、熟练掌握循环队列的基本操作：入队、出队等，掌握循环队列的存取特性。

实验内容：1、分别建立包含6个数据元素的循环队列；2、从键盘输入一个数据元素x，进行入队操作；3、获取队头元素的值；4、对循环队列进行出队操作；5、打印循环队列元素和队列长度；6、给出程序及各项操作结果。

实验步骤：#include <stdio.h>#include <malloc.h>#include <stdlib.h>#define MAXSIZE 100 /*队列的最大容量*/typedef int DataType;typedef struct {DataType data[MAXSIZE]; /*队列的存储空间*/int front, rear; /*队头队尾指针*/}SeqQueue,*PSeqQueue;PSeqQueue Init_SeqQueue( ){ /*初始化一新队列，入口参数：无，返回值：新顺序队列指针，null表示失败*/ PSeqQueue Q;Q=( PSeqQueue )malloc(sizeof(SeqQueue));if (Q){Q->front=0;Q->rear=0;printf("置空队列成功！");}return Q;}void Destroy_SeqQueue(PSeqQueue *Q){ /*销毁一队列，入口参数：要销毁的顺序队列指针的地址，返回值：无*/ if (*Q)free(*Q);*Q=NULL;}int Empty_SeqQueue(PSeqQueue Q)/*判断队列是否为空，入口参数：顺序队列，返回值：1表示为空，0表示非空*/{ if (Q && Q->front==Q->rear)return (1);elsereturn (0);}int QueueLength (PSeqQueue Q){学生自己写}//返回Q的元素个数，即队列的长度int In_SeqQueue ( PSeqQueue Q , DataType x)/*入队操作，入口参数：顺序队列和待入队元素x ，返回值：1表示成功，－1表示队满溢出*/{ if ((Q->rear+1)%MAXSIZE==Q->front){ printf("队满");return -1; /*队满不能入队*/}else{ Q->rear=(Q->rear+1) % MAXSIZE;Q->data[Q->rear]=x;return 1; /*入队完成*/}}int Out_SeqQueue (PSeqQueue Q,DataType *x){ /*出队操作，入口参数：顺序队列，返回值：1表示成功，－1表示队空,出队的元素保存到*x */if (Empty_SeqQueue(Q)){printf("队空");return -1; /*队空不能出队*/}else{ Q->front=(Q->front+1) % MAXSIZE;*x=Q->data[Q->front];return 1; /*出队完成*/}}int Front_SeqQueue(PSeqQueue Q ,DataType *x){ /*取队头元素，入口参数：顺序队列和取出元素存放地址，返回值：1表示成功，－1表示队空*/if (Q->front==Q->rear){printf("队空");return -1; /*队空不能得到队头元素*/}else{ *x=Q->data[(Q->front+1)%MAXSIZE];return 1; /*取队头元素操作完成*/}}void display(PSeqQueue S){学生填写}void main(){（由学生填写）}实验用测试数据和相关结果分析：（由学生填写）实验总结：（由学生填写）。

顺序队列（循环队列）概述队列（queue）是⼀种只允许在⼀端进⾏插⼊操作，⽽在另⼀端进⾏删除操作的线性表。

队列是⼀种先进先出（First In First Out）的线性表，简称FIFO。

允许插⼊的⼀端称为队尾，允许删除的⼀端称为队头。

因为已经限制了插⼊和删除的位置，所以对于队列，插⼊和删除时只需要考虑满和空两种状态。

线性表存储结构分为顺序存储和链式存储，这⾥只讨论静态分配的顺序存储结构。

约定为了⽅便起见，我们约定：1、初始化建队列时，令队头指针m_nFront和队尾指针m_nRear等于0，即m_nFront = m_nRear = 0;2、m_nFront指向队头元素的位置，m_nRear指向队尾元素的下⼀位。

关键点1、顺序队列的假上溢现象顺序队列的操作分别在队头和队尾两端进⾏。

在出队时，队头m_nFront和队尾m_nRear的值都是只增加（向队列长度m_nCount）靠近；如果仅通过m_nRear == m_nCount来判断顺序队列是否满队，此时可能存在m_nRear已经指向m_nCount，同时m_nFront > 0（已有元素出队），顺序队列中实际的元素个数远⼩于m_nCount⽽不能做⼊队操作的情况，导致元素出队后的空闲存储空间永远⽆法重⽤，造成假上溢。

如下图：解决⽅法：为克服假上溢，可将顺序队列想象为⼀个⾸尾相接的环状空间，称为循环队列。

在循环队列中出队⼊队时，头尾指针仍向前移动进⾏加1操作，当头尾指针指向m_nCount时，头尾指针加1操作的结果重新指向下界0（加1后对m_nCount做取余数运算）。

2、判断队空和队满想象成循环队列后，当⼊队时，m_nRear向前追赶m_nFront，出队时，m_nFront向前追赶m_nRear，故存在队空和队满时都有m_nFront ==m_nRear的情况，因此⽆法通过m_nFront == m_nRear来判断队空还是队满。

解决⽅法：牺牲存储空间中的⼀个存储单元，使队空和队满的判断条件不同即可，具体的：1）出队时，m_nRear == m_nFront时，表⽰队空，此时不能出队。

实验四队列（循环队列的创建、添加和删除操作）
1．实验目的：掌握循环队列的基本操作，并对其进行简单应用。

2．实验内容：
假设循环队列的最大长度为7，现在依次将以下数据入队列：{7，5，3，9，2，4}；
接着进行3次出队列的操作，再将15、18这两个数据入队列，最后从对头到队尾依次输出队列中的元素。

3．实验步骤：
源代码：
运行结果;
4.总结
在C语言中不能用动态分配的一维数组来实现循环队列。

如果用户的应用程序中设有循环队列，则必须为他设定一个最大队列长度；若用户无法预估队列的最大长度，则宜采用链队列。

循环队列存储结构的c语言描述1.引言1.1 概述在这一部分中，我们将概述循环队列的存储结构和其在C语言中的描述。

循环队列是一种特殊的队列，它通过数组来实现元素的存储和访问。

与普通队列不同的是，循环队列允许在队列头尾进行操作，即当队列满时，新的元素可以覆盖队列头部的元素。

循环队列的存储结构可以用一个数组来表示，其中使用两个指针分别指向队列的头部和尾部。

初始时，这两个指针指向同一个位置，表示队列为空。

当有元素入队时，尾指针向后移动并存储新的元素；当有元素出队时，头指针向后移动并删除队列头部的元素。

循环队列的实现方法有很多种，我们将在后面的部分逐一介绍。

总的来说，循环队列在存储和访问元素时具有高效性和灵活性的优点。

然而，它也有一些缺点，比如需要事先确定队列的最大容量，且存储空间可能会浪费一部分。

在本文的后续部分，我们将详细介绍循环队列的定义和特点，包括队列空和队列满的条件；同时，我们还将介绍一些常用的实现方法，包括使用固定长度的数组以及动态分配内存空间的方式。

最后，我们将给出C语言描述循环队列的代码示例，以帮助读者更好地理解和实践该数据结构。

通过掌握循环队列的基本概念和相应的C语言实现，读者将能够应用循环队列解决实际问题，并在程序设计中发挥其优势。

接下来，让我们进入正文部分，详细了解循环队列的定义和特点。

文章结构部分的内容可以按照以下方式来编写：1.2 文章结构本文将按照如下结构进行叙述循环队列存储结构的C语言描述：1. 引言：首先介绍循环队列这种数据结构的背景和作用，以及本文将要讨论的问题。

2. 正文：主要呈现循环队列的定义和特点，以及不同的实现方法。

在循环队列的定义和特点部分，将介绍什么是循环队列以及其与一般队列的区别。

在循环队列的实现方法部分，将讨论如何用C语言来实现循环队列，包括如何定义循环队列的结构体和相关操作函数的实现。

3. 结论：对循环队列的优缺点进行总结，以及给出用C语言描述循环队列的代码示例。

循环队列及链队列的基本操作1. 循环队列的基本概念和原理循环队列是一种常见的数据结构，它具有队列的特点，即先进先出（FIFO）。

与普通队列相比，循环队列的特点在于它可以充分利用数组的空间，解决了普通队列在出队操作时需要频繁搬移数据的问题。

循环队列的基本原理是使用环形数组来实现队列的存储和操作，通过头指针和尾指针的移动，实现队列的入队和出队操作。

2. 循环队列的基本操作2.1 入队操作：将元素插入队列的尾部，并更新尾指针的位置。

2.2 出队操作：从队列的头部取出元素，并更新头指针的位置。

2.3 判空操作：当头指针和尾指针重合时，队列为空。

2.4 判满操作：当尾指针的下一个位置与头指针重合时，队列为满。

3. 链队列的基本概念和原理链队列是另一种常见的队列实现方式，与循环队列不同的是，链队列使用链表来存储队列元素。

链队列的基本原理是使用链表的头节点和尾节点来实现队列的操作，通过指针的移动，实现入队和出队操作。

4. 链队列的基本操作4.1 入队操作：将元素插入队列的尾部，并更新尾节点的位置。

4.2 出队操作：从队列的头部取出元素，并更新头节点的位置。

4.3 判空操作：当头节点和尾节点指向同一个节点时，队列为空。

4.4 遍历操作：通过指针的遍历，可以获取队列中的所有元素。

5. 总结和回顾通过对循环队列和链队列的基本概念、原理和操作进行分析，我们可以看出它们都是用于实现队列功能的数据结构，但在不同的场景下有着不同的优势和应用。

循环队列适合于对空间有限且需要频繁进行入队和出队操作的场景，而链队列适合于对空间要求宽松、对操作有一定顺序要求的场景。

6. 个人观点和理解在实际编程中，循环队列和链队列都有着各自的优点和局限性，需要根据具体的场景和需求来选择合适的队列实现方式。

在使用循环队列时，需要注意头尾指针的移动，避免产生死循环和队列溢出的问题；而在使用链队列时，需要考虑对节点的动态分配和释放，避免产生内存泄漏和指针错乱的问题。

循环队列实验报告心得与体会循环队列是数据结构中一个非常经典的概念，相对于其他队列结构，循环队列可以优化存储空间的使用，减少空间的浪费。

循环队列的操作也比较高效，能够快速执行入队和出队操作。

本次实验，我们对循环队列结构进行了深入的了解与实践，更深刻地认识到了数据结构的重要性。

在实验中，我们首先对循环队列的基本概念进行了学习，通过查阅相关资料和教材，我们了解到循环队列是一种环形的特殊队列，其队尾指针在达到数组的末尾时，再从数组的第一个位置开始存储数据，如此循环下去。

这样一来，就可以充分利用数组中的元素，减少不必要的空间浪费，提高队列结构的空间利用率。

在深入了解循环队列的概念之后，我们开始实现循环队列的基本操作，包括入队、出队、判空、判满等。

通过实现这些基础操作，我们更加熟悉了循环队列的内部结构和操作流程，同时也掌握了程序设计中的一些基本思路和技巧。

在实验过程中，我们还注意到了循环队列一些常见的问题和局限性。

当队列元素数量达到数组大小时，会出现队列满的情况，此时需要进行特殊处理。

由于循环队列是基于数组实现的，所以其大小是固定的，不能动态调整，这也是循环队列的一个缺陷。

在实验结束后，我们对循环队列的性能进行了一些简单分析。

通过测试，我们发现循环队列在入队和出队操作的时间复杂度都是O（1），即不受元素数量的影响，具有较高的效率。

这进一步证明了循环队列是一种高效的数据结构。

本次实验让我们深入了解了循环队列的内部结构和基本操作，也发现了循环队列存在的问题和局限性。

通过这次实验的实践，我们进一步理解了数据结构的重要性，同时也锻炼了自己的程序设计能力和思维能力。

除了实现循环队列的基本操作，我们还对循环队列进行了扩展，添加了一些实用的操作，比如获取队列长度、获取队首和队尾元素等。

这些操作虽然不是必要的，但是在实际的应用中却非常实用，可以方便我们处理队列中的元素。

我们在实验中还掌握了一些编程技巧和调试工具，来提高程序的效率和可靠性。

数据结构实验4循环队列的实现和运算循环队列是一种特殊的队列，它的特点是可以循环利用已经出队的元
素所占用的空间。

循环队列采用一维数组来实现，通常需要两个指针（称
为队头指针front和队尾指针rear）。

循环队列的基本操作包括初始化、判空、判满、入队、出队、获取队
头元素等。

1. 初始化：循环队列的初始化很简单，只需将队头指针front和队
尾指针rear都置为0即可。

2. 判空：当队头指针front和队尾指针rear相等时，队列为空。

3. 判满：当队尾指针rear加1后等于队头指针front时，队列为满。

4. 入队操作：在插入元素之前，需要判断队列是否已满。

如果队列
为满，则无法插入新的元素；否则，在rear指针的位置插入新的元素，
并将rear指针往后移动一位。

5. 出队操作：在删除元素之前，需要判断队列是否为空。

如果队列
为空，则无法删除元素；否则，在front指针的位置删除元素，并将
front指针往后移动一位。

6. 获取队头元素：获取队列的队头元素很简单，只需返回front指
针位置的元素即可。

循环队列的实现比较简洁高效，主要是通过取模运算来实现队列指针
的循环移动。

当rear指针到达数组的最后一个位置时，再插入新的元素时，需要将rear指针指向数组的第一个位置；当front指针在数组的最
后一个位置上时，再删除元素时，需要将front指针指向数组的第一个位置。

通过循环队列的实现和运算，可以高效地进行队列的操作，从而提高算法的执行效率。

在实际应用中，循环队列常被用于实现缓冲区、进程调度等场景。

浙江大学城市学院实验报告课程名称数据结构基础实验项目名称实验八队列（循环队列）的表示和实现学生姓名专业班级学号实验成绩指导老师（签名）日期04 28一.实验目的和要求1、掌握队列的存储结构及基本操作。

2、掌握循环队列的设置及循环队列的各种基本操作的实现。

3、通过具体的应用实例，进一步熟悉和掌握队列的实际应用。

二.实验内容1、建立头文件test8.h，定义顺序存储的循环队列存储结构，并编写循环队列的各种基本操作实现函数。

同时建立一个验证操作实现的主函数文件test8.cpp，编译并调试程序，直到正确运行。

说明：队列的基本操作可包括：①void InitQueue (Queue &Q); //构造一个空队列Q②int EmptyQueue (Queue Q);//判断队列Q是否为空，若空返回1，否则返回0③void EnQueue (Queue &Q, ElemType item); //元素item 进队列Q④ElemType OutQueue (Queue &Q); //队头元素出队列Q，并返回其值⑤ElemType PeekQueue (Queue Q); //返回队头元素值⑥void ClearQueue (Queue &Q); //清空队列2、应用（选做部分）：编写程序，实现舞伴问题：假设在周末舞会上，男士们和女士们进入舞厅时，各自排成一队，跳舞开始时，依次从男队和女队的队头上各出一人配成舞伴，若两队初始人数不相同，则较长的那一队中未配对者等待下一轮舞曲。

现要求设计一个函数void partner()，模拟上述舞伴配对问题。

基本要求:1)由键盘输入数据，每对数据包括姓名和性别；2)输出结果包括配成舞伴的女士和男士的姓名，以及未配对者的队伍名称和队头者的姓名；3)要求利用test8.h中已实现的顺序循环队列的基本操作函数来实现。

函数void partner()添加到文件test8.cpp中，在主函数中进行调用测试。

循环队列的概念
循环队列是一种特殊的队列数据结构，它具有固定大小的缓冲区，可以在其中存储元素，并支持在队列前端和后端插入和删除元素。

与普通队列不同的是，循环队列允许在缓冲区的末尾和开头之间进行循环操作，从而实现更高效的内存利用。

循环队列的实现方法通常使用一个数组来表示缓冲区，并使用两个指针来指示队列的头部和尾部。

当一个元素被添加到队列中时，尾指针会向前移动一位，并将该元素存储到数组中相应的位置上。

当一个元素从队列中被删除时，头指针会向前移动一位，并从数组中相应位置上取出该元素。

由于循环队列具有固定大小的缓冲区，因此在插入新元素时可能会出现“溢出”的情况。

为了避免这种情况发生，循环队列需要使用一些技巧来判断当前是否还有空间可以存储新元素。

例如，在插入新元素时可以检查头指针和尾指针之间是否还有空闲位置，如果没有则说明缓冲区已满。

另外，在实际应用中通常需要考虑多线程环境下的并发操作问题。

为了保证多线程操作的正确性，循环队列需要使用一些同步机制来避免竞争条件的发生。

例如，在插入和删除元素时可以使用互斥锁或读写
锁来保证同一时刻只有一个线程可以访问队列。

总之，循环队列是一种非常常用的数据结构，它可以在内存中高效地存储和管理元素，并支持快速插入和删除操作。

在实际应用中，循环队列通常被用于缓存数据、消息传递、任务调度等场景中。