高中二年級(jí)下學(xué)期信息科技《用隊(duì)列組織先進(jìn)先出數(shù)據(jù)》教學(xué)課件

選擇性必修1《數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)》3.3用隊(duì)列組織先進(jìn)先出數(shù)據(jù)|一、隊(duì)列queue|隊(duì)列的基本概念|隊(duì)列是一種特殊的線性表，它只允許在表的一端進(jìn)行插入，在表的另一端進(jìn)行刪除隊(duì)尾：能進(jìn)行插入的一端隊(duì)頭：能進(jìn)行刪除的一端入隊(duì)：把一個(gè)數(shù)據(jù)元素插入隊(duì)列中的操作叫作入隊(duì)出隊(duì)：從隊(duì)列中刪除一個(gè)數(shù)據(jù)元素的操作叫作出隊(duì)空隊(duì)列：隊(duì)列中沒(méi)有元素時(shí)，稱為空隊(duì)列舉例：①售票窗口②排隊(duì)買飯?zhí)匦裕合冗M(jìn)先出（FirstInFirstOut）簡(jiǎn)稱FIFO；超市為顧客提供的售后服務(wù)請(qǐng)求建立數(shù)據(jù)模型|為服務(wù)請(qǐng)求隊(duì)列建立數(shù)據(jù)模型隊(duì)列{

隊(duì)列元素（一定數(shù)量的顧客編號(hào)）；

隊(duì)頭（即將出隊(duì)的顧客的位置）；

隊(duì)尾（即將入隊(duì)的顧客的位置）；}隊(duì)列的基本操作；設(shè)計(jì)自助服務(wù)系統(tǒng)的操作|二、隊(duì)列的基本操作Basicoperationofqueue|隊(duì)列的基本操作|對(duì)于隊(duì)列，通常有以下幾種基本操作:(1)初始化隊(duì)列：構(gòu)造一個(gè)空隊(duì)列，初始化隊(duì)頭、隊(duì)尾標(biāo)志。(2)元素入隊(duì)：若隊(duì)列非滿，插人一個(gè)元素到隊(duì)列的隊(duì)尾標(biāo)志指向的位置，該元素成為新的隊(duì)尾元素，隊(duì)尾標(biāo)志向后移動(dòng)位。q：frontrear空隊(duì)列q：frontreara1入隊(duì)q：frontreara2,a3依次入隊(duì)a1a1a2a3初始化隊(duì)列：front=rear=0入隊(duì)操作：rear=rear+1隊(duì)列的基本操作|(3)元素出隊(duì)：刪除隊(duì)頭標(biāo)志指向的隊(duì)頭元素，隊(duì)頭標(biāo)志向后移動(dòng)一位，若此時(shí)隊(duì)列非空，則隊(duì)頭標(biāo)志指向的元素成為新的隊(duì)頭元素。(4)求隊(duì)列長(zhǎng)度：返回隊(duì)列當(dāng)前所含元素個(gè)數(shù)。(5)隊(duì)空判斷：若隊(duì)列為空，則返回“真”，否則返回“假”(6)隊(duì)滿判斷：若隊(duì)列為滿，則返回“真”，否則返回“假”假設(shè)已定義隊(duì)列q、隊(duì)頭front、隊(duì)尾rear,則初始化隊(duì)列為空、入隊(duì)和出隊(duì)幾種情況如圖q：frontreara1出隊(duì)a2a3q：frontreara2出隊(duì)a3出隊(duì)操作：front=front+1求隊(duì)列長(zhǎng)度：rear-front隊(duì)空判斷：front==rear隊(duì)滿判斷：rear==maxsize三、隊(duì)列的實(shí)現(xiàn)-順序隊(duì)列Queueimplementation-sequentialqueue|順序隊(duì)列順序隊(duì)列：當(dāng)入隊(duì)或出隊(duì)時(shí)，隊(duì)尾標(biāo)志rear或隊(duì)頭標(biāo)志front只能往后移動(dòng)一位，且其隊(duì)列的最大長(zhǎng)度為maxsize（數(shù)組的容量），我們把這種隊(duì)列成為順序隊(duì)列。|數(shù)

組：frontrear順序隊(duì)列a3數(shù)組下標(biāo)：012345a4a1a20≤front≤maxsize0≤rear≤maxsizemaxsize=6順序隊(duì)列初始化隊(duì)列：front=rear=0入隊(duì)操作：rear=rear+1出隊(duì)操作：front=front+1隊(duì)空判斷：front==rear隊(duì)滿判斷：rear==maxsize求隊(duì)列長(zhǎng)度：rear-front|順序隊(duì)列的操作代碼|

隊(duì)頭標(biāo)志和隊(duì)尾標(biāo)志均為0，這時(shí)隊(duì)列為空，沒(méi)有元素初始化隊(duì)列voidInit_Queue(Queue&q){q.front=q.rear=0;}順序隊(duì)列的操作代碼|

當(dāng)front=rear時(shí)，隊(duì)列為空，返回true，否則返回false。判斷隊(duì)列是否為空boolIsEmpty_Queue(Queue&q){if(q.front==q.rear)returntrue;elsereturnfalse;}順序隊(duì)列的操作代碼|

當(dāng)rear=maxsize時(shí)，隊(duì)列為滿，返回true，否則返回false。判斷隊(duì)列是否為滿boolIsFull_Queue(Queue&q){if(q.rear==maxsize)returntrue;elsereturnfalse;}順序隊(duì)列的操作代碼|

如果隊(duì)列非滿，則將元素x放入隊(duì)尾標(biāo)志rear所指位置，然后rear指向下一個(gè)位置。入隊(duì)操作boolIn_Queue(Queue&q,stringx){if(!IsFull_Queue(q)){ q.items[q.rear]=x; q.rear=q.rear+1;}}順序隊(duì)列的操作代碼|

如果隊(duì)列為空，返回空元素（NULL），否則返回隊(duì)頭標(biāo)志front所指的元素，然后front指向下一個(gè)位置。出隊(duì)操作stringOut_Queue(Queue&q){if(IsEmpty_Queue(q)){ rerurnNull;}else{ stringretvalue; retvalue=q.items[q.front]; q.front=q.front+1; returnretvalue;}}順序隊(duì)列的操作代碼|

取當(dāng)前隊(duì)列長(zhǎng)度intSize_Queue(Queue&q){returnq.rear-q.front;}四、隊(duì)列的實(shí)現(xiàn)-循環(huán)隊(duì)列Implementationofqueue-circularqueue|循環(huán)隊(duì)列|當(dāng)對(duì)順序隊(duì)列不斷執(zhí)行入隊(duì)操作時(shí)，隊(duì)列就有可能出現(xiàn)溢出現(xiàn)象。如已定義順序隊(duì)列q，隊(duì)頭front，隊(duì)尾rear，數(shù)組容量為6，當(dāng)有元素入隊(duì)時(shí)，有下面兩種情況：1.真溢出2.假溢出循環(huán)隊(duì)列|1.真溢出當(dāng)隊(duì)列中的實(shí)際元素個(gè)數(shù)達(dá)到隊(duì)列最大長(zhǎng)度maxsize時(shí)，隊(duì)列滿此時(shí)再入隊(duì)將產(chǎn)生空間溢出現(xiàn)象，如下圖所示真溢出是一種出錯(cuò)狀態(tài)，應(yīng)設(shè)法避免數(shù)

組：frontreara7準(zhǔn)備入隊(duì)，隊(duì)列滿，隊(duì)尾標(biāo)志為maxsize，無(wú)法入隊(duì)。a3數(shù)組下標(biāo)：012345a4a1a2a5a6a7front等于0rear等于隊(duì)列最大長(zhǎng)度6循環(huán)隊(duì)列|2.假溢出由于同時(shí)有入隊(duì)和出隊(duì)兩種操作，隊(duì)頭front、隊(duì)尾rear的值只增加不減少，致使已出隊(duì)元素的空間永遠(yuǎn)無(wú)法重新利用。當(dāng)隊(duì)列中的實(shí)際元素個(gè)數(shù)小于隊(duì)列最大長(zhǎng)度(即數(shù)組容量)maxsize時(shí)，也可能由于隊(duì)尾標(biāo)志已達(dá)到maxsize而不能再做入隊(duì)操作，這時(shí)就出現(xiàn)了假溢出，如圖所示。數(shù)

組：frontreara7準(zhǔn)備入隊(duì)，隊(duì)尾標(biāo)志為maxsize，無(wú)法入隊(duì)。a1,a2已出隊(duì)，隊(duì)列實(shí)際未滿。a3數(shù)組下標(biāo)：012345a4a5a6a7front等于0rear等于隊(duì)列最大長(zhǎng)度6循環(huán)隊(duì)列|將數(shù)組存儲(chǔ)區(qū)想象為一個(gè)首尾相接的圓環(huán)，并稱存儲(chǔ)在其中的隊(duì)列為循環(huán)隊(duì)列。循環(huán)隊(duì)列|基本操作：初始化隊(duì)列：front=rear=0入隊(duì)操作：rear=(rear+1)%maxsize出隊(duì)操作：front=(front+1)%maxsize隊(duì)空