柚子快報邀請碼778899分享：數(shù)據(jù)結(jié)構(gòu) 設(shè)計循環(huán)隊列

http://yzkb.51969.com/

目錄

循環(huán)隊列：

題目：

解析：

判空：

判滿：

原理：

代碼實現(xiàn)

代碼講解

?myCircularQueueCreate

?myCircularQueueIsEmpty

myCircularQueueIsFull

myCircularQueueEnQueue

需要注意的是

?myCircularQueueDeQueue

需要注意的是

myCircularQueueFront

myCircularQueueRear

減：

myCircularQueueFree

最后

循環(huán)隊列：

將隊列連接成一個環(huán)狀結(jié)構(gòu)，內(nèi)部空間大小固定。

一般采用數(shù)組隊列

題目：

設(shè)計你的循環(huán)隊列實現(xiàn)。 循環(huán)隊列是一種線性數(shù)據(jù)結(jié)構(gòu)，其操作表現(xiàn)基于 FIFO（先進(jìn)先出）原則并且隊尾被連接在隊首之后以形成一個循環(huán)。它也被稱為“環(huán)形緩沖器”。

循環(huán)隊列的一個好處是我們可以利用這個隊列之前用過的空間。在一個普通隊列里，一旦一個隊列滿了，我們就不能插入下一個元素，即使在隊列前面仍有空間。但是使用循環(huán)隊列，我們能使用這些空間去存儲新的值。

你的實現(xiàn)應(yīng)該支持如下操作：

MyCircularQueue(k): 構(gòu)造器，設(shè)置隊列長度為 k 。Front: 從隊首獲取元素。如果隊列為空，返回 -1 。Rear: 獲取隊尾元素。如果隊列為空，返回 -1 。enQueue(value): 向循環(huán)隊列插入一個元素。如果成功插入則返回真。deQueue(): 從循環(huán)隊列中刪除一個元素。如果成功刪除則返回真。isEmpty(): 檢查循環(huán)隊列是否為空。isFull(): 檢查循環(huán)隊列是否已滿。

解析：

解決此問題，需要明白環(huán)形隊列的判空及判滿原理。

? ??int k; ? ? ?//隊列長度 k ，則空間為 k + 1

? ? int front; ? ? ?//頭標(biāo)

? ? int rear; ? ? ? //尾標(biāo)

? ? int* a; ? ? //用指針會更合適

建立一個結(jié)構(gòu)體，包含如上成員。

判空：

front == rear

判滿：

（rear + 1） %（k + 1)? == front

??尾標(biāo) + 1?? ??? ?? ?? 空間大小? ??? ??頭標(biāo)

原理：

插入，rear后移。因此rear最終會指向末尾數(shù)據(jù)的下一個位置。（插入完再后移）

超出數(shù)組之后，取模數(shù)組大小，實現(xiàn)T的周期性運(yùn)轉(zhuǎn)。（模數(shù)據(jù)，比length小的時候，不會有影

響）

當(dāng)REAR + 1 = FRONT 時，K + 1個空間，只能放K個數(shù)據(jù)，否則不能判空、判滿。

代碼實現(xiàn)

MyCircularQueue* myCircularQueueCreate(int k) { //包含的形參k，可以直接使用

MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));

obj->a = (int*)malloc( (k + 1) * sizeof(int) );

obj->front = obj->rear = 0; //下標(biāo)等元素的初始化

obj->k = k;

return obj;

}

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {

return obj->front == obj->rear;

}

bool myCircularQueueIsFull(MyCircularQueue* obj) {

//判斷是 ==

return (obj->rear + 1) % (obj->k + 1) == obj->front; // K是結(jié)構(gòu)成員，需要->訪問

}

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {

if (myCircularQueueIsFull(obj))

return false;

obj->a[obj->rear++] = value; //先使用，后++

obj->rear %= (obj->k + 1); //在數(shù)組中循環(huán)

return true;

}

bool myCircularQueueDeQueue(MyCircularQueue* obj) {

if (myCircularQueueIsEmpty(obj))

return false;

obj->front++;

obj->front %= (obj->k + 1);

return true;

}

int myCircularQueueFront(MyCircularQueue* obj) {

if (myCircularQueueIsEmpty(obj))

return -1;

return obj->a[obj->front];

}

int myCircularQueueRear(MyCircularQueue* obj) {

if (myCircularQueueIsEmpty(obj))

return -1;

return obj->a[(obj->rear - 1 + obj->k + 1 ) % (obj->k + 1)]; //obj->rear是一個整體，應(yīng)該都括起來

}

void myCircularQueueFree(MyCircularQueue* obj) {

free(obj->a); //先釋放內(nèi)部空間

free(obj);

}

代碼講解

?myCircularQueueCreate

初始化:對結(jié)構(gòu)內(nèi)的所有成員都要初始化（1.空間 2.int類型的數(shù)據(jù)）

?myCircularQueueIsEmpty

判空

front == rear

myCircularQueueIsFull

判滿

myCircularQueueEnQueue

壓入數(shù)據(jù)

需要注意的是

?1.obj->a[obj->rear++] = value; ? ?//先使用，后++? ? ? ? ? ，不要忘記++

? ?2.obj->rear %= (obj->k + 1); ? ? ? //在數(shù)組中循環(huán)

為了防止下標(biāo)再次解引用的時候引發(fā)數(shù)組越界問題，可以讓下標(biāo) %?容量，再次進(jìn)入周期

?myCircularQueueDeQueue

刪除數(shù)據(jù)

obj->front++;? ? ? ? ? ? ? ??

obj->front %= (obj->k + 1);

需要注意的是

對于數(shù)組隊列

不需要free，只需要讓頭標(biāo)++就可。?

為了防止front下標(biāo)走出數(shù)組，需要 % 空間大小，讓其進(jìn)入循環(huán)。

myCircularQueueFront

先判空，有元素直接取

myCircularQueueRear

?return obj->a[(obj->rear - 1 + obj->k + 1 ? ) % (obj->k + 1)]; ? ? ? //obj->rear是一個整體，應(yīng)該都括起來

減：

需要注意的是，找尾元素的時候，其下標(biāo)尾 rear - 1。但是當(dāng)rear的下標(biāo)為0，將會出現(xiàn)越界。

此時 （下標(biāo) + 周期） % （周期） 可以解決問題。當(dāng)（下標(biāo) + 周期）?大小小于? 周期時，由于取模，不會產(chǎn)生影響！

myCircularQueueFree

釋放的時候，應(yīng)該先釋放內(nèi)部空間，再釋放外部空間！

最后

當(dāng)需要訪問? ? K 等結(jié)構(gòu)成員變量時，需要->解引用訪問，不能直接使用！

柚子快報邀請碼778899分享：數(shù)據(jù)結(jié)構(gòu) 設(shè)計循環(huán)隊列

http://yzkb.51969.com/

文章來源