【数据结构】循环队列

举报
修修修也 发表于 2024/09/10 18:06:28 2024/09/10
【摘要】 🦄个人主页:修修修也 🎏所属专栏:数据结构 ⚙️操作环境:Visual Studio 2022​编辑目录🎏 队列顺序存储的不足 🎏 循环队列的定义 🎏 设计循环队列 结语 🎏队列顺序存储的不足我们假设用一个可以存放为n个数据的数组arr来实现队列:​编辑很容易可以知道:给arr中入队时时间复杂度为O(1),而出队时时间复杂度却是O(n).按照传统方式每次出队时都要将所有元素向前挪...

🦄个人主页:修修修也

🎏所属专栏:数据结构

⚙️操作环境:Visual Studio 2022

​编辑


目录

🎏 队列顺序存储的不足

🎏 循环队列的定义

🎏 设计循环队列

结语


🎏队列顺序存储的不足

我们假设用一个可以存放为n数据的数组arr实现队列:

​编辑

很容易可以知道:给arr中入队时时间复杂度为O(1),而出队时时间复杂度却是O(n).

按照传统方式每次出队时都要将所有元素向前挪动是非常麻烦的,我们不如在出队时让头指针也动起来,即在出队时不移动后面的元素,而是让front向后移动,指向新的队头元素:

​编辑

这样出队和入队的时间复杂度都是O(1)了,但是使用这种方式,当我们入队又出队后会造成"假溢出"问题:

数组前面有空着的空间,但因为队列入队要追加在队伍的末尾,因此只能追加在下图中9的后面,但9后面没有空间了,这时就会造成"假溢出"问题.​编辑

你想想,如果你今天去教室上课,因为是水课,后面3排都坐满了人,而前排还有很多空位,你会怎么做?直接走出教室,并告诉自己后面没有座位可坐了?

现实生活中我们不会那样做的,前面有座位,我们当然是可以坐的,除非真的满了,那才需要考虑向老师申请一个大教室.


🎏循环队列的定义

因此,解决假溢出的办法就是后面满了,就从头再开始,也即头尾相接的循环.

我们把队列的这种头尾相接的顺序存储结构称为循环队列.

在刚才的例子中,我们可以改变rear指向下标为0的位置,这样就可以继续入队元素了:

​编辑

 当我们继续一直入队元素,rear一直向后移动,直到将数组入满,此时rearfront重合,同时指向下标为5的位置,如图:

​编辑

此时我们需要思考几个问题,我们刚才说,空队列时,front等于rear,而现在队列满时,也是front等于rear,那么该如何判断此时的队列究竟是空还是?

• 办法一是设置一个标志flag,当front==rear,且flag=0时为队列空,当front==rear,且flag=1时为队列满.

• 办法二是当队列空时,条件是front=rear,当队列满时,我们修改其条件,保留一个元素空间.也就是说,当数组中只剩一个空闲单元时,我们就认为队列满了,如下图所示:​编辑

由于rear可能比front,也可能比front,所以尽管它们只相差一个位置时就是满的情况,但也可能是相差整整一圈.

所以若队列的最大尺寸为QueueSize,那么队列满的条件是(rear+1)%QueueSize==front

(这里的取模"%"的目的就是为了解决rear可能会比front大一圈的问题).

队列的长度计算也要特别注意,通用的计算队列长度公式为:

(rear-front+QueueSize)%QueueSize

有了以上关于循环队列的知识储备,我们接下来实战实现一个循环队列.


🎏设计循环队列

题目链接

622. 设计循环队列 https://leetcode.cn/problems/design-circular-queue/


题目描述

设计你的循环队列实现。 循环队列是一种线性数据结构,其操作表现基于 FIFO(先进先出)原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。

循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里,一旦一个队列满了,我们就不能插入下一个元素,即使在队列前面仍有空间。但是使用循环队列,我们能使用这些空间去存储新的值。

你的实现应该支持如下操作:

• MyCircularQueue(k): 构造器,设置队列长度为 k 。

• Front: 从队首获取元素。如果队列为空,返回 -1 。

• Rear: 获取队尾元素。如果队列为空,返回 -1 。

• enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。

• deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。

• isEmpty(): 检查循环队列是否为空。

• isFull(): 检查循环队列是否已满。


题目详情

​编辑


解题思路

循环队列的设计思路其实在文章前面的简介部分我们已经阐述过了,但在具体实现时,我们仍需注意以下几点:

注意题目要求的返回值,如入队/出队函数要求成功返回true,失败返回false.

注意队列判满的条件

注意rear,front在持续向后移动过程中,如果数值超过了合理的数组下标范围,,则需要想办法将其修正到合理的范围内.


解题代码

综上,解题代码如下:

typedef struct

{

int *arr; //存数据

int front; //头指针

int rear; //尾指针

int k; //存个数

} MyCircularQueue;




bool myCircularQueueIsEmpty(MyCircularQueue* obj)//判空,为空返回true

{

return (obj->front==obj->rear);

}




bool myCircularQueueIsFull(MyCircularQueue* obj)//判满,为满返回true

{

return ((obj->front)==((obj->rear+1)%(obj->k+1)));

}




MyCircularQueue* myCircularQueueCreate(int k)

{

MyCircularQueue*obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));

if(obj==NULL)

{

perror("malloc fail::");

return NULL;

}

obj->arr=(int*)malloc(sizeof(int)*(k+1));//留空一个,便于判断

if(obj->arr==NULL)

{

perror("malloc fail::");

return NULL;

}

obj->front=obj->rear=0;

obj->k=k;

return obj;

}




bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) //入队

{

//队满返回false

if(myCircularQueueIsFull(obj))

{

return false;

}

//队未满尾插

else

{

obj->arr[obj->rear]=value;

obj->rear++;

obj->rear%=(obj->k+1);

return true;

}

}




bool myCircularQueueDeQueue(MyCircularQueue* obj) //出队

{

//队空返回false

if(myCircularQueueIsEmpty(obj))

{

return false;

}

else//队非空则头删

{

obj->front++;

obj->front%=(obj->k+1);

return true;

}

}




int myCircularQueueFront(MyCircularQueue* obj)//取队头

{

if(myCircularQueueIsEmpty(obj))//为空则失败

{

return -1;

}

return obj->arr[obj->front];

}




int myCircularQueueRear(MyCircularQueue* obj)//取队尾

{

if(myCircularQueueIsEmpty(obj))//为空则失败

{

return -1;

}

return obj->arr[(obj->rear+obj->k)%(obj->k+1)];//如果rear=0,rear-1=-1会导致越界访问

}




void myCircularQueueFree(MyCircularQueue* obj)//销毁,开几个销几个

{

free(obj->arr);

free(obj);

}

提交运行:

​编辑


结语

希望这篇有关数据结构循环队列的文章能对您有所帮助,欢迎大佬们留言或私信与我交流.学海漫浩浩,我亦苦作舟!关注我,大家一起学习,一起进步!

相关文章推荐

【数据结构】什么是线性表 ?

【数据结构】线性表的链式存储结构

【数据结构】什么是 ?

【数据结构】用 C 语言实现顺序 ( 附完整运行代码 )

【数据结构】深入浅出理解链表中二级指针的应用

【数据结构】 10 道经典面试题目带你玩转链表


​编辑


 数据结构与队列篇思维导图:

编辑

【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。