一、概念與結構

循環隊列是一種特殊的隊列，首尾相連成環，也叫環形隊列。環形隊列具有以下三個特點：

（1）隊頭刪除數據，隊尾插入數據。

（2）給定固定的空間，使用過程中不能擴容。

（3）環形隊列滿了之后，不能繼續插入數據（即插入數據失敗）。

環形隊列可以使用數組實現，也可以使用循環鏈表實現。使用數組實現的話更簡單。定義頭指針front和尾指針rear。當rear指向最后一個元素的時候，我們只需要讓rear % 空間大小就可以讓rear指針重新指向front。

但是，這樣又帶來一個問題，當環形隊列為空時：front == rear；當環形隊列滿了：front == rear。那么，我們該如何區分環形隊列是空還是滿呢？我們可以在結構體中再定義一個size變量，用于統計環形隊列中有效數據的個數。但是這樣又要額外開辟四個字節的空間，有沒有更好的辦法呢？我們額外申請一塊空間，但這塊空間不保存任何數據，這樣就不用額外增加結構體的成員變量。

此時，rear == front表示環形隊列為空；如果滿足（rear + 1）%（k + 1）== front，表示環形隊列滿了。

二、題目描述?

https://leetcode.cn/problems/design-circular-queue

三、參考代碼??

typedef struct 
{int* arr;int front;//隊頭int rear;//隊尾int capacity;//循環隊列的空間大小
} MyCircularQueue;MyCircularQueue* myCircularQueueCreate(int k) 
{MyCircularQueue* pq = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));//申請k+1個空間pq->arr = (int*)malloc((k + 1) * sizeof(int));pq->front = pq->rear = 0;pq->capacity = k;return pq;
}bool myCircularQueueIsEmpty(MyCircularQueue* obj) 
{return obj->front == obj->rear;
}bool myCircularQueueIsFull(MyCircularQueue* obj) 
{return (obj->rear + 1) % (obj->capacity + 1) == obj->front;
}
//向循環隊列中插入一個元素
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) 
{//先判斷是否滿了if(myCircularQueueIsFull(obj)){return false;}//沒有滿else{obj->arr[obj->rear++] = value;obj->rear %= obj->capacity + 1;return true;}
}
//從循環隊列中刪除一個元素
bool myCircularQueueDeQueue(MyCircularQueue* obj) 
{if(myCircularQueueIsEmpty(obj)){return false;}//非空else{obj->front++;obj->front %= obj->capacity + 1;return true;}
}int myCircularQueueFront(MyCircularQueue* obj) 
{if(myCircularQueueIsEmpty(obj)){return -1;}return obj->arr[obj->front];
}int myCircularQueueRear(MyCircularQueue* obj) 
{if(myCircularQueueIsEmpty(obj)){return -1;}int prev = obj->rear - 1;if(obj->rear == 0){prev = obj->capacity;}return obj->arr[prev];
}void myCircularQueueFree(MyCircularQueue* obj) 
{if(obj->arr)free(obj->arr);obj->arr = NULL;obj->front = obj->rear = obj->capacity = 0;free(obj);obj = NULL;
}/*** 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);
*/