985短網(wǎng)址生成器常州seo
目錄
一、題目：
二、思路詳解：
1.循環(huán)隊(duì)列的存儲(chǔ)定義
2.循環(huán)隊(duì)列的創(chuàng)建
3.循環(huán)隊(duì)列的判空與判斷情況
(1) 循環(huán)隊(duì)列的判空:
?(2) 循環(huán)隊(duì)列的判滿
4.循環(huán)隊(duì)列元素的插入
5.循環(huán)隊(duì)列元素的刪除
6.獲取隊(duì)頭元素
7.獲取隊(duì)尾元素?
8.循環(huán)隊(duì)列釋放
三、完整代碼展示：
一、題目：
設(shè)計(jì)你的循環(huán)隊(duì)列實(shí)現(xiàn)。 循環(huán)隊(duì)列是一種線性數(shù)據(jù)結(jié)構(gòu)，其操作表現(xiàn)基于 FIFO（先進(jìn)先出）原則并且隊(duì)尾被連接在隊(duì)首之后以形成一個(gè)循環(huán)。它也被稱為“環(huán)形緩沖器”。
循環(huán)隊(duì)列的一個(gè)好處是我們可以利用這個(gè)隊(duì)列之前用過(guò)的空間。在一個(gè)普通隊(duì)列里，一旦一個(gè)隊(duì)列滿了，我們就不能插入下一個(gè)元素，即使在隊(duì)列前面仍有空間。但是使用循環(huán)隊(duì)列，我們能使用這些空間去存儲(chǔ)新的值。
你的實(shí)現(xiàn)應(yīng)該支持如下操作：
MyCircularQueue(k): 構(gòu)造器，設(shè)置隊(duì)列長(zhǎng)度為 k 。Front: 從隊(duì)首獲取元素。如果隊(duì)列為空，返回 -1 。Rear: 獲取隊(duì)尾元素。如果隊(duì)列為空，返回 -1 。enQueue(value): 向循環(huán)隊(duì)列插入一個(gè)元素。如果成功插入則返回真。deQueue(): 從循環(huán)隊(duì)列中刪除一個(gè)元素。如果成功刪除則返回真。isEmpty(): 檢查循環(huán)隊(duì)列是否為空。isFull(): 檢查循環(huán)隊(duì)列是否已滿。難度：中等
題目鏈接：622. 設(shè)計(jì)循環(huán)隊(duì)列
示例：
MyCircularQueue circularQueue = new MyCircularQueue(3); // 設(shè)置長(zhǎng)度為 3 circularQueue.enQueue(1); ?// 返回 true circularQueue.enQueue(2); ?// 返回 true circularQueue.enQueue(3); ?// 返回 true circularQueue.enQueue(4); ?// 返回 false，隊(duì)列已滿 circularQueue.Rear(); ?// 返回 3 circularQueue.isFull(); ?// 返回 true circularQueue.deQueue(); ?// 返回 true circularQueue.enQueue(4); ?// 返回 true circularQueue.Rear(); ?// 返回 4
題目解析：就是根據(jù)題中給的接口進(jìn)行函數(shù)的實(shí)現(xiàn)。要求我們實(shí)現(xiàn)一個(gè)循環(huán)隊(duì)列。
用心閱讀下方會(huì)有很大的收獲。?
二、思路詳解：
1.循環(huán)隊(duì)列的存儲(chǔ)定義
首先我們需要定義出一個(gè)循環(huán)隊(duì)列的存儲(chǔ)定義，這里采用的是使用動(dòng)態(tài)數(shù)組來(lái)進(jìn)行模擬循環(huán)隊(duì)列，根據(jù)題中給出的接口返回類型，我們可以知道循環(huán)隊(duì)列的數(shù)據(jù)類型為int 。
其次，還需定義兩個(gè)記錄數(shù)組的下標(biāo)，一個(gè)記錄隊(duì)列的隊(duì)頭，另一個(gè)記錄隊(duì)列的隊(duì)尾(也就是指向要入隊(duì)的下一個(gè)元素的位置)。另外還要提供一個(gè)表示要存儲(chǔ)數(shù)據(jù)的具體個(gè)數(shù)。
如圖：
代碼：
//采用動(dòng)態(tài)數(shù)組的形式來(lái)模擬循環(huán)隊(duì)列
typedef struct {int* a; //指向數(shù)組int front; //隊(duì)頭int tail; //隊(duì)尾int k; //數(shù)據(jù)個(gè)數(shù)
} MyCircularQueue;2.循環(huán)隊(duì)列的創(chuàng)建
循環(huán)隊(duì)列的創(chuàng)建，先使用malloc進(jìn)行創(chuàng)建一個(gè)?循環(huán)隊(duì)列空間
接著根據(jù)給的數(shù)據(jù)個(gè)數(shù)k讓指針a指向一個(gè)動(dòng)態(tài)數(shù)組，在分別對(duì)front,tail,k進(jìn)行初始化，注意tail = 0表示要存放的下一個(gè)數(shù)據(jù)元素的位置，對(duì)動(dòng)態(tài)數(shù)組a開(kāi)辟空間的時(shí)候要多開(kāi)辟一個(gè)空間，避免假溢出的現(xiàn)象。最后一定要返回之前創(chuàng)建的循環(huán)隊(duì)列。
代碼：
//創(chuàng)建長(zhǎng)度為k的循環(huán)隊(duì)列
MyCircularQueue* myCircularQueueCreate(int k) {//使用動(dòng)態(tài)內(nèi)存函數(shù)來(lái)申請(qǐng)內(nèi)存//這里多申請(qǐng)一個(gè)空間的目的是防止假溢出//使用malloc創(chuàng)建一個(gè)循環(huán)隊(duì)列MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));//為循環(huán)隊(duì)列里面的指針a ,讓a指向一個(gè)長(zhǎng)度為k+1的數(shù)組obj->a= (int*)malloc(sizeof(int)*(k+1));obj->front = 0; //隊(duì)頭從數(shù)組的下標(biāo)0開(kāi)始o(jì)bj->tail = 0; //隊(duì)尾指向下一個(gè)元素obj->k = k; //隊(duì)列的長(zhǎng)度為kreturn obj;
}物理存儲(chǔ)情況，如圖：
但是我們一般會(huì)到其循環(huán)的邏輯結(jié)構(gòu)，邏輯存儲(chǔ)，如圖：
?3.循環(huán)隊(duì)列的判空與判斷情況
循環(huán)隊(duì)列的插入和刪除是不可避免的，當(dāng)這之前就需要先完成判和判滿的接口。注意：一定要把判空和判滿的函數(shù)實(shí)現(xiàn)放在隊(duì)列插入和刪除函數(shù)實(shí)現(xiàn)的前面。
(1) 循環(huán)隊(duì)列的判空:
根據(jù)函數(shù)的返回類型是bool，空我們就返回true ,否則返回false。
isEmpty(): 檢查循環(huán)隊(duì)列是否為空。
因?yàn)檫@里采取的是通過(guò)動(dòng)態(tài)數(shù)組來(lái)模擬循環(huán)隊(duì)列，所以隊(duì)列空的條件就是當(dāng)front == tail 的時(shí)候，此時(shí)的循環(huán)隊(duì)列就是空的。
如圖：
代碼：
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {//隊(duì)空，就是隊(duì)頭與隊(duì)尾相同時(shí)return obj->front == obj->tail;
}?(2) 循環(huán)隊(duì)列的判滿
?同樣根據(jù)函數(shù)的返回類型是bool，空我們就返回true ,否則返回false。
isFull(): 檢查循環(huán)隊(duì)列是否已滿。
什么時(shí)候會(huì)滿呢？當(dāng)(tail+1)%(k+1) == front,就是隊(duì)尾下標(biāo)加1模開(kāi)辟空間的個(gè)數(shù)?
可能很多會(huì)對(duì)為什么要多開(kāi)辟一個(gè)空間，原因就在這：對(duì)于隊(duì)列的判滿的情況，
當(dāng)沒(méi)有創(chuàng)建的額外空間，隊(duì)列只有數(shù)據(jù)10 和 11 的情況下，
像上圖就是假溢出現(xiàn)象，這個(gè)隊(duì)列并沒(méi)有滿。
總的來(lái)說(shuō)：
循環(huán)隊(duì)列為了區(qū)分隊(duì)列的空和滿，需要額外增加一個(gè)空的元素來(lái)占據(jù)隊(duì)列的一個(gè)位置，這樣隊(duì)列滿的狀態(tài)就可以通過(guò)頭尾指針相鄰且不重合來(lái)判斷，而不會(huì)出現(xiàn)頭尾指針重合但隊(duì)列實(shí)際上并不滿的情況。同時(shí)循環(huán)隊(duì)列需要對(duì)頭尾指針進(jìn)行模運(yùn)算，如果沒(méi)有額外的空間，那么當(dāng)隊(duì)列最后一個(gè)元素占據(jù)了數(shù)組最后一個(gè)位置時(shí)，下一個(gè)元素就會(huì)從數(shù)組的第一個(gè)位置開(kāi)始，這樣就無(wú)法正確進(jìn)行模運(yùn)算，而增加一個(gè)空的元素可以解決這個(gè)問(wèn)題。
?代碼：
bool myCircularQueueIsFull(MyCircularQueue* obj) {return (obj->tail+1)%(obj->k+1) == obj->front;
}
?4.循環(huán)隊(duì)列元素的插入
enQueue(value): 向循環(huán)隊(duì)列插入一個(gè)元素。如果成功插入則返回真。
插入前判斷是否滿，滿就返回false,接著就是數(shù)據(jù)的插入，插入后，對(duì)tail下標(biāo)進(jìn)行取模(因?yàn)槭欠磸?fù)利用原來(lái)的空間，還有就是避免溢出)，插入成功就返回true。
?代碼：
//插入元素
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {//插入元素前先進(jìn)行判斷是否滿if(myCircularQueueIsFull(obj)){return false;}//插入元素使用尾插obj->a[obj->tail] = value;obj->tail++;//避免tail的下標(biāo)越界obj->tail%=(obj->k+1);return true;
}5.循環(huán)隊(duì)列元素的刪除
?刪除前，要進(jìn)行判斷是否為空。隊(duì)頭減一，進(jìn)行刪除，刪除后取模。
deQueue(): 從循環(huán)隊(duì)列中刪除一個(gè)元素。如果成功刪除則返回真。
?代碼：
//出隊(duì)
bool myCircularQueueDeQueue(MyCircularQueue* obj) {//刪除元素隊(duì)列不能為空if(myCircularQueueIsEmpty(obj)){return false;}//出隊(duì)，頭刪obj->front++;obj->front%=(obj->k+1);return true;
}?6.獲取隊(duì)頭元素
獲取前進(jìn)行判斷，是否為空。
Front: 從隊(duì)首獲取元素。如果隊(duì)列為空，返回 -1??
??代碼：
//獲取隊(duì)首元素
int myCircularQueueFront(MyCircularQueue* obj) {//隊(duì)列不能為空if(myCircularQueueIsEmpty(obj)){return -1; //隊(duì)空返回-1}return obj->a[obj->front];
}7.獲取隊(duì)尾元素?
獲取前進(jìn)行判斷，是否為空。
Rear: 獲取隊(duì)尾元素。如果隊(duì)列為空，返回 -1??
??代碼：
//獲取隊(duì)尾元素
int myCircularQueueRear(MyCircularQueue* obj) {//隊(duì)列不能為空if(myCircularQueueIsEmpty(obj)){return -1; //隊(duì)空返回-1}//注意當(dāng)tail = 0的情況return obj->a[(obj->tail - 1+ obj->k+1)%(obj->k+1)];
}
解釋一下 上述最后一行代碼：
重點(diǎn)：
首先tail是指向要存放下一個(gè)元素的位置，找隊(duì)尾元素時(shí)，tail要進(jìn)行-1。
?因?yàn)閿?shù)組下標(biāo)最小是從0開(kāi)始的，當(dāng)tail ==0且隊(duì)列不為空的情況下，上方代碼obj->tail-1,就會(huì)造成0-1 == -1的情況。上方采用(obj->tail - 1+ obj->k+1)%(obj->k+1)就可以完美的避免，當(dāng)然
其實(shí)可以寫(xiě)成
int myCircularQueueRear(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return -1;// return obj->a[(obj->tail-1 + obj->k+1)%(obj->k+1)];if(obj->tail == 0){return obj->a[obj->k];}else{return obj->a[obj->tail-1];}
}8.循環(huán)隊(duì)列釋放
?因?yàn)橛胢alloc開(kāi)辟的動(dòng)態(tài)內(nèi)存空間，為了避免內(nèi)存泄漏，我們還要釋放內(nèi)存。注意釋放的順序。
?代碼：
void myCircularQueueFree(MyCircularQueue* obj) {free(obj->a);free(obj);
}三、完整代碼展示：
?代碼：?
//采用動(dòng)態(tài)數(shù)組的形式來(lái)模擬循環(huán)隊(duì)列
typedef struct {int* a; //指向數(shù)組int front; //隊(duì)頭int tail; //隊(duì)尾int k; //數(shù)據(jù)個(gè)數(shù)
} MyCircularQueue;//創(chuàng)建長(zhǎng)度為k的循環(huán)隊(duì)列
MyCircularQueue* myCircularQueueCreate(int k) {//使用動(dòng)態(tài)內(nèi)存函數(shù)來(lái)申請(qǐng)內(nèi)存//這里多申請(qǐng)一個(gè)空間的目的是防止假溢出//使用malloc創(chuàng)建一個(gè)循環(huán)隊(duì)列MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));//為循環(huán)隊(duì)列里面的指針a ,讓a指向一個(gè)長(zhǎng)度為k+1的數(shù)組obj->a= (int*)malloc(sizeof(int)*(k+1));obj->front = 0; //隊(duì)頭從數(shù)組的下標(biāo)0開(kāi)始o(jì)bj->tail = 0; //隊(duì)尾指向下一個(gè)元素obj->k = k; //隊(duì)列的長(zhǎng)度為kreturn obj;
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {//隊(duì)空，就是隊(duì)頭與隊(duì)尾相同時(shí)return obj->front == obj->tail;
}bool myCircularQueueIsFull(MyCircularQueue* obj) {return (obj->tail+1)%(obj->k+1) == obj->front;
}//插入元素
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {//插入元素前先進(jìn)行判斷是否滿if(myCircularQueueIsFull(obj)){return false;}//插入元素使用尾插obj->a[obj->tail] = value;obj->tail++;//避免tail的下標(biāo)越界obj->tail%=(obj->k+1);return true;
}//出隊(duì)
bool myCircularQueueDeQueue(MyCircularQueue* obj) {//刪除元素隊(duì)列不能為空if(myCircularQueueIsEmpty(obj)){return false;}//出隊(duì)，頭刪obj->front++;obj->front%=(obj->k+1);return true;
}//獲取隊(duì)首元素
int myCircularQueueFront(MyCircularQueue* obj) {//隊(duì)列不能為空if(myCircularQueueIsEmpty(obj)){return -1; //隊(duì)空返回-1}return obj->a[obj->front];
}//獲取隊(duì)尾元素
int myCircularQueueRear(MyCircularQueue* obj) {//隊(duì)列不能為空if(myCircularQueueIsEmpty(obj)){return -1; //隊(duì)空返回-1}//注意當(dāng)tail = 0的情況return obj->a[(obj->tail - 1+ obj->k+1)%(obj->k+1)];
}void myCircularQueueFree(MyCircularQueue* obj) {free(obj->a);free(obj);
}/*** 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);
*/