当前位置：首页 > news >正文

力扣（LeetCode) ——622. 设计循环队列（C语言）

news 2025/8/17 7:09:17

题目：622. 设计循环队列

在这里插入图片描述

示例1：

MyCircularQueue circularQueue = new MyCircularQueue(3); // 设置长度为 3
circularQueue.enQueue(1); // 返回 true
circularQueue.enQueue(2); // 返回 true
circularQueue.enQueue(3); // 返回 true
circularQueue.enQueue(4); // 返回 false，队列已满
circularQueue.Rear(); // 返回 3
circularQueue.isFull(); // 返回 true
circularQueue.deQueue(); // 返回 true
circularQueue.enQueue(4); // 返回 true
circularQueue.Rear(); // 返回 4

解题思路：

根据题目要求设计一个循环队列，需要满足以下要求：
在这里插入图片描述

最终代码1：

通过额外开辟一个空间，解决空和满的冲突问题。

typedef struct {int* a;int head;//指向头int tail;//指向尾的下一个int k;
} MyCircularQueue;MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));obj->a = (int*)malloc(sizeof(int) * (k + 1));obj->head = 0;obj->tail = 0;obj->k = k;return obj;
}
//是否为空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj->head == obj->tail;
}
//是否已满
bool myCircularQueueIsFull(MyCircularQueue* obj) {return (obj->tail + 1) % (obj->k + 1) == obj->head;
}
//插入
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if (myCircularQueueIsFull(obj)){return false;}obj->a[obj->tail] = value;obj->tail++;obj->tail = (obj->tail) % (obj->k + 1);return true;}
//删除
bool myCircularQueueDeQueue(MyCircularQueue* obj) {if (myCircularQueueIsEmpty(obj)){return false;}obj->head++;obj->head = (obj->head) % (obj->k + 1);return true;
}
//不为空取首元素
int myCircularQueueFront(MyCircularQueue* obj) {if (myCircularQueueIsEmpty(obj)){return -1;}return obj->a[obj->head];
}
//不为空取尾元素
int myCircularQueueRear(MyCircularQueue* obj) {if (myCircularQueueIsEmpty(obj)){return -1;}return obj->a[(obj->tail + obj->k) % (obj->k + 1)];
}void myCircularQueueFree(MyCircularQueue* obj) {free(obj->a);free(obj);
}

最终代码2：

通过增加一个size来判断队列是否为空或满。

typedef struct {int* a;int phead;int ptail;int k;int size;
} MyCircularQueue;MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));obj->a = (int*)malloc(sizeof(int)*k);obj->phead = 0;obj->ptail = 0;obj->k = k;obj->size = 0;return obj;
}
//是否为空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj->size == 0;}
//是否已满
bool myCircularQueueIsFull(MyCircularQueue* obj) {return obj->size == obj->k;
}//插入
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if(myCircularQueueIsFull(obj)){return false;}else{if(myCircularQueueIsEmpty(obj)){obj->a[obj->phead] = value;}obj->a[obj->ptail] = value;obj->ptail++;obj->ptail %= obj->k;obj->size++;return true;}
}
//删除
bool myCircularQueueDeQueue(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj)){return false;}else{obj->phead = (obj->phead+obj->k+1)%obj->k;obj->size--;return true;}
}
//取首元素
int myCircularQueueFront(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj)){return -1;}return obj->a[obj->phead];
}
//取尾元素
int myCircularQueueRear(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj)){return -1;}else{return obj->a[(obj->ptail+obj->k-1)%obj->k];}
}void myCircularQueueFree(MyCircularQueue* obj) {free(obj->a);free(obj);
}