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

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

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

隊頭（即將出隊的顧客的位置）；

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

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

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

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

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

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

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

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

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

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