? ?文章目錄

1.循環(huán)隊列的定義

2.循環(huán)隊列的判空判滿

3.創(chuàng)建隊列并初始化

4.入隊和出隊

5. 返回隊尾隊首元素

6.釋放循環(huán)隊列

---

1.循環(huán)隊列的定義

定義：存儲隊列元素的表從邏輯上被視為一個環(huán)。

? ? ? ?

我們此次實現(xiàn)的循環(huán)隊列，采用順序表

typedef struct {int*a;int front;int rear;int k;} MyCircularQueue;

本質(zhì)上是一個出入受限的順序表，那我們是怎么實現(xiàn)他的環(huán)狀結(jié)構的呢？畢竟順序表是一個線性的結(jié)構而不是環(huán)狀的。

答? 他用取模運算剛好在存儲空間上變成了“環(huán)狀”。

例如：我們要走一個環(huán)狀順序表

如果我們將rear=1；front=2在邏輯上我們可以正常移動，但其實我們物理存儲上的指針已經(jīng)溢出了，所以我們剛好可以取模來控制指針的移動。

如果我們尾指針前進一步就可以（Q.rear+1）% k，剛好可以到達front的位置。

2.循環(huán)隊列的判空判滿

如圖我們可以看到，此時rear==front既可以是判空的條件，也可以是判滿的條件，那我們應該怎么區(qū)分呢？有三種方法://這里的指針變量會和題目中的不太一樣，但是判斷邏輯相同

1.犧牲一個單元來進行區(qū)分

隊滿：（Q.rear+1）%MaxSize ==Q.front；

隊空：? ?Q.front==Q.rear

2.設置一個Size表示隊列元素長度來判斷。

隊滿：Size==MaxSize;

隊空：Size==0

3.設置一個 tag標記

tag==0&&?Q.front==Q.rear,隊空；

tag==1&&?Q.front==Q.rear,隊滿。

• isEmpty(): 檢查循環(huán)隊列是否為空。
• isFull(): 檢查循環(huán)隊列是否已滿。

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {assert(obj);if(obj->rear==obj->front ){return  true;}return false ;
}bool myCircularQueueIsFull(MyCircularQueue* obj) {assert(obj);if((obj->rear+1)%(obj->k+1)==obj->front ){return  true;}return false ;
}

3.創(chuàng)建隊列并初始化

MyCircularQueue(k): 構造器，設置隊列長度為 k?

MyCircularQueue* myCircularQueueCreate(int k)
{MyCircularQueue*obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));//創(chuàng)建一個循環(huán)的隊列結(jié)構體指針節(jié)點obj->a=(int*)malloc(sizeof(int)*(k+1)) ;//隊列長度為k，但是要多一個空間用來判斷空還是滿obj->front=obj->rear=0;obj->k=k;return obj;
}

? ? 隊列長度為k，但是要多一個空間用來判斷空還是滿?，所以我們用的是第一種判空判滿策略，犧牲一個存儲空間

4.入隊和出隊

入隊操作:? ? obj->a[obj->rear]=value;
? ? ? ? ? ? ? ? ? ? obj->rear=(obj->rear+1)%(obj->k+1);//? 先賦值再移動指針

出隊操作：? ?obj->front=(obj->front+1)%(obj->k+1);// 直接移動指針

• enQueue(value): 向循環(huán)隊列插入一個元素。如果成功插入則返回真。
• deQueue(): 從循環(huán)隊列中刪除一個元素。如果成功刪除則返回真。

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

5. 返回隊尾隊首元素

• Front: 從隊首獲取元素。如果隊列為空，返回 -1 。
• Rear: 獲取隊尾元素。如果隊列為空，返回 -1 。

int myCircularQueueFront(MyCircularQueue* obj) {assert(obj);if (myCircularQueueIsEmpty(obj)){return -1;}return obj->a[obj->front];}int myCircularQueueRear(MyCircularQueue* obj) {assert(obj);if (myCircularQueueIsEmpty(obj)){return -1;}else{int rear=obj->rear==0 ? obj->k : obj->rear-1;return obj->a[rear];  }
}

int rear=obj->rear==0 ? obj->k : obj->rear-1;? 由于隊尾后面還有一個用于判空判滿的空間，如果rear剛好指向這片空間，他實際上是指向的真正的隊尾下標為k；如果不為0說明他指向的空間為正常的前驅(qū)結(jié)點。

?6.釋放循環(huán)隊列

?切記:? 先釋放結(jié)構體指針指向的創(chuàng)建的隊列所在的空間，再去釋放結(jié)構體指針的空間。

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