[理學(xué)]第4章棧和隊(duì)列-資料下載頁(yè)
2025-01-19 14:59本頁(yè)面
【正文】 ＃ 輸出： 7 8 5 2 * + 6 3 / 25 隊(duì)列 與線性表相同，仍為一對(duì)一關(guān)系。 順序隊(duì) 或 鏈隊(duì) ，以 循環(huán)順序隊(duì) 更常見(jiàn)。 只能在隊(duì)首和隊(duì)尾運(yùn)算，且訪問(wèn)結(jié)點(diǎn)時(shí)依照先進(jìn)先出 （ FIFO） 的原則。 關(guān)鍵是掌握 入隊(duì) 和 出隊(duì) 操作，具體實(shí)現(xiàn)依順序隊(duì)或鏈隊(duì)的不同而不同。 存儲(chǔ)結(jié)構(gòu) 運(yùn)算規(guī)則 實(shí)現(xiàn)方式 邏輯結(jié)構(gòu) 只能在表的一端進(jìn)行插入運(yùn)算，在表的另一端進(jìn)行刪除運(yùn)算的線性表。 基本操作 ： 入隊(duì)或出隊(duì)，建空隊(duì)列，判隊(duì)空或隊(duì)滿等操作。 尾部插入 首部刪除 隊(duì)列定義 26 隊(duì)列 （ Queue） 是僅在 表尾 進(jìn)行插入操作，在 表頭 進(jìn)行刪除操作的線性表。它是一種先進(jìn)先出 （ＦＩＦＯ） 的線性表。 例如：隊(duì)列 Q= (a1 , a2 , a3 , ………., an1 , an ) 在隊(duì)尾插入元素稱為 入隊(duì) ；在隊(duì)首刪除元素稱為 出隊(duì) 。 隊(duì)首 隊(duì)尾 為什么要設(shè)計(jì)隊(duì)列？它有什么獨(dú)特用途？ 1. 離散事件的模擬 （模擬事件發(fā)生的先后順序 ,例如 CPU芯片中的指令譯碼隊(duì)列） ； 2. 操作系統(tǒng)中的作業(yè)調(diào)度 （一個(gè) CPU執(zhí)行多個(gè)作業(yè)） ； 3. 簡(jiǎn)化程序設(shè)計(jì)。 27 隊(duì)列的順序存儲(chǔ) struct Queue { ElemType *queue。 int front,rear。 int MaxSize。 }。 front: 指向當(dāng)前的隊(duì)頭指針 rear: 指向下一個(gè)插入元素的位置 28 隊(duì)列的順序存儲(chǔ) 插入 4個(gè)數(shù) :10,20,30,40 刪除 2個(gè)數(shù) :10,20 40 30 再插入 4個(gè)數(shù) :50,60,70,80 70 60 50 40 30 80 40 30 20 10 29 循環(huán)隊(duì)列的順序存儲(chǔ) 80 70 60 50 40 30 90 隊(duì)列為空的條件： = 隊(duì)列滿的條件： （ +1)= （ +1) % MaxSize = 錯(cuò)誤 30 循環(huán)隊(duì)列的順序存儲(chǔ) 初始化隊(duì)列 void InitQueue(Queue amp。q) { =10。 =new ElemType[]。 ==0。 } 31 入隊(duì)時(shí)空間不夠的處理 80 70 60 50 40 30 90 80 70 60 50 40 30 90 80 70 60 50 40 30 90 32 循環(huán)隊(duì)列的鏈接存儲(chǔ) a1 a2 … an ^ front rear 隊(duì)列為空的條件： =NULL hq 一般不會(huì)出現(xiàn)隊(duì)列滿的情況，除非內(nèi)存不夠
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1