前言:

? ? ? ? 隊列是一種具有先進先出特性的結構,但是當數據出隊列以后,前面的空間就無法再次利用了,循環隊列就可以解決這個問題

一:概念及結構:

1.循環隊列概念

????????循環隊列是一種線性數據結構，其操作表現基于 FIFO（先進先出）原則并且隊尾被連接在隊首之后以形成一個循環.

2.循環隊列結構

? ? ? ? 循環隊列可以使用數組實現也可以使用鏈表實現,但是還是建議使用數組實現.另外在給數組開辟空間時,要比隊列實際長度多一個,如果開辟空間和隊列存儲數據的長度一樣的話,在判斷隊列為空和隊列為滿時,兩者都為 front==rear 會出現一樣的情況導致無法判斷,如

所以必須多開辟一個空間,這個空間不存儲數據,這樣就可以區分出兩種情況

結構定義:

? ? ? ? front用于維護隊頭,指向隊頭元素位置,back用于維護隊尾,總是指向隊尾元素的下一個位置,k表示隊列實際存數據的長度

ps:循環隊列的長度是固定的

typedef struct {int *a;int front; int back;int k;  //隊列大小
} MyCircularQueue;

二:功能實現

1.入隊:

????首先要判斷隊列是否已滿，再進行入隊的操作，入隊操作需要考慮索引循環的問題，當索引越界，需要讓它變成最小值

? ? ? ? 如果入隊是這種情況,直接在隊尾處插入數據,back++即可

? ? ? ? 但是如果碰到這種情況,back就不能簡單加一就完事了了,還需要將back重新指向數組剛開始的空間,不然就體現不出循環的特點了

?????????所以在隊尾插入數據back++后,進行?back=(back)%(k+1)?就可以使back重新指向數組起始位置(這里要注意的是,我定義的k是隊列不帶多開辟的那一個空間的長度)

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if(myCircularQueueIsFull(obj))//入隊前先判斷是否還有空間return false;obj->a[obj->back]=value;obj->back++;obj->back%=(obj->k+1);return true;
}

2.出隊:

? ? ? ?首先判斷隊列是否為空,在進行出隊操作,出隊也需要考慮front的索引問題

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

3.取隊頭元素

????????front指向的就是隊頭元素

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

4.取隊尾元素

? ? ? ? ? 由于back始終指向隊尾的下一個元素,在一般情況下直接返回back-1所指向的元素即可,但是有一種特殊情況,如果此時back指向的是數組起始位置的話,訪問back-1所指向的元素就會越界,所以這里也涉及循環的問題

方法一: 把特殊情況分離出來

int myCircularQueueRear(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return -1;if(obj->back==0)return obj->a[obj->k];elsereturn obj->a[obj->back-1];
}

方法二: 兩種情況統一處理

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

5.判空

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj->front==obj->back;
}

6.判滿

bool myCircularQueueIsFull(MyCircularQueue* obj) {return (obj->back+1)%(obj->k+1)==obj->front;
}

7.銷毀隊列

void myCircularQueueFree(MyCircularQueue* obj) {free(obj->a);obj->front=obj->back=0;obj->k=0;
}

8.求隊列當前元素個數

當back在front之后時,back-front就可獲得當前隊列元素個數,但是當back在front前面時,back+(k+1)

可以讓back指向不處理循環問題本身應該指向的位置

int myCircularQueueSize(MyCircularQueue* obj) {return (obj->back+(k+1)-obj->front)%(k+1);
}