數(shù)據(jù)結(jié)構(gòu)課件隊(duì)列ppt課件-資料下載頁
2025-04-29 02:57本頁面
【正文】 的作用 ， 在此 ， 僅舉出兩個(gè)方面例子來說明它 ， 其它應(yīng)用在后面章節(jié)中將會遇到 。 第一個(gè)例子就是 CPU資源的競爭問題 。 在具有多個(gè)終端的計(jì)算機(jī)系統(tǒng)中 ， 有多個(gè)用戶需要使用 CPU各自運(yùn)行自己的程序 ， 它們分別通過各自終端向操作系統(tǒng)提出使用 CPU的請求 ， 操作系統(tǒng)按照每個(gè)請求在時(shí)間上的先后順序 ， 將其排成一個(gè)隊(duì)列 ， 每次把 CPU分配給隊(duì)頭用戶使用 ， 當(dāng)相應(yīng)的程序運(yùn)行結(jié)束 ， 則令其出隊(duì) ， 再把 CPU分配給新的隊(duì)頭用戶 ， 直到所有用戶任務(wù)處理完畢 。 第二個(gè)例子就是主機(jī)與外部設(shè)備之間速度不匹配的問題 。 以主機(jī)和打印機(jī)為例來說明 ， 主機(jī)輸出數(shù)據(jù)給打印機(jī)打印 ， 主機(jī)輸出數(shù)據(jù)的速度比打印機(jī)打印的速度要快得多 ， 若直接把輸出的數(shù)據(jù)送給打印機(jī)打印 ， 由于速度不匹配 ， 顯然是不行的 。 所以解決的方法是設(shè)置一個(gè)打印數(shù)據(jù)緩沖區(qū) ， 主機(jī)把要打印輸出的數(shù)據(jù)依此寫如到這個(gè)緩沖區(qū)中 ， 寫滿后就暫停輸出 ， 繼而去做其它的事情 ， 打印機(jī)就從緩沖區(qū)中按照先進(jìn)先出的原則依次取出數(shù)據(jù)并打印 ， 打印完后再向主機(jī)發(fā)出請求 ， 主機(jī)接到請求后再向緩沖區(qū)寫入打印數(shù)據(jù) ， 這樣利用隊(duì)列既保證了打印數(shù)據(jù)的正確 ， 又使主機(jī)提高了效率 。 討論（本章小結(jié)） 線性表、棧與隊(duì)的異同點(diǎn) 相同點(diǎn)： 邏輯結(jié)構(gòu)相同 ， 都是線性的；都可以用順序存儲或鏈表存儲；棧和隊(duì)列是兩種特殊的線性表 ，即 受限的線性表 （ 只是對插入 、 刪除運(yùn)算加以限制 ） 。 不同點(diǎn)： ① 運(yùn)算規(guī)則不同 ， 線性表為隨機(jī)存取 ， 而棧是只允許在一端進(jìn)行插入和刪除運(yùn)算 ， 因而是后進(jìn)先出表LIFO；隊(duì)列是只允許在一端進(jìn)行插入 、 另一端進(jìn)行刪除運(yùn)算 ， 因而是先進(jìn)先出表 FIFO。 ② 用途不同，線性表比較通用；堆棧用于函數(shù)調(diào)用、遞歸和簡化設(shè)計(jì)等；隊(duì)列用于離散事件模擬、多道作業(yè)處理和簡化設(shè)計(jì)等。 稱正讀和反讀都相同的字符序列為 “ 回文 ” ，例如 “ abba”，寫一個(gè)算法，判別讀入以 “ @”為結(jié)束符的字符序列是否為“ 回文 ” 。 假設(shè)以帶頭結(jié)點(diǎn)的循環(huán)鏈表表是隊(duì)列，并且只設(shè)一個(gè)指針指向隊(duì)尾結(jié)點(diǎn)，但不設(shè)頭指針，設(shè)計(jì)相應(yīng)的入隊(duì)和出隊(duì)算法。 int Test() //判別輸入的字符串是否回文序列 ,是返回 1,否返回 0 { Stack S。Queue Q 。char a,b。 InitStack(S)。InitQueue(Q)。 while((c=getchar())!=39。@39。) { Push(S,c)。EnQueue(Q,c)。 //同時(shí)使用棧和隊(duì)列兩種結(jié)構(gòu) } while(!StackEmpty(S)) { Pop(S,a)。DeQueue(Q,b))。 if(a!=b) return ERROR。} return OK。 } 試寫一個(gè)算法判別讀入的一個(gè)以 ‘ @’為結(jié)束符的字符序列是否是 “ 回文 ” 。
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1