第3章 棧與隊(duì)列 2次2

第3章棧與隊(duì)列1回顧線性表及操作特殊的線性表——棧棧的操作原則棧的順序存儲和鏈?zhǔn)酱鎯Y(jié)構(gòu)棧的操作2第3章棧與隊(duì)列學(xué)習(xí)目的要求:棧的基本概念和棧的基本運(yùn)算。棧在計算機(jī)中的應(yīng)用。隊(duì)列的基本概念和隊(duì)列的基本運(yùn)算。隊(duì)列在計算機(jī)中的應(yīng)用。33.2隊(duì)列3.2.1隊(duì)列的定義隊(duì)列（queue）也是一種特殊的線性表。特殊性：它僅允許在表的一端進(jìn)行插入，在表的另一端進(jìn)行刪除。4a1a2a3a4a5a6rearrearrearrearrearrearfrontfrontfrontfrontfrontfrontrear3.2隊(duì)列3.2.1隊(duì)列的定義隊(duì)列的操作： a1,a2,a3入隊(duì)，

a1,a2出隊(duì)，a4,a5,a6入隊(duì)，

a3,a4,a5,a6出隊(duì)。 由于每個元素必然按照進(jìn)入的次序離隊(duì)，所以又把隊(duì)列稱為“先進(jìn)先出”表（FirstInFirstOut，簡稱FIFO表）53.2隊(duì)列3.2.1隊(duì)列的定義隊(duì)尾：允許進(jìn)行插入操作的一端，由隊(duì)尾指針rear指示隊(duì)空：當(dāng)隊(duì)列中沒有元素時稱為隊(duì)空隊(duì)首：允許進(jìn)行刪除操作的一端，由隊(duì)首指針front指示出隊(duì)：隊(duì)的刪除操作,又稱離隊(duì)入隊(duì)：隊(duì)列的插入操作，又稱進(jìn)隊(duì)6隊(duì)列的基本操作可以歸納為以下幾種:

（1）InitQueue（）;初始化一個空隊(duì)列Q；（2）GetFront（&Q，&y）;取隊(duì)列Q的隊(duì)頭元素，y返回其值，但隊(duì)列Q狀態(tài)不變；（3）EnQuene（&Q，x）;若隊(duì)列Q還有空間，將元素x插入到隊(duì)尾；（4）DelQueue（&Q，&y）;若隊(duì)列Q不為空，刪除隊(duì)列Q的隊(duì)頭元素，y返回其值；（5）Empty（&Q）;判斷隊(duì)列Q是否為空，若為空返回一個真值，否則返回一個假值。3.2隊(duì)列7隊(duì)列的存儲結(jié)構(gòu)：順序存儲——順序隊(duì)列鏈?zhǔn)酱鎯Α滉?duì)列3.2隊(duì)列83.2.2隊(duì)列的順序存儲結(jié)構(gòu)及其運(yùn)算1.順序隊(duì)列隊(duì)列順序存儲結(jié)構(gòu)稱為順序隊(duì)列（sequentialqueue）。順序隊(duì)列與順序表一樣，用一個一維數(shù)組來存放數(shù)據(jù)元素。在內(nèi)存中，用一組連續(xù)的存儲單元順序存放隊(duì)列中各元素。3.2隊(duì)列93.2.2隊(duì)列的順序存儲結(jié)構(gòu)及其運(yùn)算1.順序隊(duì)列#defineMAXLEN10typedef

int

elementtype;typedef

struct

/*隊(duì)列的順序存儲結(jié)構(gòu)定義*/{

int

element[MAXLEN];/*存放隊(duì)列元素的數(shù)組*/

intfront,rear; /*隊(duì)首指針,隊(duì)尾指針*/}SeQueue;3.2隊(duì)列1043210front=rear=-1(1)初始空隊(duì)(2)元素a入隊(duì)(3)元素b,c,d入隊(duì)(4)元素a出隊(duì)43210rearafront=-1rear=043210reardcbafront=-1rear=343210reardcbfront=0rear=3front總結(jié)：（1）在隊(duì)列為空的初始狀態(tài)時，front=rear=-1。（2）每當(dāng)向隊(duì)列插入一個元素，尾指針rear向后移動一位，rear=rear+1。（3）當(dāng)rear=MAXLEN-1時，表示隊(duì)滿;（4）每從隊(duì)列中刪除一個元素時，隊(duì)首指針也向后移動一位，front=front+1。（5）入隊(duì)的所有元素都出隊(duì)后，隊(duì)列為空，此時front=rear;11說明：（1）指針的位置：隊(duì)尾指針指向隊(duì)尾元素（尾元素下標(biāo)），隊(duì)首指針指向隊(duì)首元素的前一個位置；（2）溢出：當(dāng)隊(duì)列滿時（rear=MAXLEN-1）再做入隊(duì)運(yùn)算必定產(chǎn)生空間溢出，簡稱“上溢”；當(dāng)隊(duì)列空時（front=rear）再做出隊(duì)運(yùn)算也將產(chǎn)生溢出，簡稱“下溢”3.2隊(duì)列3.2.2隊(duì)列的順序存儲結(jié)構(gòu)及其運(yùn)算12a1a2a3a4a5a6rearrearrearrearrearrearfrontfrontfrontfrontfrontfrontrear入隊(duì)、出隊(duì)操作：3.2隊(duì)列3.2.2隊(duì)列的順序存儲結(jié)構(gòu)及其運(yùn)算012345入隊(duì)：(1)判滿; (2)移動隊(duì)尾指針rear++；

(3)新元素入隊(duì)尾element[rear]=x;出隊(duì)：(1)判空; (2)移動隊(duì)首指針front++; (3)返回刪除元素x=element[front]；elementfront=rear=-113（1）入隊(duì)int

Enqueue_sq(SeQueue*q,elementtypex){

if(q->rear==MAXLEN-1)return(0);/*隊(duì)列滿返回0*/q->rear++;q->element[q->rear]=x;return(1);}3.2隊(duì)列3.2.2隊(duì)列的順序存儲結(jié)構(gòu)及其運(yùn)算14（2）出隊(duì)int

Delqueue_sq(SeQueue*q,elementtype*x){

if(q->front==q->rear)return(0);/*隊(duì)列空返回0*/else{q->front++;*x=q->element[q->front];return(1);}}3.2隊(duì)列3.2.2隊(duì)列的順序存儲結(jié)構(gòu)及其運(yùn)算15隊(duì)列的存儲結(jié)構(gòu)：順序存儲——順序隊(duì)列鏈?zhǔn)酱鎯Α滉?duì)列3.2隊(duì)列163.2.3隊(duì)列的鏈?zhǔn)酱鎯Y(jié)構(gòu)及其運(yùn)算隊(duì)列的鏈?zhǔn)酱鎯Y(jié)構(gòu)稱為鏈隊(duì)列（linkedqueue）。3.2隊(duì)列用帶頭結(jié)點(diǎn)的單鏈表表示如下：173.2.3隊(duì)列的鏈?zhǔn)酱鎯Y(jié)構(gòu)及其運(yùn)算鏈隊(duì)列的結(jié)構(gòu)定義：typedef

structnode /*定義鏈隊(duì)列結(jié)點(diǎn)*/{

intdata; /*以整型數(shù)據(jù)為例*/

structnode*next; /*存放下一個結(jié)點(diǎn)地址*/}NODE;3.2隊(duì)列183.2.3隊(duì)列的鏈?zhǔn)酱鎯Y(jié)構(gòu)及其運(yùn)算鏈隊(duì)列的操作：（1）鏈隊(duì)列為空條件：front=rear;均指向頭結(jié)點(diǎn)。（2）鏈隊(duì)列不存在滿的情況，除非內(nèi)存已滿。（3）入隊(duì)操作：向隊(duì)尾插入新結(jié)點(diǎn)。（4）出對操作：刪除隊(duì)首結(jié)點(diǎn)。3.2隊(duì)列193.2.3隊(duì)列的鏈?zhǔn)酱鎯Y(jié)構(gòu)及其運(yùn)算3.2隊(duì)列鏈隊(duì)列入隊(duì)操作：xfront①生成新結(jié)點(diǎn)并由指針p指向新結(jié)點(diǎn)，數(shù)據(jù)域賦值為x，指針域?yàn)镹ULL；bc∧③修改隊(duì)尾指針rear=t;parear②向隊(duì)尾插入結(jié)點(diǎn)完成入隊(duì),rear->next=t；∧20（1）入隊(duì)NODE*pushqueue(NODE*rear,intx)/*入隊(duì)操作*/{NODE*p;p=(NODE*)malloc(sizeof(NODE));p->data=x;/*將要插入的數(shù)據(jù)x存儲到結(jié)點(diǎn)p的數(shù)據(jù)域中*/p->next=NULL;rear->next=p;/*將p插入鏈隊(duì)列尾部*/rear=p; /*修改隊(duì)尾指針rear*/

return(rear);}3.2隊(duì)列213.2.3隊(duì)列的鏈?zhǔn)酱鎯Y(jié)構(gòu)及其運(yùn)算3.2隊(duì)列鏈隊(duì)列出隊(duì)操作：①隊(duì)列不為空的情況下，指針p指向隊(duì)列的首元素③返回刪除結(jié)點(diǎn)的數(shù)據(jù)p->data，釋放結(jié)點(diǎn)free(p);rear②刪除隊(duì)首結(jié)點(diǎn)，完成出隊(duì),front->next=p->next；pfrontbc∧a22（2）出隊(duì)NODE*popqueue(NODE*front,NODE*rear,int*x)/*出隊(duì)操作*/{NODE*p;

if(front!=rear)/*判斷鏈隊(duì)列空,若鏈隊(duì)列不空*/{p=front->next; /*p指向鏈隊(duì)列第一個元素*/front->next=p->next; /*將p元素出隊(duì)*/

if(p->next==NULL) /*表示原鏈隊(duì)列中只有一個元素*/rear=front;/*出隊(duì)后,隊(duì)空,修改rear指針*/*x=p->data; /*保存出隊(duì)后的元素值*/

free(p);

return(rear);/*返回rear*/}}3.2隊(duì)列23總結(jié)隊(duì)列的定義隊(duì)列的操作特點(diǎn)隊(duì)列的存儲結(jié)構(gòu)順序隊(duì)列判空、判滿條件隊(duì)列的入隊(duì)、出隊(duì)操作242.循環(huán)隊(duì)列3.2隊(duì)列a1a2a3a4a5a6rearrearrearrearrearrearfrontfrontfrontfront012345順序隊(duì)列操作的過程中可能會出現(xiàn)這樣情況，尾指針指向一維數(shù)組最后，但前面有元素已經(jīng)出隊(duì)，這時要插入元素，仍然發(fā)生溢出，而實(shí)際上隊(duì)列并未滿。這種溢出稱為“假溢出”。為了解決這個問題，下面討論循環(huán)隊(duì)列。252.循環(huán)隊(duì)列循環(huán)隊(duì)列是將存儲隊(duì)列的存儲區(qū)看成是一個首尾相連的環(huán)，即將表示隊(duì)列的數(shù)組元素element［0］與element［MAXLEN-1］連接起來，形成一個環(huán)形表。3.2隊(duì)列當(dāng)隊(duì)列的第MaxSize-1個位置被占用以后，只要隊(duì)列的前端還有可用空間，則把新的數(shù)據(jù)元素加入隊(duì)列的第0號位置。26

540312front=rear=-1rearfeadbc

540312front=-1;rear=52)a,b,c,d,e,f入隊(duì)fedc

540312rearrear=5front=1front3)a,b出隊(duì)1)初始空隊(duì)入隊(duì)操作：rear=(rear+1)%MAXLEN;element[rear]=x;元素出隊(duì)：front=(front+1)%MAXLEN;解決：通過rear=(rear+1)%MAXLEN，讓rear歸零。問題：當(dāng)rear=MAXLEN-1時，再執(zhí)行rear++，數(shù)組下標(biāo)越界。27fegdhc

540312rearfront=rear=1front4)g,h入隊(duì)，隊(duì)滿

540312rearfront=rear=1front5)c,d,e,f,g,h出隊(duì)，隊(duì)空問題：當(dāng)隊(duì)滿和隊(duì)空時條件都是front=rear此時：front=rear是循環(huán)隊(duì)列空的標(biāo)志；（rear+1）%MAXLEN=front是循環(huán)隊(duì)列滿的標(biāo)志。解決方法:(1)設(shè)標(biāo)志位；(2)少用一個元素空間283.2隊(duì)列2.循環(huán)隊(duì)列隊(duì)空條件：rear=front隊(duì)滿條件：(rear+1)%MAXLEN=front入隊(duì)操作：rear=(rear+1)%MAXLEN;element[rear]=x;出隊(duì)操作：front=(front+1)%MAXLEN;x=element[front];總結(jié)：29（1）入隊(duì)int

EnCqueue(CQueue*cq,elementtypex){

if((cq->rear+1)%MAXLEN==cq->front)return(0);/*循環(huán)隊(duì)列滿返回0*/else{

cq->rear=(cq->rear+1)%MAXLEN;

cq->element[cq->rear]=x;return(1);}}3.2隊(duì)列30（2）出隊(duì)int

DelCqueue(CQueue*cq,elementtype*x){

if(cq->rear==cq->front)return(0);/*循環(huán)隊(duì)列空返回0*/else{

cq->front=(cq->front+1)%MAXLEN;*x=cq->element[cq->front];return(1);}}3.2隊(duì)列313.2.4隊(duì)列的應(yīng)用例3.6打印數(shù)據(jù)緩沖區(qū)問題。在打印機(jī)打印的時候，主機(jī)輸出數(shù)據(jù)的速度比打印機(jī)打印的速度要快得多。由于速度不匹配，大大影響了主機(jī)的工作效率。為了解決這個問題，通常是在內(nèi)存中設(shè)置一個打印數(shù)據(jù)緩沖區(qū)。緩沖區(qū)是一塊連續(xù)的存儲空間，把它設(shè)計成循環(huán)隊(duì)列結(jié)構(gòu)，主機(jī)把要打印的數(shù)據(jù)依次寫入到這個緩沖區(qū)中，寫滿后就暫停輸出，主機(jī)此時可以進(jìn)行其他工作。打印機(jī)就從緩沖區(qū)按