《數(shù)據(jù)結(jié)構(gòu)課件隊(duì)列》ppt課件-文庫(kù)吧
2025-04-14 02:57 本頁(yè)面
【正文】 （ c) a出隊(duì) (d) b,c出隊(duì)，隊(duì)為空 define MAXQSIZE 100 typedef struct { ElemType data[MAXQSIZE]。 int front。 /*隊(duì)頭位置 */ int rear。 /*隊(duì)尾位置 */ }SqQueue。 順序隊(duì)列的操作演示 隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)定義： SqQueue Q Qfront 存放即將要被刪除的元素的下標(biāo)。 Qrear 存放即將要被插入的元素（目前不在隊(duì)列中）的下標(biāo)。 Q data[ Qfront]和 Q data[ Qrear] ?初始化： = =0 ?隊(duì)空： = ?隊(duì)滿： =maxsize（假溢出） ?求隊(duì)長(zhǎng)： ? 入隊(duì)：新元素按 rear 指示位置加入，再將隊(duì)尾指針加一 ，即 rear = rear + 1 ? 出隊(duì)：將 front指示的元素取出，再將隊(duì)頭指針加一，即 front = front + 1 非循環(huán)隊(duì)列 注意： 入隊(duì)?wèi)?yīng)考慮隊(duì)滿；出隊(duì)?wèi)?yīng)考慮隊(duì)空。 和棧類似，隊(duì)列中亦有上溢和下溢現(xiàn)象。此外，順序隊(duì)列中還存在 “ 假上溢 ” 現(xiàn)象。因?yàn)樵谌腙?duì)和出隊(duì)的操作中，頭尾指針只增加不減小，致使被刪除元素的空間永遠(yuǎn)無(wú)法重新利用。因此，盡管隊(duì)列中實(shí)際的元素個(gè)數(shù)遠(yuǎn)遠(yuǎn)小于向量空間的規(guī)模，但也可能由于尾指針?biāo)瘸鱿蛄靠臻g的上界而不能做入隊(duì)操作。該現(xiàn)象稱為假上溢。 為充分利用向量空間，克服上述假上溢現(xiàn)象，可以將向量空間想象為一個(gè)首尾相接的圓環(huán)，并稱這種向量為循環(huán)向量，存儲(chǔ)在其中的隊(duì)列稱為 循環(huán)隊(duì)列（ Circular Queue)。在循環(huán)隊(duì)列中進(jìn)行出隊(duì)、入隊(duì)操作時(shí)，頭尾指針仍要加 1，朝前移動(dòng)。只不過(guò)當(dāng)頭尾指針指向向量上界（ QueueSize1）時(shí)，其加 1操作的結(jié)果是指向向量的下界 0。 顯然，因?yàn)檠h(huán)隊(duì)列元素的空間可以被利用，除非向量空間真的被隊(duì)列元素全部占用，否則不會(huì)上溢。因此，除一些簡(jiǎn)單的應(yīng)用外，真正實(shí)用的順序隊(duì)列是循環(huán)隊(duì)列（環(huán)形隊(duì)列）。 由于入隊(duì)時(shí)尾指針向前追趕頭指針，出隊(duì)時(shí)頭指針向前追趕尾指針，故隊(duì)空和隊(duì)滿時(shí)頭尾指針均相等。因此，我們無(wú)法通過(guò) Qf = Qr來(lái)判斷隊(duì)列 “ 空 ” 還是 “ 滿 ” 。 front 5 4 0 3 1 2 J6 J7 J8 J4 J5 rear 0 1 2 3 4 5 rear front J5 J6 J7 0 1 2 3 4 5 rear front J4 J9 J8 J4 J5 J6 0 1 2 3 4 5 rear front
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1