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