本文是個(gè)人學(xué)習(xí)筆記，素材來自青島大學(xué)王卓老師的教學(xué)視頻。
一方面用于學(xué)習(xí)記錄與分享，
另一方面是想讓更多的人看到這么好的《數(shù)據(jù)結(jié)構(gòu)與算法》的學(xué)習(xí)視頻。
如有侵權(quán)，請(qǐng)留言作刪文處理。
課程視頻鏈接：
數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)–第05周13–3.5隊(duì)列的表示和實(shí)現(xiàn)2–3.5.2隊(duì)列的順序表示和實(shí)現(xiàn)1
?? 【W(wǎng)eek05】13_隊(duì)列的順序表示和實(shí)現(xiàn)1
隊(duì)列
順序隊(duì)列空棧、入隊(duì)和出隊(duì)示意圖
? 思考：存在什么問題？？
設(shè)數(shù)組大小為 MAXQSIZE，rear = MAXQSIZE 時(shí)，發(fā)生溢出。
解決假上溢的方法
(1) 將隊(duì)中元素依次向隊(duì)頭方向移動(dòng)。
缺點(diǎn)：浪費(fèi)時(shí)間。每移動(dòng)一次，隊(duì)中元素都要移動(dòng)。
(2) 將隊(duì)空間設(shè)想成一個(gè)循環(huán)的表，即分配給隊(duì)列的 m 個(gè)存儲(chǔ)單元可以循環(huán)使用。
當(dāng) rear 為 maxqsize 時(shí)，若向量的開始端空著，又可從頭使用空著的空間。
當(dāng) front 為 maxqsize 時(shí)，也是一樣。
就好像下標(biāo)為 0 的位置是接在下標(biāo)為 5 的位置后面。
?? 解決假上溢的方法——引入循環(huán)隊(duì)列
base[0] 接在 base[MAXQSIZE - 1] 之后，若 rear + 1 == M，則令 rear = 0；
實(shí)現(xiàn)方法：
利用 模運(yùn)算（mod，C語言中：%）。
插入元素：
Q.base[Q.rear] = x;
Q.rear = (Q.rear + 1) % MAXQSIZE;
刪除元素：
x = Q.base[s.front];
Q.front = (Q.front + 1) % MAXQSIZE;
循環(huán)隊(duì)列：循環(huán)使用為隊(duì)列分配的存儲(chǔ)空間。
循環(huán)隊(duì)列入隊(duì)和出隊(duì)
? 思考：循環(huán)隊(duì)列時(shí)會(huì)出現(xiàn)隊(duì)空：front == rear，隊(duì)滿：front == rear，如何判斷隊(duì)空和隊(duì)滿？
解決方案：
(1) 另外設(shè)一個(gè)標(biāo)志以區(qū)別隊(duì)空和隊(duì)滿
(2) 另設(shè)一個(gè)變量，記錄元素個(gè)數(shù)
(3) 少用一個(gè)元素空間文章來源：http://www.zghlxwxcb.cn/news/detail-581716.html
循環(huán)隊(duì)列解決隊(duì)滿時(shí)判斷方法——少用一個(gè)元素空間
文章來源地址http://www.zghlxwxcb.cn/news/detail-581716.html
到了這里，關(guān)于青島大學(xué)_王卓老師【數(shù)據(jù)結(jié)構(gòu)與算法】Week05_13_隊(duì)列的順序表示和實(shí)現(xiàn)1_學(xué)習(xí)筆記的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
