?本題重點(diǎn)：
1. 選擇合適的數(shù)據(jù)結(jié)構(gòu)
2. 針對選擇的數(shù)據(jù)結(jié)構(gòu)判斷“空”和“滿”
這兩點(diǎn)是不分先后次序的，在思考時應(yīng)該被綜合起來。事實(shí)上，無論我們選擇鏈表還是數(shù)組，最終都能實(shí)現(xiàn)題中描述的“循環(huán)隊(duì)列”的功能，只不過選擇不同結(jié)構(gòu)時，我們面臨和需要解決的問題不同。
一、思路
1. 數(shù)組實(shí)現(xiàn)隊(duì)列。定義變量 front 標(biāo)識隊(duì)頭，變量 rear 標(biāo)識隊(duì)尾。
數(shù)組設(shè)計(jì)循環(huán)隊(duì)列的好處：
1. 找隊(duì)尾元素方便；使用鏈表實(shí)現(xiàn)時，需要找尾。
2. 循環(huán)實(shí)現(xiàn)方便，通過控制下標(biāo)即可完成循環(huán)。
2. 初始時，front = rear = 0，每次插入一個元素，rear向后走一位。
3. 判斷“空” 和 “滿”。如果 front 和 rear 下標(biāo)相同，隊(duì)列為空，還是滿？
4. 理解（rear + 1）% （k + 1）== front 。
若隊(duì)列已滿，則rear 的下一個位置為 front。
此外，每一次插入數(shù)據(jù) 或者 刪除數(shù)據(jù) 后，都要進(jìn)行取模操作：
防止 front 和 rear 走出實(shí)際數(shù)組的范圍，造成數(shù)組越界。
二、功能模塊實(shí)現(xiàn)?
1.?MyCircularQueue(k): 設(shè)置隊(duì)列長度為 k
typedef struct {
int* a; // 指向的空間用來存儲元素
int front;
int rear;
int k;
} MyCircularQueue;
?
MyCircularQueue* myCircularQueueCreate(int k) {
MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
obj->front = obj->rear = 0;
obj->k = k;
obj->a = (int*)malloc(sizeof(int) * (k + 1));
// 多創(chuàng)建1個空位，
// 該位置不用來存儲元素，僅用于判斷隊(duì)列“空”和“滿”
return obj;
}2.?isEmpty(): 檢查循環(huán)隊(duì)列是否為空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
if(obj->rear == obj->front)
return true;
else
return false;
}3.?isFull():?檢查循環(huán)隊(duì)列是否已滿
bool myCircularQueueIsFull(MyCircularQueue* obj) {
if((obj->rear + 1) % (obj->k + 1) == obj->front)
return true;
else
return false;
}4.?enQueue(value):?向循環(huán)隊(duì)列插入一個元素。
如果成功插入則返回真。
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
if(myCircularQueueIsFull(obj))
return false;
else
{
obj->a[obj->rear] = value;
obj->rear++;
obj->rear %= obj->k + 1;
return true;
}
}5.?deQueue():?從循環(huán)隊(duì)列中刪除一個元素。
如果成功刪除則返回真。
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj))
return false;
else
{
obj->front++;
obj->front %= obj->k + 1;
return true;
}
}?6.?Front:?從隊(duì)首獲取元素。
如果隊(duì)列為空，返回 -1 。文章來源：http://www.zghlxwxcb.cn/news/detail-696010.html
int myCircularQueueFront(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj))
return -1;
else
return obj->a[obj->front];
} 7.?Rear:?獲取隊(duì)尾元素。
如果隊(duì)列為空，返回 -1 。?文章來源地址http://www.zghlxwxcb.cn/news/detail-696010.html
int myCircularQueueRear(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj))
return -1;
else
return obj->a[(obj->rear + (obj->k + 1) - 1) % (obj->k + 1)];
}8. QueueFree: 銷毀循環(huán)隊(duì)列
void myCircularQueueFree(MyCircularQueue* obj) {
free(obj->a);
free(obj);
}?
三、所有代碼
typedef struct {
int* a;
int front;
int rear;
int k;
} MyCircularQueue;
MyCircularQueue* myCircularQueueCreate(int k) {
MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
obj->front = obj->rear = 0;
obj->k = k;
obj->a = (int*)malloc(sizeof(int) * (k + 1));
return obj;
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
if(obj->rear == obj->front)
return true;
else
return false;
}
bool myCircularQueueIsFull(MyCircularQueue* obj) {
if((obj->rear + 1) % (obj->k + 1) == obj->front)
return true;
else
return false;
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
if(myCircularQueueIsFull(obj))
return false;
else
{
obj->a[obj->rear] = value;
obj->rear++;
obj->rear %= obj->k + 1;
return true;
}
}
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj))
return false;
else
{
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 + 1) - 1) % (obj->k + 1)];
}
void myCircularQueueFree(MyCircularQueue* obj) {
free(obj->a);
free(obj);
}到了這里，關(guān)于leetcode622-設(shè)計(jì)循環(huán)隊(duì)列的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
