数据结构第九弹---循环队列
2024-01-07 19:34:52
循环队列
1、循环队列的定义
顺序队列在使用过程中容易出现虚假的满状态, 为了解决这个问题,就产生了一个较巧妙的方法,将顺序队列臆造为一个环状的空间,称之为循环队列。循环队列中指针和队列元素之间的关系不变,我们只需要利用模运算就可以很容易实现指针的循环移动。但是循环队列中存在一个问题,在循环队列中只凭头指针front等于尾指针rear无法判别队列空间是“空”还是“满”,可有两种处理方法:其一是另设一个标志位以区别队列是“空”还是“满”;其二是少用一个元素空间,约定以“队列头指针在队列尾指针的下一位置(指环状的下一位置)上”作为队列呈“满”状态的标志。此处使用方法二来解决这个问题。
2、循环队列的结构
typedef struct CircularQueue{
int* a;//存放数据数组
int front;//头结点
int back;//尾结点后一个,有效数据个数
int k;//元素个数
} CircularQueue;
3、循环队列的实现
3.1、初始化队列
开辟k+1个空间,k个存放数据,将头尾结点初始化为0,即数组的第一个位置。
代码实现
//队列初始化
CircularQueue* InitQueue(int k)
{
CircularQueue* obj=(CircularQueue*)malloc(sizeof(CircularQueue));//为队列分配空间
obj->a=(int*)malloc(sizeof(int)*(k+1));
obj->front=obj->back=0;//初始队列为空,头尾指针都指向0的位置
obj->k=k;
return obj;
}
测试
3.2、判断是否为空
根据结构定义,头结点跟尾结点相等时则队列为空。为真则为空,为假则不为空。
代码实现
bool QueueEmpty(CircularQueue* obj) {
return obj->front==obj->back;//头尾结点相等时则为空
}
测试
3.3、判断是否为满
根据循环队列结构的定义,尾结点后一个是头结点则队列为满。为真则为满,不为真则不满。
代码实现
bool QueueFull(CircularQueue* obj) {
return (obj->back+1)%(obj->k+1)==obj->front;//尾结点的下一个等于头结点则为满
}
测试
3.4、入队
根据队列的结构定义,back为尾结点的后一个,当队列空间没有满时,插入数据时则在back位置插入。
代码实现
bool EnQueue(CircularQueue* obj, int value) {
//满了返回false
if(QueueFull(obj))
{
return false;
}
obj->a[obj->back]=value;//插入有效数据
obj->back++;
obj->back%=(obj->k+1);//进入循环,不能超过最大个数
return true;
}
测试
3.5、出队
根据队列的定义,只能队头出数据,在循环队列里面通过头尾结点来访问数据,将front++即可删除头结点数据。
代码实现
bool DeQueue(CircularQueue* obj) {
//如果为空返回false
if(QueueEmpty(obj))
{
return false;
}
obj->front++;//出队则头结点往前走
obj->front%=(obj->k+1);
return true;
}
测试
3.6、返回队头元素
在保证队列不是空的情况下,队头元素为front下标的元素,为空则返回-1
代码实现
int QueueFront(CircularQueue* obj) {
//为空返回-1
if(QueueEmpty(obj))
return -1;
return obj->a[obj->front];
}
测试
3.7、返回队尾元素
在保证队列不是空的情况下,队头元素为back前一个下标的元素,为空则返回-1
代码实现
int QueueRear(CircularQueue* obj) {
//为空返回-1
if(QueueEmpty(obj))
return -1;
//有一种特殊情况 不是back-1
//1.
//return obj->a[(obj->back-1+obj->k+1)%(obj->k+1)];
return obj->a[(obj->back+obj->k)%(obj->k+1)];
//2.
// if(obj->back==0)
// {
// return obj->a[obj->k];
// }
// else
// {
// return obj->a[obj->back-1];
// }
}
测试
3.8、销毁队列
数组是通过队列的指针访问,且数组和队列都是内存是连续的,可以直接释放内存,所以先释放数组,在释放队列
void QueueFree(CircularQueue* obj) {
free(obj->a);//释放数组
free(obj);//释放队列
}
4、代码汇总
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
typedef int QDataType;
//结构定义
typedef struct CircularQueue{
QDataType* a;//存放数据数组
int front;//头结点
int back;//尾结点后一个,有效数据个数
int k;//元素个数
} CircularQueue;
//初始化
CircularQueue* InitQueue(int k)
{
CircularQueue* obj=(CircularQueue*)malloc(sizeof(CircularQueue));//为队列分配空间
obj->a=(int*)malloc(sizeof(int)*(k+1));
obj->front=obj->back=0;//初始队列为空,头尾指针都指向0的位置
obj->k=k;
return obj;
}
//判断是否为空
bool QueueEmpty(CircularQueue* obj) {
return obj->front==obj->back;//头尾结点相等时则为空
}
//判断是否为满
bool QueueFull(CircularQueue* obj) {
return (obj->back+1)%(obj->k+1)==obj->front;//尾结点的下一个等于头结点则为满
}
//入队
bool EnQueue(CircularQueue* obj, int value) {
//满了返回false
if(QueueFull(obj))
{
return false;
}
obj->a[obj->back]=value;//插入有效数据
obj->back++;
obj->back%=(obj->k+1);//进入循环,不能超过最大个数
return true;
}
//出队
bool DeQueue(CircularQueue* obj) {
//如果为空返回false
if(QueueEmpty(obj))
{
return false;
}
obj->front++;//出队则头结点往前走
obj->front%=(obj->k+1);
return true;
}
//获取队头元素
int QueueFront(CircularQueue* obj) {
//为空返回-1
if(QueueEmpty(obj))
return -1;
return obj->a[obj->front];
}
//获取队尾元素
int QueueRear(CircularQueue* obj) {
//为空返回-1
if(QueueEmpty(obj))
return -1;
//有一种特殊情况 不是back-1
//1.
//return obj->a[(obj->back-1+obj->k+1)%(obj->k+1)];
return obj->a[(obj->back+obj->k)%(obj->k+1)];
//2.
// if(obj->back==0)
// {
// return obj->a[obj->k];
// }
// else
// {
// return obj->a[obj->back-1];
// }
}
//销毁
void QueueFree(CircularQueue* obj) {
free(obj->a);
free(obj);
}
循环队列OJ链接
循环队列
总结
本篇博客就结束啦,谢谢大家的观看,如果公主少年们有好的建议可以留言喔,谢谢大家啦!
文章来源:https://blog.csdn.net/2201_75584283/article/details/135339394
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!