【数据结构与算法（C语言）】循环队列图解

2024-06-13 06:50:02
开发
7

1. 前言

将队列的头尾相接，臆造成环状的顺序存储结构称为循环队列。

普通的顺序存储队列会出现 假溢出 情况。如下面三张图（三个步骤）描述的情况

1.1 普通循环队列假溢出

下面来看看普通队列是如何产生假溢出现象的。

1.1.1 初始化队列

此时队列为空队列。头指针和尾指针都指向第一个空间

1.1.2 插满队列

插入J1、J2、J3、J4、J5、J6，因为q->rear=6，说明队列已满
在这里插入图片描述

1.1.3 删除元素后，再插入元素

删除J1，J2，按道理应该是空出两个空间，可以插入新元素，但此时q ->rear指向6号地址，还是判定队列已满，如果再插入元素，q-rear=7,则队列溢出。但实际队列是有空间的

在这里插入图片描述

1.2 循环队列

普通的循环队列有上述假溢出缺点。于是乎，循环队列就应运而生了。

循环队列的解决假溢出方法如下面三张图中展示的步骤：

1.2.1 插入元素，队列已满

还剩一个空间的时候，队列就满了。这样设置的原因是，如果不浪费一个空间的话，当 queue.front=queue.rear，可能会有两种情况，一个是队列为空，一个是队列已满。如果预留一个空间的话，可以用 queue.rear + 1=queue.front 判断队列已满，这样和队列为空的判断方式不冲突。
在这里插入图片描述

1.2.2 将元素J1、J2出列，循环队列又空出两个空间

在这里插入图片描述

1.2.3 元素J6可以继续入列

在这里插入图片描述

2. 存储结构和函数说明

2.1 队列的结构

typedef struct{
	QElemType * base;  //存储空间 
	int front;	   //队列头的下标
	int rear; 	   //队列尾的下标
}SqQueue;     //定义一个队列类型

2.2 基本操作函数

和上一篇博客中的链式队列差不多，一共8个函数。

Status InitQueue(SqQueue * queue); //初始化队列
void DestroyQueue(SqQueue *queue); //销毁队列
Status ClearQueue(SqQueue * queue);//清空队列
Status QueueEmpty(SqQueue queue);  //判断队列是否为空
Status GetHead(SqQueue queue ,QElemType * e); //获取队列头元素
int QueueLength(SqQueue queue);			//获取队列长度
Status EnQueue(SqQueue  * queue, QElemType e); //元素入列
Status DeQueue(SqQueue * queue ,QElemType * e); //元素出列

2.3 初始化队列

原型：Status InitQueue(SqQueue * queue)
说明：初始化队列,申请一个头结点的内存

/*初始化队列,申请一个头结点的内存*/
Status InitQueue(SqQueue * queue)
{
	queue->base = (QElemType *) malloc(sizeof(QElemType)*MAXSIZE); //申请一个队列结点作为头结点的内存地址给 队头指针；
	if(queue->base == NULL)
		return FALSE;
	queue->front = queue->rear =0;
	return TRUE;
}

2.4 销毁队列 DestroyQueue

原型：void DestroyQueue(SqQueue *queue)
功能：销毁队列，释放队列的数据空间

/*销毁栈，释放队列的数据空间*/
void DestroyQueue(SqQueue *queue)
{
	free(queue->base);
	queue->front= queue->rear =0;
}

2.5 清空队列 ClearQueue

原型：Status ClearQueue(SqQueue * queue)
功能：清空队列的元素，但队列的空间保留

//将队列queue清空
Status ClearQueue(SqQueue * queue)
{
	queue->front = queue->rear = 0;
	return OK;	
}

2.6 获取队列第一个元素 GetHead

原型：Status GetHead(SqQueue queue ,QElemType * e)
功能：获取队列第一个元素,注意不是删除元素

//获取队列第一个元素
Status GetHead(SqQueue queue ,QElemType * e)
{
	if(QueueEmpty(queue))
		return FALSE;
	*e=queue.base[queue.front];
	return TRUE;
}

2.7 获取队列长度

原型：int QueueLength(SqQueue queue)
功能：队列长度

//返回队列长度
int QueueLength(SqQueue queue)
{
	return (queue.rear - queue.front + MAXSIZE) % MAXSIZE;
}

2.8 元素入列 EnQueue

原型：Status EnQueue(SqQueue * queue, QElemType e)
功能：元素e 插入队列queue

//元素e 插入队列queue
Status EnQueue(SqQueue  * queue, QElemType e)
{
	if((queue->rear + 1) % MAXSIZE == queue->front) //队列满，
		return FALSE ;
	queue->base[queue->rear]=e;       //e 插入队列尾部，队尾加1
	queue->rear = (queue->rear + 1) % MAXSIZE;
	return TRUE;
}

2.9 元素出列 DeQueue

原型：Status DeQueue(SqQueue * queue ,QElemType * e)
功能：若队列queue不空，则删除Q的队头元素，用e返回其值，并返回 OK；否则返回ERROR

//若队列queue不空，则删除Q的队头元素，用e返回其值，并返回 OK；否则返回ERROR
Status DeQueue(SqQueue * queue ,QElemType * e)
{
	if(QueueEmpty( *queue))
		return FALSE;
	*e = queue->base[queue->front];
	queue->front= (queue->front + 1) % MAXSIZE;
	return TRUE;
}

2.10 遍历队列 QueueTraverse

原型：Status QueueTraverse(SqQueue queue,void (*visit)())
功能：遍历队列，对队列的每个元素调用Visit函数

//遍历队列，对队列的每个元素调用Visit函数
Status QueueTraverse(SqQueue queue,void (*visit)())
{
	int i = queue.front;
	if(QueueEmpty(queue))
		return FALSE ;
	if(queue.front < queue.rear)	
		while(i < queue.rear)
			visit(queue.base[i++]);
	else{
		while(i< MAXSIZE)
			visit(queue.base[i++]);
		i=0;
		while(i<queue.rear)
			visit(queue.base[i++]);
	}
	return TRUE;
}

3. 完整源码和测试代码

#include <stdio.h>
#include <stdlib.h>

#define TRUE  1
#define FALSE 0
#define OK    1
#define ERROR 0
#define MAXSIZE 6 //最大值设置为6

typedef  int Status;

typedef  int QElemType; //定义元素类型为整型


typedef struct{
	QElemType * base;  //存储空间 
	int front;	   //队列头的下标
	int rear; 	   //队列尾的下标
}SqQueue;     //定义一个队列类型 

Status InitQueue(SqQueue * queue);
void DestroyQueue(SqQueue *queue);
Status ClearQueue(SqQueue * queue);
Status QueueEmpty(SqQueue queue);
Status GetHead(SqQueue queue ,QElemType * e);
int QueueLength(SqQueue queue);
Status EnQueue(SqQueue  * queue, QElemType e);
Status DeQueue(SqQueue * queue ,QElemType * e);

/*初始化队列,申请一个头结点的内存*/
Status InitQueue(SqQueue * queue)
{
	queue->base = (QElemType *) malloc(sizeof(QElemType)*MAXSIZE); //申请一个队列结点作为头结点的内存地址给 队头指针；
	if(queue->base == NULL)
		return FALSE;
	queue->front = queue->rear =0;
	return TRUE;
}

/*销毁队列，释放队列的数据空间*/
void DestroyQueue(SqQueue *queue)
{
	free(queue->base);
	queue->front= queue->rear =0;
}

//将队列queue清空
Status ClearQueue(SqQueue * queue)
{
	queue->front = queue->rear = 0;
	return OK;	
}

//判断队列是否为空
Status QueueEmpty(SqQueue queue)
{
	return queue.front == queue.rear? TRUE:FALSE; 
}

//获取队列第一个元素
Status GetHead(SqQueue queue ,QElemType * e)
{
	if(QueueEmpty(queue))
		return FALSE;
	*e=queue.base[queue.front];
	return TRUE;
}


//返回队列长度
int QueueLength(SqQueue queue)
{
	return (queue.rear - queue.front + MAXSIZE) % MAXSIZE;
}


//元素e 插入队列queue
Status EnQueue(SqQueue  * queue, QElemType e)
{
	if((queue->rear + 1) % MAXSIZE == queue->front) //队列满，
		return FALSE ;
	queue->base[queue->rear]=e;       //e 插入队列尾部，队尾加1
	queue->rear = (queue->rear + 1) % MAXSIZE;
	return TRUE;
}

//若队列queue不空，则删除Q的队头元素，用e返回其值，并返回 OK；否则返回ERROR
Status DeQueue(SqQueue * queue ,QElemType * e)
{
	if(QueueEmpty( *queue))
		return FALSE;
	*e = queue->base[queue->front];
	queue->front= (queue->front + 1) % MAXSIZE;
	return TRUE;

}
void Visit(QElemType e)
{
	printf("%3d",e);
}
//遍历队列，对队列的每个元素调用Visit函数
Status QueueTraverse(SqQueue queue,void (*visit)())
{
	int i = queue.front;
	if(QueueEmpty(queue))
		return FALSE ;
	if(queue.front < queue.rear)	
		while(i < queue.rear)
			visit(queue.base[i++]);
	else{
		while(i< MAXSIZE)
			visit(queue.base[i++]);
		i=0;
		while(i<queue.rear)
			visit(queue.base[i++]);
	}
	return TRUE;
}

int main()
{
	QElemType e;
	SqQueue queue;
	InitQueue(&queue);
	printf("队头分别插入数字3、4、5、6、7后:");//此时队列已经满了，设置maxsize=6,实际只能存储5个，
						   //因为只剩一个空间，代表队列已满。即 front= (rear+1)%maxsize
						   //如果不留一个空间空着，那么队列满和队列空都是 front=rear,很难分辨
	EnQueue(&queue,3);
	EnQueue(&queue,4);
	EnQueue(&queue,5);
	EnQueue(&queue,6);
	EnQueue(&queue,7);
	QueueTraverse(queue,Visit);
	printf("\n继续插入数字8");
	if(EnQueue(&queue,8))
		printf("\n出问题了，队列满了，还能插入!");
	else
		printf("\n队列已满，无法插入!");
	printf("\n删除队头数字后:");
	DeQueue(&queue,&e);	    //删除后的队列中还剩4个元素
	QueueTraverse(queue,Visit);
	printf("\n继续插入8数字后：");
	EnQueue(&queue,8);	    //数字8被存放到queue.base[5]中了
	QueueTraverse(queue,Visit);
	printf("\n清空队列");
	ClearQueue(&queue);
	printf("\n队列长度:%d\n",QueueLength(queue));
	DestroyQueue(&queue);
	getchar();
	return 0;
}

4. 测试结果

在这里插入图片描述

5. 小结

循环队列的优缺点

5.1 优点：

(a) 解决了普通的顺序存储队列的假溢出问题。
(b) 读取方便、快捷

5.2 缺点

存储空间大小固定，无法根据需要进行扩展。

原文地址:https://blog.csdn.net/weiweiliude2/article/details/139610109 本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：https://www.suanlizi.com/kf/1801024184529326080.html 如若内容造成侵权/违法违规/事实不符，请联系《酸梨子》网邮箱：1419361763@qq.com进行投诉反馈，一经查实，立即删除！

阅读全部