第3章 棧與隊列 2次2

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

a1,a2出隊，a4,a5,a6入隊，

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

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

int

elementtype;typedef

struct

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

int

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

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

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

Enqueue_sq(SeQueue*q,elementtypex){

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

Delqueue_sq(SeQueue*q,elementtype*x){

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

structnode /*定義鏈隊列結(jié)點*/{

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

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

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

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

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

free(p);

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

540312front=rear=-1rearfeadbc

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

540312rearrear=5front=1front3)a,b出隊1)初始空隊入隊操作：rear=(rear+1)%MAXLEN;element[rear]=x;元素出隊：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入隊，隊滿

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

EnCqueue(CQueue*cq,elementtypex){

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

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

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

DelCqueue(CQueue*cq,elementtype*x){

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

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