數(shù)據(jù)結(jié)構(gòu)(Java版)隊(duì)列課件

1、隊(duì)列主要內(nèi)容隊(duì)列的定義隊(duì)列的操作隊(duì)列的實(shí)現(xiàn)實(shí)踐項(xiàng)目：使用隊(duì)列實(shí)現(xiàn)模擬營(yíng)業(yè)廳程序。用java類庫(kù)實(shí)現(xiàn)模擬營(yíng)業(yè)廳程序。隊(duì)列的應(yīng)用網(wǎng)絡(luò)打印程序。當(dāng)網(wǎng)絡(luò)中的用戶發(fā)送了打印作業(yè)后，那么這些作業(yè)將進(jìn)入一個(gè)打印隊(duì)列中等候打印，而網(wǎng)絡(luò)打印程序每打印一份作業(yè)，就從隊(duì)列中出隊(duì)一份作業(yè)。磁盤驅(qū)動(dòng)程序。管理一個(gè)磁盤輸入/輸出請(qǐng)求的隊(duì)列。操作系統(tǒng)中的調(diào)度程序，維護(hù)一個(gè)等待處理器時(shí)間片的進(jìn)程隊(duì)列。行業(yè)應(yīng)用程序。比如，醫(yī)院候診程序、銀行業(yè)務(wù)等候程序、移動(dòng)電話業(yè)務(wù)等候程序等等?；鶖?shù)排序程序。使用隊(duì)列實(shí)現(xiàn)的一種排序方法。 問題引入移動(dòng)電話公司計(jì)劃在某個(gè)區(qū)的某條路上新增設(shè)一個(gè)業(yè)務(wù)廳，配置多少個(gè)營(yíng)業(yè)員比較合理？ 下面是根據(jù)市場(chǎng)調(diào)查

2、得到的一組數(shù)據(jù)，希望以此為依據(jù)能測(cè)算出比較合理的營(yíng)業(yè)員配置數(shù)目。平均每天約100個(gè)顧客，平均每30秒增加一個(gè)顧客。一個(gè)營(yíng)業(yè)員處理一個(gè)顧客業(yè)務(wù)的平均時(shí)間是2分鐘（120秒），也就是一個(gè)顧客實(shí)際辦理業(yè)務(wù)的平均時(shí)間。營(yíng)業(yè)員處理顧客需求原則：只有一個(gè)顧客等候隊(duì)列，先到先辦理。如果某個(gè)營(yíng)業(yè)員可以提供服務(wù)，則顧客一到就可以辦理業(yè)務(wù)。如何用程序來解決這個(gè)問題呢？1、 隊(duì)列的定義 和棧相反，隊(duì)列(Queue)是一種先進(jìn)先出(First In First Out,縮寫為FIFO)的線性結(jié)構(gòu)。它只允許在表的一端進(jìn)行插入，而在另一端刪除元素。這和我們?nèi)粘Ｉ钪械呐抨?duì)是一致的，最早進(jìn)入隊(duì)列的元素最早離開。在隊(duì)列中，允

3、許插入的一端叫做隊(duì)尾(rear)，允許刪除的一端則稱為隊(duì)頭(front)。2、隊(duì)列的操作（運(yùn)算）進(jìn)隊(duì)：在隊(duì)尾添加一個(gè)數(shù)據(jù)元素。出隊(duì)：刪除隊(duì)頭的數(shù)據(jù)元素。獲取隊(duì)頭元素：獲取隊(duì)列中當(dāng)前隊(duì)頭的數(shù)據(jù)元素。獲取當(dāng)前隊(duì)列中的元素個(gè)數(shù)：求當(dāng)前隊(duì)列中的元素個(gè)數(shù)。判斷隊(duì)列是否為空：判斷當(dāng)前隊(duì)列中是否還有元素。 3、隊(duì)列的實(shí)現(xiàn)隊(duì)列可用兩種方式來實(shí)現(xiàn)數(shù)組實(shí)現(xiàn)：隊(duì)首是索引為0的位置。鏈?zhǔn)綄?shí)現(xiàn)：借助兩個(gè)引用（指針）front和rear，front指向鏈表第一個(gè)元素,rear指向的鏈表最后一個(gè)元素。順序隊(duì)列存儲(chǔ)結(jié)構(gòu)及其基本狀態(tài) 順序隊(duì)列的“假溢出” 問題 假設(shè)用來存儲(chǔ)一個(gè)順序隊(duì)列的數(shù)組的長(zhǎng)度n=5，則當(dāng)數(shù)據(jù)data1,d

4、ata2,data3進(jìn)隊(duì)后，將data1,data2依次出隊(duì)，然后將data4,data5入隊(duì)。此時(shí)隊(duì)尾指針rear=5，如果此時(shí)有一個(gè)數(shù)據(jù)元素data想進(jìn)入隊(duì)列，則發(fā)生“假溢出”現(xiàn)象。如下圖: 如何解決順序隊(duì)列假溢出?順序隊(duì)列假溢出是因?yàn)殛?duì)頭指針front和隊(duì)尾指針rear沒能及時(shí)地隨數(shù)組上下界值的變化而進(jìn)行變化。因此解決的方法是把順序隊(duì)列所使用的存儲(chǔ)空間構(gòu)造成一個(gè)邏輯上首尾相接的循環(huán)隊(duì)列，即最后一個(gè)存儲(chǔ)單元相鄰的下一個(gè)存儲(chǔ)位置是數(shù)組的第一個(gè)存儲(chǔ)單元。也就是說，當(dāng)rear和front的值達(dá)到n-1（數(shù)組的長(zhǎng)度）時(shí)，就使其等于0，這樣就可以避免順序隊(duì)列頭部空出許多存儲(chǔ)單元，而隊(duì)尾卻因數(shù)組下標(biāo)越

5、界出現(xiàn)假溢出的狀況。 順序循環(huán)隊(duì)列的存儲(chǔ)結(jié)構(gòu)及其狀態(tài)鏈?zhǔn)疥?duì)列的存儲(chǔ)結(jié)構(gòu)及其基本狀態(tài) 項(xiàng)目實(shí)踐 調(diào)試運(yùn)行例題3-2 項(xiàng)目設(shè)計(jì)首先對(duì)數(shù)據(jù)元素（顧客）和數(shù)據(jù)操作（進(jìn)隊(duì)和出隊(duì)等）進(jìn)行設(shè)計(jì)，然后設(shè)計(jì)一個(gè)顧客隊(duì)列實(shí)現(xiàn)所定義的數(shù)據(jù)操作，最后在主程序中加載一個(gè)顧客隊(duì)列并對(duì)其進(jìn)行處理，從而得到所要的結(jié)果。項(xiàng)目實(shí)現(xiàn)步驟程序共包含下面三個(gè)類，一個(gè)接口，都放在一個(gè)源程序文件 SimulationOffice.java中。Customer類。定義數(shù)據(jù)元素，記錄顧客到達(dá)和離開的時(shí)刻。QueueADT類。定義數(shù)據(jù)元素的操作，即進(jìn)隊(duì)、出隊(duì)等。ArrayQueue類。用數(shù)組實(shí)現(xiàn)的隊(duì)列，ArrayQueue對(duì)象可以模擬顧客隊(duì)列。

6、SimulationOffice類。接受輸入數(shù)據(jù)，完成顧客隊(duì)列的加載和處理，計(jì)算并輸出顧客來營(yíng)業(yè)廳辦理業(yè)務(wù)所花費(fèi)的平均時(shí)間。類SimulationOffice 需要解決的問題從鍵盤輸入業(yè)員個(gè)數(shù)、顧客人數(shù)、業(yè)務(wù)處理時(shí)間和顧客到達(dá)的平均間隔時(shí)間。根據(jù)顧客人數(shù)和顧客到達(dá)的平均間隔時(shí)間值構(gòu)造一個(gè)顧客等候隊(duì)列，辦事原則是先到先辦理。如果某個(gè)營(yíng)業(yè)員可以提供服務(wù)（空閑），則顧客一到就可以辦理業(yè)務(wù)。設(shè)置一個(gè)數(shù)組用來記錄營(yíng)業(yè)員當(dāng)前的空閑時(shí)刻。為了簡(jiǎn)單起見，我們用整數(shù)來表示這個(gè)時(shí)間，初始的空閑時(shí)刻均為0。總是最先空閑的那個(gè)營(yíng)業(yè)員來處理當(dāng)前顧客隊(duì)列中的隊(duì)頭顧客，當(dāng)一個(gè)營(yíng)業(yè)員處理完一個(gè)顧客要求后，顧客離去的時(shí)刻就是這

7、個(gè)營(yíng)業(yè)員的當(dāng)前空閑時(shí)刻。顧客離去時(shí)間的計(jì)算。如果顧客到達(dá)時(shí)間大于當(dāng)前營(yíng)業(yè)員當(dāng)前空閑時(shí)刻，則顧客一到就可以辦理業(yè)務(wù)，離去時(shí)間=到達(dá)時(shí)間+業(yè)務(wù)處理時(shí)間；如果顧客到達(dá)時(shí)間小于營(yíng)業(yè)員當(dāng)前空閑時(shí)刻，則需要等候，離去時(shí)間=營(yíng)業(yè)員當(dāng)前空閑時(shí)刻+業(yè)務(wù)處理時(shí)刻累加每個(gè)顧客花費(fèi)的時(shí)間。計(jì)算并輸出每個(gè)顧客平均花費(fèi)的時(shí)間。具體實(shí)現(xiàn)算法1 定義相關(guān)變量2 從鍵盤輸入售票員個(gè)數(shù),業(yè)務(wù)處理時(shí)間,顧客數(shù)目,顧客之間的間隔時(shí)間.3 定義一個(gè)數(shù)組用來記錄每個(gè)營(yíng)業(yè)員的當(dāng)前時(shí)間4 定義一個(gè)顧客隊(duì)列cQueue,并初始化隊(duì)列中每個(gè)顧客的到達(dá)時(shí)間,每隔*秒到達(dá)一個(gè)顧客5 Whilie(cQueue不空) 出隊(duì)一個(gè)顧客 找出當(dāng)前時(shí)間最小的

8、那個(gè)營(yíng)業(yè)員,由該營(yíng)業(yè)員來處理這個(gè) 顧客. 當(dāng)顧客到達(dá)時(shí)間大于營(yíng)業(yè)員當(dāng)前時(shí)間時(shí),該顧客的離開時(shí)間為 顧客到達(dá)時(shí)間+營(yíng)業(yè)員處理一個(gè)顧客的時(shí)間 否則,該顧客的離開時(shí)間為該營(yíng)業(yè)員的當(dāng)前時(shí)間+營(yíng)業(yè)員處理一個(gè) 顧客的時(shí)間. 修改該營(yíng)業(yè)員的當(dāng)前時(shí)間 累加顧客花費(fèi)時(shí)間 6 計(jì)算顧客平均花費(fèi)時(shí)間 7 輸出售票員個(gè)數(shù)和顧客平均花費(fèi)時(shí)間.課堂實(shí)訓(xùn)1修改程序。為顧客增加一個(gè)編號(hào)顯示XX號(hào)顧客到XX號(hào)窗口（營(yíng)業(yè)員）辦理業(yè)務(wù)。課堂實(shí)訓(xùn)2鏈?zhǔn)疥?duì)列的設(shè)計(jì)與實(shí)現(xiàn): 將例題3-2中的順序隊(duì)列改為鏈?zhǔn)疥?duì)列。 課堂實(shí)訓(xùn)3使用Java類庫(kù)中的集合類實(shí)現(xiàn)模擬營(yíng)業(yè)廳程序 .在JAVA類庫(kù)中，沒有類似于Stack類的專門用來處理隊(duì)列的類，但是我們可以通過LinkedList類來實(shí)現(xiàn)隊(duì)列的功能 .使用java.util.Linke