軟件技術(shù)基礎(chǔ)課件

15-11.隊列的基本概念2.循環(huán)隊列及其運(yùn)算3.循環(huán)隊列類4.隊列的應(yīng)用2.2.3隊列及其應(yīng)用15-21.什么是隊列定義：允許在一端進(jìn)行插入,而在另一端進(jìn)行刪除的線性表。（基于方法的定義）插入的一端為隊尾(rear),刪除的一端為隊頭(head)邏輯特征：FIFO,LILO要素（決定操作的細(xì)節(jié)）隊的存儲結(jié)構(gòu)隊尾的標(biāo)識隊頭的標(biāo)識主要操作：初始化空隊、判斷隊空、判斷隊滿、入隊、出隊、取隊頭隊頭入隊出隊a1a2a3……an隊尾15-3隊列的存儲結(jié)構(gòu)順序隊列:用數(shù)組實現(xiàn)隊列fronta[0]隊首隊尾a[1]......a[n]MAXrear15-4移元素？移指針？frontrear入隊、退隊、退隊、入隊、入隊、入隊、(再入隊將溢出)rearfrontrear入隊與退隊移指針：方便，但會造成假溢出，浪費(fèi)空間問題：如何解決假溢出？兩個辦法：①移動元素：簡單，低效；√②將隊列設(shè)想成一個環(huán)狀結(jié)構(gòu)——

循環(huán)隊列。rearfront15-5將順序隊列設(shè)想為首尾相連的環(huán)狀空間，第1個單元聯(lián)結(jié)第m個單元。當(dāng)指針超出隊列空間的最大位置時，令它們?yōu)?，使隊列空間能“循環(huán)”使用。m4321Q.rearQ.frontJ6J5J4指針的移動

Q.rear=(Q.rear+1)%m

Q.front=(Q.front+1)%m

2.循環(huán)隊列序號J6J4J5Q.rearQ.front循環(huán)隊列圖示423m51Q.rearQ.frontJ6J7J8J9J4J5

J6Q.frontQ.rearJ5J4(a)(b)隊空(c)隊滿問題：如何判斷隊列滿和空？

1)在(a)狀態(tài)下，J4、J5、J6出隊，

隊列狀態(tài)如圖(b)，這時有：

Q.front==Q.rear;

2)在(a)狀態(tài)下，J7、J8、J9入隊后，

再要入隊，隊列狀態(tài)如圖(c)，這時也有： Q.front==Q.rear;

無法判斷隊列是空還是滿！Q.rear

Q.front？423m51423m51423m5115-7兩種解決方法：另設(shè)一個標(biāo)志位s以區(qū)分隊空、隊滿。

s=0:隊列空

s=1:隊列非空引入隊列長度少用一個存儲單元，即當(dāng)隊列達(dá)到圖(d)所示狀態(tài)時，就認(rèn)為隊列已滿，即：

Q.front==(Q.rear+1)%mQ.rear

Q.frontJ6J7J8J4J5（d）空余單元423m5115-8順序存儲的循環(huán)隊列C++描述usingnamespacestd;template<typenameT> //模板申明，T為類型參數(shù)voidinit_Queue(T*q,intm,int*front,int*rear,int*s){q=newT(m); //申請m個存儲空間

*front=m;*rear=m;*s=0; //初始化空隊列return; } 注：q數(shù)組q[0……m-1]15-9循環(huán)隊列入隊操作usingnamespacestd;template<typenameT> voidaddcq(T*q,intm,int*front,int*rear,int*s,Tx

){if((*s==1)&&(*rear==*front)) //判隊列滿{cout<<“Queueoverflow!”<<endl;return;}

*rear=*rear+1;

//隊尾序號指針遞增

if(*rear==m+1)*rear=1; //序號循環(huán)q[*rear-1]=x;*s=1; //入隊，置隊列非空return; } 注：*rear中的序號與數(shù)組中元素的存儲位置的對應(yīng)15-10循環(huán)隊列退隊操作usingnamespacestd;template<typenameT> voiddelcq(T*q,intm,int*front,int*rear,int*s

){Ty;if(*s==0) //判隊列空{(diào)cout<<“Queueunderflow!”<<endl;return;}

*front=*front+1;

//隊尾序號指針遞增

if(*front==m+1)*front=1; //序號循環(huán)*y=q[*front-1]; //退隊if(*front==*rear)*s=0; //置隊列空標(biāo)志return; } 注：*front中的序號與數(shù)組中元素的存儲位置的對應(yīng)15-113.

循環(huán)隊列類-sq_Queue#include<iostream>usingnamespacestd;template<classT> classsq_Queue //順序棧類{private: //數(shù)據(jù)成員intmm; //存儲空間容量intfront; //隊頭指標(biāo)（注意與前例的區(qū)別）

intrear; //隊尾指標(biāo)（注意與前例的區(qū)別）ints; //隊空標(biāo)志T*q;public: //成員函數(shù)sq_Queue(int); //構(gòu)造函數(shù)，初始化空隊列voidprt_sq_Queue(); //輸出隊頭及隊尾指針和隊中元素

intflag_sq_Queue();

//檢測循環(huán)隊列狀態(tài)voidins_sq_Queue(T); //入隊

Tdel_sq_Queue(); //退隊}; 請同學(xué)自行分析各成員函數(shù)及其用法（p44-46）15-124.隊列應(yīng)用解決由于多用戶引起的資源競爭問題：如操作系統(tǒng)中的作業(yè)排隊，作業(yè)按請求處理的先后次序排隊，每當(dāng)一個作業(yè)的處理完畢，就再取隊頭作業(yè)進(jìn)行處理；新的作業(yè)要求處理時，先排在隊尾排隊等待。又如網(wǎng)絡(luò)排隊打印服務(wù)。用于紀(jì)錄程序中的步驟順序，以便進(jìn)行非純逆向回朔特征的過程：如圖的廣度優(yōu)先搜索遍歷。離散事件模擬：模擬實際應(yīng)用中的各種排隊現(xiàn)象，如交通流量控制、銀行服務(wù)系統(tǒng)。15-13離散事件模擬事件發(fā)生是隨機(jī)的。事件發(fā)生和持續(xù)的時間是隨機(jī)的。對事件的處理按先來后到的順序進(jìn)行。用程序模擬離散事件：時間模擬：1）確定最小時間間隔。用隨機(jī)數(shù)模擬事件發(fā)生的概率，產(chǎn)生事件。用隨機(jī)數(shù)模擬對事件處理和結(jié)束的概率。2）用隨機(jī)數(shù)模擬事件發(fā)生的時間，持續(xù)時間。(時間點(diǎn),片)用隨機(jī)數(shù)模擬對事件處理和結(jié)束的時間。(時間片,點(diǎn))順序模擬：用隊列模擬有先后順序關(guān)系的離散事件內(nèi)容和處理過程。15-14加油站工作模擬序號123m到車率dt/grearfront加油站總服務(wù)時間:time采樣間隔:dt

(dt<g)Rnd<=dt/g

:到車

01加油時間:d加油機(jī)狀態(tài):flag(0,1)=d-dt,flag(i)<=0:取隊頭車加油服務(wù)對象:aut(0,1)=C