1.設計要求
設計你的回圈佇列實作， 回圈佇列是一種線性資料結構，其操作表現基于 FIFO（先進先出）原則并且隊尾被連接在隊首之后以形成一個回圈，它也被稱為“環形緩沖器”，
你的實作應該支持如下操作：
MyCircularQueue(k): 構造器，設定佇列長度為 k ，
Front: 從隊首獲取元素，如果佇列為空，回傳 -1 ，
Rear: 獲取隊尾元素，如果佇列為空，回傳 -1 ，
enQueue(value): 向回圈佇列插入一個元素，如果成功插入則回傳真，
deQueue(): 從回圈佇列中洗掉一個元素，如果成功洗掉則回傳真，
isEmpty(): 檢查回圈佇列是否為空，
isFull(): 檢查回圈佇列是否已滿，
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/design-circular-queue
2.設計思路流程
1.我們先采用鏈表的方法實作，使鏈表的尾結點的指標指向頭節點，這樣就形成了一個回圈鏈表，插入資料時插入到尾結點，采用尾插法，但是這樣存在一個問題：空和滿的條件是一樣的，無法判斷慷訓是滿，此時判斷條件都是head==tail，
2.上述方法不可取，我們空出來一個結點的方法，比如說有4個結點，但是我們只存盤三個資料，判斷空的條件還是head==tail，但是我修改判斷滿的條件為尾結點的下一個是頭節點為滿，插入資料我們依然采用尾插法，
3.以上方法均采用的是鏈表的形式，鏈表上在物理結果和邏輯結構上都是連續的，都是回圈的，這使讀者更加直觀了解回圈佇列的實作，但是回圈佇列所存盤的元素是一定的k個，不需要動態開辟記憶體空間，我們可以考慮采用順序表來實作，順序表在物理結構上并不連續，但是在邏輯結構上是連續的，
3.代碼實作
typedef struct
{
int* a;
int k;//佇列對多能存盤多少資料
int front;//頭
int tail;//尾（隊尾資料下一個）
} MyCircularQueue;
（1）MyCircularQueue(k): 構造器，設定佇列長度為 k
MyCircularQueue* myCircularQueueCreate(int k)
{
MyCircularQueue* obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
obj->a=(int*)malloc(sizeof(int)*(k+1));
obj->front=0;
obj->tail=0;
obj->k=k;
return obj;
}
（2）Front: 從隊首獲取元素，如果佇列為空，回傳 -1
int myCircularQueueFront(MyCircularQueue* obj)
{
if(myCircularQueueIsEmpty(obj))
{
return -1;
}
else
{
return obj->a[obj->front];
}
}
（3）Rear: 獲取隊尾元素，如果佇列為空，回傳 -1
int myCircularQueueRear(MyCircularQueue* obj)
{
if(myCircularQueueIsEmpty(obj))
{
return -1;
}
else
{
int tailPrev=obj->tail-1;
if(tailPrev==-1)
{
tailPrev=obj->k;
}
return obj->a[tailPrev];
}
}
（4）enQueue(value): 向回圈佇列插入一個元素，如果成功插入則回傳真
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value)
{
if(myCircularQueueIsFull(obj))
{
return false;
}
else
{
obj->a[obj->tail]=value;
++obj->tail;
if(obj->tail==obj->k+1)
{
obj->tail=0;
}
}
return true;
}
（5）deQueue(): 從回圈佇列中洗掉一個元素，如果成功洗掉則回傳真
bool myCircularQueueDeQueue(MyCircularQueue* obj)
{
if(myCircularQueueIsEmpty(obj))
{
return false;
}
else
{
++obj->front;
if(obj->front==obj->k+1)
{
obj->front=0;
}
}
return true;
}
（6）isEmpty(): 檢查回圈佇列是否為空
bool myCircularQueueIsEmpty(MyCircularQueue* obj)
{
return obj->front==obj->tail;
}
（7）isFull(): 檢查回圈佇列是否已滿
bool myCircularQueueIsFull(MyCircularQueue* obj)
{
int tailNext=obj->tail+1;
if(tailNext==obj->k+1)
{
tailNext=0;
}
return tailNext==obj->front;
}
（8）Free(): 銷毀回圈佇列
void myCircularQueueFree(MyCircularQueue* obj)
{
free(obj->a);
free(obj);
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/281680.html
標籤：其他
上一篇：第三講：工業網路——物理介質