这是一道leetcode关于队列的经典题:
622. 设计循环队列https://leetcode.cn/problems/design-circular-queue/
思路:
大家注意这个题目要求,这个队列是定长的,如果满了则不能再添加数据。那么我们设计一个队头front和队尾rear,每次添加数据rear向后走,这时就有一个问题,怎么区分空和满呢?当最后一个数据入队列之后,由于这是个循环队列,rear会回到front这个位置。那么比较好的一种方法就是多开一个空间,满的条件是rear+1==front。
实现:
循环队列的定义:
typedef struct {
int K;
int* a;
int front;
int rear;
} MyCircularQueue;
循环队列的创建:
为队列和数组创建空间,需要注意的是数组a的空间是K+1个,要多开一个.
MyCircularQueue* myCircularQueueCreate(int k) {
MyCircularQueue* obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
//多开辟一个空间,用以区分空和满
obj->K=k;
obj->a=(int*)malloc(sizeof(int)*(obj->K+1));
obj->front=0;
obj->rear=0;
return obj;
}
判断队列是否为空:
如果front==rear则为空。
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
return obj->front==obj->rear;
}
判断队列是否为满:
如果rear+1==front则为满,或者说(rear+1)%(k+1)==front。
bool myCircularQueueIsFull(MyCircularQueue* obj) {
return (obj->rear+1)%(obj->K+1)==obj->front;
}
数据入队列:
先判断队列是否满了,满了则返回false。如果不满则在rear这个位置上添加数据,再把rear++,再将rear=rear%(k+1)。
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
if(myCircularQueueIsFull(obj))
return false;
obj->a[obj->rear]=value;
obj->rear++;
obj->rear=(obj->rear)%(obj->K+1);
return true;
}
数据出队列:
判断一下队列是否为空,空则返回false。出队列直接将front++即可,再将front=front%(k+)。
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj))
return false;
obj->front++;
obj->front=(obj->front)%(obj->K+1);
return true;
}
取队列头部数据:
int myCircularQueueFront(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj))
return -1;
else
return obj->a[obj->front];
}
取队列尾部数据:
这里需要注意,尾部数据的位置是在rear-1这个位置,所以rear-1+k+1就是rear+k.文章来源:https://www.toymoban.com/news/detail-758989.html
int myCircularQueueRear(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj))
return -1;
else
return obj->a[(obj->rear+obj->K)%(obj->K+1)];
}
销毁队列:
void myCircularQueueFree(MyCircularQueue* obj) {
free(obj->a);
free(obj);
}
完整代码:
typedef struct {
int K;
int* a;
int front;
int rear;
} MyCircularQueue;
MyCircularQueue* myCircularQueueCreate(int k) {
MyCircularQueue* obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
//多开辟一个空间,用以区分空和满
obj->K=k;
obj->a=(int*)malloc(sizeof(int)*(obj->K+1));
obj->front=0;
obj->rear=0;
return obj;
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
return obj->front==obj->rear;
}
bool myCircularQueueIsFull(MyCircularQueue* obj) {
return (obj->rear+1)%(obj->K+1)==obj->front;
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
if(myCircularQueueIsFull(obj))
return false;
obj->a[obj->rear]=value;
obj->rear++;
obj->rear=(obj->rear)%(obj->K+1);
return true;
}
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj))
return false;
obj->front++;
obj->front=(obj->front)%(obj->K+1);
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
return obj->a[(obj->rear+obj->K)%(obj->K+1)];
}
void myCircularQueueFree(MyCircularQueue* obj) {
free(obj->a);
free(obj);
}
这次的分享到这里就结束了,感谢大家的阅读!文章来源地址https://www.toymoban.com/news/detail-758989.html
到了这里,关于手把手教你实现一个循环队列(C语言)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!