内江 网站建设,网站百度指数,建设一个公司网站要具备什么,游戏公司网站模板下载本专栏内容为#xff1a;leetcode刷题专栏#xff0c;记录了leetcode热门题目以及重难点题目的详细记录 #x1f493;博主csdn个人主页#xff1a;小小unicorn ⏩专栏分类#xff1a;Leetcode #x1f69a;代码仓库#xff1a;小小unicorn的代码仓库#x1f69a; … 本专栏内容为leetcode刷题专栏记录了leetcode热门题目以及重难点题目的详细记录 博主csdn个人主页小小unicorn ⏩专栏分类Leetcode 代码仓库小小unicorn的代码仓库 关注我带你学习编程知识 循环队列 题目描述解题思路代码解决结果与总结 题目描述 题目来源Leetcode622.设计循环队列 设计你的循环队列实现。 循环队列是一种线性数据结构其操作表现基于 FIFO先进先出原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。
循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里一旦一个队列满了我们就不能插入下一个元素即使在队列前面仍有空间。但是使用循环队列我们能使用这些空间去存储新的值。
你的实现应该支持如下操作
1.MyCircularQueue(k): 构造器设置队列长度为 k 。 2.Front: 从队首获取元素。如果队列为空返回 -1 。 3.Rear: 获取队尾元素。如果队列为空返回 -1 。 4.enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。 5.deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。 6.isEmpty(): 检查循环队列是否为空。 7.isFull(): 检查循环队列是否已满。
解题思路
在环形队列中队列为空时队头队尾指向同一个位置。当队列不为空时队头指向插入的第一个数据队尾指向最后一个数据的下一个位置。当tail1等于front时说明环形队列已满。 注意环形队列的队尾不能像常规队列中队尾一样指向最后一个数据如果这样的话我们将不能区别环形队列的状态是空还是满因为此时队头和队尾都指向同一个位置。这就意味着我们必须留出一个空间这个空间不能存放数据这样我们才能很好的区别环形队列的状态是空还是满。 我们如果用一个数组来实现这个环形队列的话上面这三种状态就对应于以下三种状态 可以看出此时这个数组和环形完全扯不上关系这其实很简单我们只需注意判断两个地方 1.当指针指向整个数组的后方的时候让该指针重新指向数组的第一个元素。 2.当指针指向整个数组的前方的时候让该指针直接指向数组最后一个有效元素的后面。 这样就使得该数组在逻辑上是“环形”的了。
代码解决
typedef struct
{int* a;//数组模拟环形队列int k;//队列可存储的有效数据总数int front;//队头int tail;//队尾的后一个位置
} MyCircularQueue;MyCircularQueue* myCircularQueueCreate(int k)
{MyCircularQueue* obj (MyCircularQueue*)malloc(sizeof(MyCircularQueue));//申请一个环形队列obj-a (int*)malloc(sizeof(int)*(k1));//开辟队列空间//初始时队头和队尾均为0obj-front 0;obj-tail 0;obj-k k;//设置队列可存储的有效数据个数return obj;
}bool myCircularQueueIsEmpty(MyCircularQueue* obj)
{return obj-front obj-tail;//当front和tail指向同一位置时队列为空
}bool myCircularQueueIsFull(MyCircularQueue* obj)
{int tailNext obj-tail1;if(tailNext obj-k1)//当指针指到队列末尾时指针返回队列开头使队列循环{tailNext 0;}return tailNext obj-front;//当tail1指向的位置与front相同时队列满
}bool myCircularQueueEnQueue(MyCircularQueue* obj, int value)
{if(myCircularQueueIsFull(obj))//队列已满不能再插入数据{return false;}else//插入数据{obj-a[obj-tail] value;obj-tail;if(obj-tail obj-k1)//使队列循环obj-tail 0;return true;}
}bool myCircularQueueDeQueue(MyCircularQueue* obj)
{if(myCircularQueueIsEmpty(obj))//当队列为空时无法再删除数据{return false;}else//删除数据{obj-front;if(obj-front obj-k1)//使队列循环obj-front 0;return true;}
}int myCircularQueueFront(MyCircularQueue* obj)
{if(myCircularQueueIsEmpty(obj))//当队列为空时无数据可返回{return -1;}else{return obj-a[obj-front];//返回队头指向的数据}
}int myCircularQueueRear(MyCircularQueue* obj)
{if(myCircularQueueIsEmpty(obj))//当队列为空时无数据返回{return -1;}else//返回tail-1指向位置的数据{int tailPrev obj-tail-1;if(tailPrev -1)//使队列循环tailPrev obj-k;return obj-a[tailPrev];}
}void myCircularQueueFree(MyCircularQueue* obj)
{free(obj-a);//先释放动态开辟的数组free(obj);//再释放动态开辟的结构体
}
结果与总结 通过所有示例问题得到解决。
