一.前言

上一次我們分享了關于隊列的基本實現——https://blog.csdn.net/yiqingaa/article/details/139033067?spm=1001.2014.3001.5502

現在我們將使用隊列知識來解決問題——設計循環隊列：https://leetcode.cn/problems/design-circular-queue/submissions/533299335

二.正文

1.1題目描述

?

1.2題目分析

?

本題給了我們七個操作需求，需要我們將這些函數功能實現出來。

對于這道題，假如我們是使用數組來實現隊列，在這里我們可以事先模擬走一下：

?

那么我們如何解決這個問題呢。在這里我們我們可以通過多創建一個空間的方式解決這個問題。

?

（1）定義棧的結構

typedef struct {int* a;//a是int*類型的數組int k;//k代表了我們的數組長度int head;//head會指向我們的頭元素（head在這里不是指針，可以當成另類的下標）int tail;//tail在我們數據的后一個位置（tail在這里不是指針，可以當成另類的下標）
} MyCircularQueue;

假如k是4，數組有1，2，3，4這些數據。那么就有：

?

?（2）創建我們的隊列

MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));obj->a=(int*)malloc(sizeof(int)*(k+1));if(obj->a==NULL){perror("malloc fail!");}obj->k=k;obj->head=obj->tail=0;return obj;
}

我們首先為我們的隊列結構體申請了sizeof(MyCircularQueue)字節大小的空間。

然后又為了我們數組申請了sizeof(int)*(k+1)字節大小的空間。

用我們的結構體成員k接受形參k的值。

并讓head，tail都初始化為0。

（3）判斷隊列是否為空

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {if(obj->head==obj->tail)return true;return false;
}

這里我們先實現了判斷隊列是否為空的函數功能，因為這個函數功能在后面實現數據插入和刪除中都需要用到，因此，在這里我們就先實現了。

?（4）判斷隊列是否數據已滿

bool myCircularQueueIsFull(MyCircularQueue* obj) {if((obj->tail+1)%(obj->k+1)==obj->head)return true;return false;
}

?（5）隊列數據的插入

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if(myCircularQueueIsFull(obj)==true)return false;
obj->a[obj->tail]=value;
obj->tail++;
obj->tail=(obj->tail)%(obj->k+1);
return true;
}

這里我們先進行了判斷，如果隊列數據已經滿了，就插不了數據了，直接返回false即可。

在這里，我們需要額外注意這行代碼：obj->tail=(obj->tail)%(obj->k+1);

相信同學們看到這里已經發現了，我們上述代碼中很多都用到了取余%的應用，這是為了讓head和tail能正常的循環。

（6） 隊列數據的刪除

bool myCircularQueueDeQueue(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj)==true)return false;obj->head++;obj->head=(obj->head)%(obj->k+1);return true;
}

這里我們需要知道，如果隊列沒有數據的時候，我們不能進行數據刪除，因為本來隊列都沒數據了，再刪除就會出現內存泄露的問題。

（7） 取出隊頭的數據

int myCircularQueueFront(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj)==true)return -1;return obj->a[obj->head];
}

?（8）取出隊尾的數據

int myCircularQueueRear(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj)==true)return -1;return obj->a[(obj->tail-1+obj->k+1)%(obj->k+1)];
}

?（9）銷毀我們創建的對列

void myCircularQueueFree(MyCircularQueue* obj) {free(obj->a);free(obj);
}

?1.3代碼實現

typedef struct {int* a;int k;int head;int tail;
} MyCircularQueue;MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));obj->a=(int*)malloc(sizeof(int)*(k+1));if(obj->a==NULL){perror("malloc fail!");}obj->k=k;obj->head=obj->tail=0;return obj;
}bool myCircularQueueIsEmpty(MyCircularQueue* obj) {if(obj->head==obj->tail)return true;return false;
}
bool myCircularQueueIsFull(MyCircularQueue* obj) {if((obj->tail+1)%(obj->k+1)==obj->head)return true;return false;
}bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if(myCircularQueueIsFull(obj)==true)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)==true)return false;obj->head++;obj->head=(obj->head)%(obj->k+1);return true;
}int myCircularQueueFront(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj)==true)return -1;return obj->a[obj->head];
}int myCircularQueueRear(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj)==true)return -1;return obj->a[(obj->tail-1+obj->k+1)%(obj->k+1)];
}void myCircularQueueFree(MyCircularQueue* obj) {free(obj->a);free(obj);
}/*** Your MyCircularQueue struct will be instantiated and called as such:* MyCircularQueue* obj = myCircularQueueCreate(k);* bool param_1 = myCircularQueueEnQueue(obj, value);* bool param_2 = myCircularQueueDeQueue(obj);* int param_3 = myCircularQueueFront(obj);* int param_4 = myCircularQueueRear(obj);* bool param_5 = myCircularQueueIsEmpty(obj);* bool param_6 = myCircularQueueIsFull(obj);* myCircularQueueFree(obj);
*/

---

以上代碼就是我們在力扣網上運行的代碼。

三.結言

本題的分享就到這了，有興趣的小伙伴，能不能給個三連，真的求求了。

帥哥美女們，咱們下期再見。