实验八 队列(循环队列)的表示和实现

实验目的：通过本次实验，掌握循环队列的基本概念和操作方法，了解其在实际应用中的优势，并能够熟练运用循环队列解决实际问题。

实验环境：操作系统：Windows 10编程语言：C语言开发环境：Visual Studio实验内容：1. 循环队列的定义及初始化2. 循环队列的入队操作3. 循环队列的出队操作4. 循环队列的判空操作5. 循环队列的判满操作6. 循环队列的遍历操作7. 循环队列的应用实例实验步骤：一、循环队列的定义及初始化1. 定义循环队列的数据结构：```c#define MAX_SIZE 100 // 定义队列的最大容量typedef struct {int data[MAX_SIZE]; // 存储队列元素的数组int front; // 队头指针int rear; // 队尾指针} CircleQueue;```2. 初始化循环队列：```cvoid InitQueue(CircleQueue q) {q->front = q->rear = 0; // 初始化队头和队尾指针}```二、循环队列的入队操作1. 判断队列是否已满：```cint IsFull(CircleQueue q) {return (q->rear + 1) % MAX_SIZE == q->front;}```2. 入队操作：```cint EnQueue(CircleQueue q, int e) {if (IsFull(q)) {return 0; // 队列已满，无法入队}q->data[q->rear] = e; // 将元素e入队q->rear = (q->rear + 1) % MAX_SIZE; // 更新队尾指针return 1; // 入队成功}```三、循环队列的出队操作1. 判断队列是否为空：```cint IsEmpty(CircleQueue q) {return q->front == q->rear;}```2. 出队操作：```cint DeQueue(CircleQueue q, int e) {if (IsEmpty(q)) {return 0; // 队列为空，无法出队}e = q->data[q->front]; // 将队头元素出队q->front = (q->front + 1) % MAX_SIZE; // 更新队头指针 return 1; // 出队成功}```四、循环队列的判空操作1. 判断队列是否为空：```cint IsEmpty(CircleQueue q) {return q->front == q->rear;}```五、循环队列的判满操作1. 判断队列是否已满：```cint IsFull(CircleQueue q) {return (q->rear + 1) % MAX_SIZE == q->front; }```六、循环队列的遍历操作1. 遍历循环队列：```cvoid TraverseQueue(CircleQueue q) {if (IsEmpty(q)) {printf("队列为空，无法遍历。

数据结构实验报告姓名：方钢学号：20105567 专业：电子商务班级：10—1班指导教师：实验时间：实验地点：新区实验楼四楼（实验题目）循环队列1.实验内容和要求1.1实验要求①本次实验中，队列使用顺序结构循环队列；②结构定义和运算实验放入库文件“seqQueue.h”中；③各运算和变量命名直观易懂，并有相应的注释。

1.2实验内容<1>初始化一个队列。

<2>判断是否队空。

<3>判断是否队满。

<4>入队<5>出队<6>取队头元素<7>求当前队列中元素个数<8>编写算法实现①初始化空循环队列；②当键盘输入奇数时，此奇数入队；③当键盘输入偶数时，队头出队；④当键盘输入0时，算法退出；⑤每当键盘输入后，输出当前队列中的所有元素2.实验目的①掌握队列的基本概念。

②掌握循环队列的建立、入队和出队等方法。

③根据具体问题的需要，设计出合理的表示数据的结构，并设计相关算法。

3.算法设计<1>初始化一个队列。

<2>判断是否队空。

<3>判断是否队满。

<4>入队<5>出队<6>取队头元素<7>求当前队列中元素个数算法：int main(int argc, char* argv[]){seqQueue L;elementType x;int k,m,n;initQueue(&L);// 初始化顺序循环队列if(queueEmpty(L))// 判断空队列cout<<"当前队列空！"<<endl;elsecout<<"当前队列非空！"<<endl;cout<<"请输入入队元素的最大元素x=";cin>>x;if(x<MaxLen){while(x!=0){enQueue(&L, x);//循环入队for(m=x-1;m>=0;m--){break;}x=m;}cout<<"当前队列中元素（从头至尾）:"; int i=L.front+1;while(i<=L.rear){cout<<L.data[i]<<", ";i++;}cout<<endl;cout<<"队列中元素个数为:";n=(L.rear-L.front+MaxLen)%MaxLen;cout<<n;cout<<endl;queueFront(L, x); // 取队头元素 cout<<"当前队头元素: x="<<x<<endl;outQueue(&L); // 出队（删除）cout<<"出队后队列中元素（从头至尾）:";i=L.front+1;while(i<=L.rear){cout<<L.data[i]<<", ";i++;}cout<<endl;}elsecout<<"I'm sorry<<endl";return 0;}截图：<8>编写算法实现①初始化空循环队列；②当键盘输入奇数时，此奇数入队；③当键盘输入偶数时，队头出队；④当键盘输入0时，算法退出；⑤每当键盘输入后，输出当前队列中的所有元素算法：int main(int argc, char* argv[]){seqQueue L;elementType x;initQueue(&L);// 初始化顺序循环队列if(queueEmpty(L))// 判断空队列cout<<"当前队列空！"<<endl;elsecout<<"当前队列非空！"<<endl;cout<<"请输入入队元素:"<<endl;cin>>x;while(x!=0){if(x%2!=0){enQueue(&L, x);}elseoutQueue(&L);cout<<"当前队列中元素（从头至尾）:"; int i=L.front+1;while(i<=L.rear){cout<<L.data[i]<<", ";i++;}cout<<endl;cin>>x;}while(x==0){cout<<"退出程序"<<endl;break;}return 0;}截图：4.总结和心得通过对循环队列的上机实验明白了循环队列的一些功能，对循环队列有了更深刻的了解。

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

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

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

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

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

2、选做：编写程序，实现舞伴问题。

假设在周末舞会上，男士们和女士们进入舞厅时，各自排成一队，跳舞开始时，依次从男队和女队的队头上各出一人配成舞伴，若两队初始人数不相同，则较长的那一队中未配对者等待下一轮舞曲。

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

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

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

3、填写实验报告，实验报告文件取名为report8.doc。

4、上传实验报告文件report8.doc、源程序文件test3_2.cpp及SeqQueue.h 到Ftp服务器上自己的文件夹下。

三. 函数的功能说明及算法思路抽象数据类型：ADT SET isData：一个队列Q，假定用标示符Queue表示队列的存储类型Operation：void InitQueue(Queue& Q)//初始化队列为空并带有动态存储空间分配int EmptyQueue(Queue Q)//判断队列是否为空,空返回1,否则返回0void EnQueue(Queue& Q , ElemType item )//向队列插入元素，若队列已满重新分配更大的存储空间ElemType OutQueue(Queue& Q)//从队列中删除元素并返回ElemType PeekQueue(Queue Q)//读取队首元素，不改变队列状态void ClearQueue(Queue &Q)//清除队列为空，并释放动态存储空间void partner(Queue a,Queue b)//实现解决舞伴问题end QUEUE存储结构：typedef char ElemType;struct Queue{ //动态分配ElemType *queue;int front,rear;//队头指针,队尾指针int MaxSize;//队列最大存储数};struct Dancer{ //存储舞者的姓名和性别char name;char sex;};解决舞伴问题分析：void partner(Queue a,Queue b)建立两个队列a和b，a放女生，b放男生。

队列的理解和实现（⼀）-----循环队列（java实现）什么是队列我们都知道栈是先进后出的⼀种线性表，与之相反的是，队列是⼀种先进先出的线性表。

它只允许在表的⼀端进⾏插⼊，⽽在另⼀端进⾏删除。

举个例⼦来说，在⽣活中我们买东西需要进⾏排队，最先排队的可以最早的离开队伍，⽽排在最后⾯的需要最后离开队伍。

在队列当中，允许插⼊的⼀端称为队尾，⽽允许删除的⼀段称为队头。

和栈与线性表类似，队列也分为顺序队列和链队列。

普通队列所存在的问题在使⽤数组实现的队列中，⼊队的操作就是将尾指针rear右移⼀个单位（加⼀），然后将元素值赋值给rear单位。

出队时，则是头指针front 后移⼀个单位（加⼀）。

当进⾏了⼀定数量的⼊队和出队操作后，可能会出现这样的情况：尾指针rear已指到数组的最后有⼀个元素，即rear=maxSize-1，此时若再数组的前⾯部分可能还有很多闲置空间，即这种溢出并⾮是真的没有可⽤的存储空间，故称这种溢出现象为“假溢出”。

显然，必须要解决这⼀块假溢出的问题，否则顺序队列就没有太多使⽤价值。

解决假溢出⼀般情况下有两个⽅式:１．在普通队列中设置元素实际个数变量size,在每次⼊队或者出队时将size和maxSize进⾏⽐较，从⽽避免假溢出。

使⽤这种⽅式未免有些繁琐。

２．使⽤循环队列，将队列掰弯，也就是将队列看成环状结构，即data[0]为紧接着data[MaxLen-1]的单元，为相邻的元素，⾸位成为⼀个环，如下所⽰：理解循环队列⾸先要确认的是，循环队列仍然是基于数组实现的，使⽤⼀组地址连续的存储单元依次存放从队头到队尾的元素，且仍然设置两个指针front，rear。

注意的是，其实这两个指针是整数型的，起得是知识的作⽤便于理解，所以称之为指针。

这两个指针，⼀个指着队头，⼀个指着队尾。

这两个指针可以看做动态的过程，即这两个指针其实是互相追赶的。

在追赶中就是队列中元素添加和删除的过程。

当rear追到front时就表⽰队列已经满了，当front追上rear时就表⽰队列已经空了。

循环队列的学习解析以及C语言实现首先我们先来了解一下队列的概念：队列是一种先进先出的线性表只能在表头删除在表尾插入，操作系统的作业队列就是队列的一个很好的应用。

也有可以在两端均可进行插入和删除操作的队列，称为双端队列，但其用处并没有一般队列广泛。

ADT Queue {数据对象：D＝{ai | ai∈ElemSet, i=1,2,...,n, n≥0} 数据关系：R1＝{ <a i-1,ai > | ai-1, ai ∈D, i=2,...,n} （约定其中a1端为队列头，an端为队列尾）基本操作：InitQueue(&Q) 初始化队列DestroyQueue(&Q) 销毁队列QueueEmpty(Q) 判断队列空否QueueLength(Q) 求取队长GetHead(Q, &e) 取对头元素ClearQueue(&Q) 清空对列EnQueue(&Q, e) 入队一个元素DeQueue(&Q, &e) 出队一个元素QueueTravers(Q, visit()） 访问队列} ADT Queue队列也有两种存储结构，分别是顺序存储和链式存储。

队列的顺序结构和顺序表以及顺序栈的存储结构类似，他们所运用的都是一组地址连续的存储。

其中队列需要附设两个整形变量front 和rear 分别指示队列头元素和队列的尾元素的位置。

c b a 5 4 3 2 1 0 Q.rear →Q.fron → Q.rea → Q.fron→(1)空队列 (2)a,b,,c 相继入队由于顺序队列所分配的空间有限，根据队列入队和出队的特点可能发生“假溢出”现象，即队尾元素无法在前移。

解决的办法就是将队列抽象成为环状，即循环队列。

循环队列以下是循环队列的几种主要的操作以及C 语言实现：/********循环队列的数据结构***********/#define MAXQSIZE 10typedef struct{QElemType *base;int front;int rear; { 队空条件：Q.front=Q.rear队满条件：(Q.rear+1)%MAXQSIZE} SqQueue;1、循环队列的初始化Status InitQueue(SqQueue &Q){ //构建一个空队列Q.base = new QElemType[MAXQSIZE];if( Q.base = NULL) //存储分配失败exit(OVERFLOW) ;Q.front = Q.rear = 0; //头尾指针置为零，队列为空return OK;}2、求循环队列长度int QueueLength(Squeue Q){return (Q.rear - Q.front + MAXQSIZE )%MAXQSIZE; }3、入队Status EnQueue (SqQueue &Q , QElemType e){if((Q.rear+1)%MAXQSIZe == Q.front)return ERROW;Q.base[Q.rear] = e;Q.rear = (Q.rear + 1) %MAXQSIZE;return OK:}4、出队Status DeQueue(SqQueue &Q,QElemType &e)if(Q.front==Q.rear)return ERROW;e=Q.base[Q.front];Q.front = (Q.front + 1 )%MAXQSIZE; return OK;}5、取队头元素SElemType GetHead(SqQueue Q) {if(Q.front ! = Q.rear)return Q.base[Q.front];}队列的链式表示和实现。

C语⾔循环队列的表⽰与实现实例详解1.概述：C语⾔的队列（queue），是先进先出（FIFO, First-In-First-Out）的线性表数据结构。

在具体应⽤中通常⽤链表或者数组来实现。

队列只允许在后端（称为rear）进⾏插⼊操作，在前端（称为front）进⾏删除操作。

循环队列可以更简单的防⽌伪溢出的发⽣，但是队列⼤⼩是固定的。

2.实例代码：/* 队列的顺序存储结构(循环队列) */#define MAX_QSIZE 5 /* 最⼤队列长度+1 */typedef struct{QElemType *base; /* 初始化的动态分配存储空间 */int front; /* 头指针，若队列不空，指向队列头元素 */int rear; /* 尾指针，若队列不空，指向队列尾元素的下⼀个位置 */}SqQueue;/* 循环队列的基本操作(9个) */void InitQueue(SqQueue *Q){ /* 构造⼀个空队列Q */Q->base=malloc(MAX_QSIZE*sizeof(QElemType));if(!Q->base) /* 存储分配失败 */exit(OVERFLOW);Q->front=Q->rear=0;}void DestroyQueue(SqQueue *Q){ /* 销毁队列Q，Q不再存在 */if(Q->base)free(Q->base);Q->base=NULL;Q->front=Q->rear=0;}void ClearQueue(SqQueue *Q){ /* 将Q清为空队列 */Q->front=Q->rear=0;}Status QueueEmpty(SqQueue Q){ /* 若队列Q为空队列，则返回TRUE；否则返回FALSE */if(Q.front==Q.rear) /* 队列空的标志 */return TRUE;elsereturn FALSE;}int QueueLength(SqQueue Q){ /* 返回Q的元素个数，即队列的长度 */return(Q.rear-Q.front+MAX_QSIZE)%MAX_QSIZE;}Status GetHead(SqQueue Q,QElemType *e){ /* 若队列不空，则⽤e返回Q的队头元素，并返回OK；否则返回ERROR */if(Q.front==Q.rear) /* 队列空 */return ERROR;*e=Q.base[Q.front];return OK;}Status EnQueue(SqQueue *Q,QElemType e){ /* 插⼊元素e为Q的新的队尾元素 */if((Q->rear+1)%MAX_QSIZE==Q->front) /* 队列满 */return ERROR;Q->base[Q->rear]=e;Q->rear=(Q->rear+1)%MAX_QSIZE;return OK;}Status DeQueue(SqQueue *Q,QElemType *e){ /* 若队列不空，则删除Q的队头元素，⽤e返回其值，并返回OK；否则返回ERROR */if(Q->front==Q->rear) /* 队列空 */return ERROR;*e=Q->base[Q->front];Q->front=(Q->front+1)%MAX_QSIZE;return OK;}void QueueTraverse(SqQueue Q,void(*vi)(QElemType)){ /* 从队头到队尾依次对队列Q中每个元素调⽤函数vi() */int i;i=Q.front;while(i!=Q.rear){vi(Q.base[i]);i=(i+1)%MAX_QSIZE; }printf("\n");}。

用链表实现循环队列的方法循环队列是一种利用固定大小的数组实现队列的数据结构，它具有高效的空间利用率和灵活的数据处理能力。

在某些场景下，我们可以使用链表来实现循环队列，以便更好地满足特定需求。

本文将详细介绍如何用链表实现循环队列的方法。

一、链表循环队列的基本概念链表循环队列是一种基于链表实现的队列结构，它具备以下特点：1.链表中的节点包含两个域：数据域和指针域。

数据域存储队列中的元素，指针域存储指向下一个节点的指针。

2.链表循环队列具有头指针和尾指针，分别指向队列的第一个元素和最后一个元素。

3.链表循环队列的长度可以动态调整，不会受到固定数组长度的限制。

二、链表循环队列的初始化1.创建一个头节点，头节点的数据域可以不存储有效数据，仅作为队列的起始节点。

2.初始化头指针和尾指针，使它们都指向头节点。

3.初始化队列长度为0。

三、链表循环队列的基本操作1.入队操作：a.创建一个新节点，将新节点数据域设置为待入队的元素。

b.将尾指针指向的节点的指针域指向新节点。

c.更新尾指针，使其指向新节点。

d.队列长度加1。

2.出队操作：a.判断队列是否为空，若为空，则返回错误信息。

b.保存头指针指向的节点的数据域值。

c.更新头指针，使其指向下一个节点。

d.删除原头节点。

e.队列长度减1。

3.获取队首元素：a.判断队列是否为空，若为空，则返回错误信息。

b.返回头指针指向的节点的数据域值。

4.判断队列是否为空：a.判断头指针是否等于尾指针，若相等，则队列为空。

四、链表循环队列的优势1.空间利用率高：链表循环队列可以根据需求动态调整长度，有效避免内存浪费。

2.灵活性强：链表循环队列可以方便地实现队列的扩展和收缩，适应不同场景的需求。

3.数据处理高效：链表循环队列在入队和出队操作时，时间复杂度均为O(1)，具有较高的处理效率。

总结：使用链表实现循环队列是一种高效、灵活的数据结构设计方法。

队列（循环队列的顺序实现）⼀、概述与栈相反，队列是先进先出(FIFO)，后进后出的数据结构。

插⼊的⼀端叫做队尾，⽽出去的⼀端则称为队头或队⾸。

但是队列(Queue)有⼀种扩展形式，称为双端队列(Deque)，即可以在两端都进⾏插⼊和删除的操作，看起来双端队列似乎更加使⽤，但在实际应⽤中却并不常见。

同样的，队列也有两种实现形式，即顺序队列和链队列。

链队列可以参考链栈，直接将出栈操作改成删除头节点即可，插⼊删除⽅便，适合栈和队列。

顺序队列当然是数组实现，顺序队列的问题在于出队时前⾯空出的位置是否由后⾯的元素补充，如果不补充，那么会造成空间极度的浪费，如果补充，那么需要将每个元素都向前移，时间复杂度此时来到O(N)，为了解决这个问题，循环队列应运⽽⽣，即将补充的元素放到前⾯由于出队⽽造成的空缺位置。

这样就可以最⼤限度的利⽤已申请的空间。

⼆、顺序实现循环队列数据域：private int Capacity;private int front;private int rear;private int [] data;static int DEFAULT_SIZE = 6;public Queue(){front = rear = 0;Capacity = DEFAULT_SIZE;data = new int [Capacity];}由于JAVA并不⽀持泛型数组，因此我们以int型的队列作为⽰例。

这⾥简单描述⼀下循环队列的结构，⼀个空的循环队列如下图：当⼊队3个元素时变为：再出队1个元素接下来是求长度和判满空public int getSize(){return (rear - front + Capacity) % Capacity;}public boolean isEmpty(){return (rear == front);}public boolean isFull(){return ((rear + 1) % Capacity == front);}先说求元素个数(长度)，从图中看起来好像直接返回rear-front即可，但是因为是循环队列，考虑下列情况：显然不能⽤简单的减法，必须将两种算法统⼀起来，因此(rear - front + Capacity) % Capacity正是起到这样的作⽤。

实现循环队列的入队出队等基本操作循环队列是一种特殊的队列数据结构，通过循环利用数组空间来实现入队和出队操作。

它的特点是队头和队尾可以在数组上循环移动，从而充分利用数组空间，提高队列的效率。

下面将详细介绍循环队列的实现。

1.定义循环队列的数据结构循环队列的数据结构由以下几个成员组成：-一个固定大小的数组，用于存储队列元素。

- 一个队头指针front，指向队列的第一个元素。

- 一个队尾指针rear，指向队列的最后一个元素的下一个位置。

2.初始化循环队列首先，我们需要在内存中分配一个固定大小的数组，并初始化队头和队尾指针为0。

```pythondef __init__(self, k: int):self.queue = [0] * kself.front = self.rear = 0```3.入队操作入队操作会在队尾插入一个新元素，并将队尾指针后移一位。

如果队列已满，则入队操作会失败。

```pythondef enqueue(self, value: int) -> bool:if self.isFull(:return Falseself.queue[self.rear] = valueself.rear = (self.rear + 1) % len(self.queue)return True```4.出队操作出队操作会删除队头元素，并将队头指针后移一位。

如果队列为空，则出队操作会失败。

```pythondef dequeue(self) -> bool:if self.isEmpty(:return Falseself.front = (self.front + 1) % len(self.queue)return True```5.判空操作判空操作会检查队头和队尾指针是否相等，如果相等则说明队列为空。

```pythondef isEmpty(self) -> bool:return self.front == self.rear```6.判满操作判满操作会检查队尾指针的下一位是否等于队头指针，如果相等则说明队列已满。