隊(duì)列3.2目錄CONTENTE模塊二線性結(jié)構(gòu)棧和隊(duì)列3.1棧蕪湖職業(yè)技術(shù)學(xué)院說(shuō)起隊(duì)列，大家肯定在熟悉不過(guò)了。在我們?nèi)粘Ｉ钪校覀冏龊芏嗍虑槎夹枰抨?duì)。比如：學(xué)生在食堂窗口打飯要排隊(duì)，去超市購(gòu)物，在收銀臺(tái)付款時(shí)要排隊(duì)，甚至去醫(yī)院掛號(hào)也需要排隊(duì)?？傊?，隊(duì)列，在我們?nèi)粘Ｖ?，非常常?jiàn)。畢竟排隊(duì)，是遵守秩序的標(biāo)志，而遵守秩序是文明的標(biāo)志。我們都想要生活在一個(gè)文明的國(guó)度，如果，一個(gè)國(guó)家沒(méi)有秩序，那情況真的不堪設(shè)想。（加圖片）蕪湖職業(yè)技術(shù)學(xué)院同樣的在日常生活中，有許多類似棧的例子，如刷洗盤子時(shí)，依次把每個(gè)洗凈的盤子放到洗好的盤子上。.相當(dāng)于進(jìn)棧；取用盤子時(shí)，從一摞盤子上一個(gè)接一個(gè)地向下拿，相當(dāng)于出棧。洗盤子，簡(jiǎn)單的一項(xiàng)勞動(dòng)，而勞動(dòng)是日常生活的必需品，熱愛(ài)勞動(dòng)也是中華民族的優(yōu)秀傳統(tǒng)。勞動(dòng)最光榮、勞動(dòng)最崇高、勞動(dòng)最偉大、勞動(dòng)最美麗。其中，習(xí)近平總書(shū)記關(guān)于“勞動(dòng)最美麗”的重要論述，是習(xí)近平新時(shí)代中國(guó)特色社會(huì)主義思想的重要組成部分，是馬克思主義勞動(dòng)美學(xué)理論中國(guó)化的最新成果。（加圖片）蕪湖職業(yè)技術(shù)學(xué)院本章我們要解決的問(wèn)題：棧的順序存儲(chǔ)結(jié)構(gòu)和基本操作的實(shí)現(xiàn)。棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)和基本操作的實(shí)現(xiàn)。隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)(循環(huán)隊(duì)列)和基本操作的實(shí)現(xiàn)。隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)和基本操作的實(shí)現(xiàn)。棧和隊(duì)列的各自特點(diǎn)和適用場(chǎng)合。掌握棧和隊(duì)列的定義、特點(diǎn)、典型算法及在實(shí)際中的應(yīng)用。棧3.1數(shù)據(jù)結(jié)構(gòu)模塊二線性結(jié)構(gòu)棧和隊(duì)列3.1棧例

棧的例子現(xiàn)實(shí)生活中的棧3.1棧計(jì)算機(jī)中的棧3.1棧棧的定義棧是限制只能在表的一端進(jìn)行插入和刪除操作的線性表，在表中允許插入和刪除的這一端稱為棧頂(Top)，另一端稱棧底(Bottom)。a1a2……an進(jìn)棧出棧棧底棧頂3.1棧棧的定義當(dāng)棧中沒(méi)有元素時(shí)稱為空棧。處于棧頂位置的數(shù)據(jù)元素稱為棧頂元素。棧的插入操作被稱為進(jìn)?；蛉霔?，刪除操作稱為出?；蛲藯?。棧的特點(diǎn)：先進(jìn)后出（LIFO）a1a2……an進(jìn)棧出棧棧底棧頂3.1棧棧的定義a1a2……an進(jìn)棧出棧棧底棧頂?shù)谝环N：1，2，3進(jìn)，再3，2，1出。出棧次序：321第二種：出棧次序：123第三種：出棧次序：213第四種：出棧次序：132第五種：出棧次序：231

棧對(duì)線性表的插入和刪除的位置做了限制，但是值得注意的是，沒(méi)有對(duì)元素插入和刪除的時(shí)間進(jìn)行限制。所以，并不是說(shuō)元素依a1,a2,…,an的順序進(jìn)棧過(guò)程中不允許元素出棧。例如，1,2,3依次進(jìn)棧，會(huì)有哪些出棧次序?

有沒(méi)有312的出棧次序呢?3.1棧棧的定義動(dòng)畫演示：3.1棧棧的基本操作（1）InitStack(&S)名稱：初始化。作用：構(gòu)造一個(gè)空棧S。前置條件：無(wú)。（2）DestroyStack(&S)名稱：銷毀。作用：棧S被銷毀。前置條件：棧S已存在。（3）ClearStack(&S)名稱：清空。作用：將S清為空棧。前置條件：棧S已存在。3.1棧棧的基本操作（4）StackEmpty(S)名稱：判空。作用：若棧S為空棧，則返回TRUE，否則FALSE。前置條件：棧S已存在。（5）StackLength(S)名稱：棧長(zhǎng)度。作用：返回S的元素個(gè)數(shù)，即棧的長(zhǎng)度。前置條件：棧S已存在。（6）GetTop(S)名稱：獲取棧頂。操作結(jié)果：返回S的棧頂元素。前置條件：棧S已存在且非空。3.1棧棧的基本操作（7）Push(&S,x)名稱：壓入（插入）。作用：插入元素x為新的棧頂元素。前置條件：棧S已存在。（8）Pop(&S)名稱：彈出（刪除）。作用：刪除S的棧頂元素，并返回棧頂數(shù)據(jù)元素。前置條件：棧S已存在且非空。（9）StackTraverse(S)名稱：遍歷。作用：從棧底到棧頂依次對(duì)棧S的每一個(gè)數(shù)據(jù)元素進(jìn)行訪問(wèn)。前置條件：棧S已存在且非空。和線性表類似，棧也有兩種存儲(chǔ)表示方法。1．順序棧棧底位置可以設(shè)置在數(shù)組的任一個(gè)端點(diǎn)，而棧頂是隨著插入和刪除而變化的;設(shè)一個(gè)位置指針top（棧頂指針）來(lái)動(dòng)態(tài)地指示棧頂元素在順序棧中的位置。利用順序存儲(chǔ)方式表示的棧稱為順序棧。棧中的數(shù)據(jù)元素用一個(gè)預(yù)設(shè)的足夠大的一維數(shù)組來(lái)實(shí)現(xiàn)datatypedata[StackSize];3.1棧棧的存儲(chǔ)結(jié)構(gòu)1．順序棧#defineStackSize最大元素?cái)?shù)

typedefstruct{DataTypedata[StackSize];inttop;//記錄棧頂位置}SeqStack；定義一個(gè)指向順序棧的指針：

SeqStack*S;順序棧的類型描述如下：3.1棧棧的存儲(chǔ)結(jié)構(gòu)1．順序棧

通常0下標(biāo)端設(shè)為棧底，這樣空棧時(shí)棧頂指針S->top?=?-1；入棧時(shí)，棧頂指針加1，即S->top++；出棧時(shí)，棧頂指針減1，即S->top--。3.1棧棧的存儲(chǔ)結(jié)構(gòu)1．順序棧3.1棧棧的存儲(chǔ)結(jié)構(gòu)順序棧的基本操作：

3210top-1?？?/⑴置?？眨ǔ跏蓟﹙oidInitStack(SeqStack*S){S->top=-1;}//⑵判?？読ntStackEmpty(SeqStack*S){returnS->top==-1;}3.1棧棧的存儲(chǔ)結(jié)構(gòu)1．順序棧順序棧的基本操作：

3D2C1B0Atop-1棧滿//⑶判棧滿intStackFull(SeqStack*S){returnS->top==StackSize-1;}注：StackSize為棧的空間大小是不是很簡(jiǎn)單呀3.1棧棧的存儲(chǔ)結(jié)構(gòu)1．順序棧順序棧的基本操作：

3210top-1進(jìn)棧操作AB//⑷進(jìn)棧voidPush(SeqStack*S,DataTypex){if(StackFull(S)) printf("Stackoverflow\n");//上溢

else { S->top++;//棧頂位置變量加1 S->data[S->top]=x;//將x入棧

}}3.1棧棧的存儲(chǔ)結(jié)構(gòu)1．順序棧順序棧的基本操作：

3210top-1出棧操作ABx=//⑸出棧DataTypePop(SeqStack*S){ DataTypex; if(StackEmpty(S)) { printf("Stackunderflow\n");//下溢

x='\0'; }else { x=S->data[S->top];//獲取棧頂元素

S->top--;//棧頂位置減1 } returnx;//棧頂元素返回}3.1棧棧的存儲(chǔ)結(jié)構(gòu)順序棧的基本操作：

321B0top-1取棧頂元素ABx=//(6)取棧頂元素DataTypeStackTop（SeqStack*S）{if(StackEmpty(S)) printf("Stackisempty");returnS->data[S->top];}注：只是讀取棧頂元素，top位置不變3.1棧棧的存儲(chǔ)結(jié)構(gòu)1．順序棧順序棧的基本操作：⑴

對(duì)于順序棧，入棧時(shí)，首先判斷是否棧滿。棧滿時(shí)，不能入棧。⑵出棧和讀棧頂元素操作，先判斷棧是否為空，為空不能操作。棧滿的條件為：s->top==StackSize-1說(shuō)明：3.1棧棧的存儲(chǔ)結(jié)構(gòu)1．順序棧3.1棧棧的存儲(chǔ)結(jié)構(gòu)2．雙向棧一個(gè)程序中常常要用到多個(gè)棧，并且必須給每個(gè)棧預(yù)先分配一個(gè)足夠大的存儲(chǔ)空間，勢(shì)必會(huì)造成系統(tǒng)空間浪費(fèi)。多個(gè)棧共用一個(gè)足夠大的連續(xù)存儲(chǔ)空間，則可利用棧的動(dòng)態(tài)特性使它們的存儲(chǔ)空間互補(bǔ)，這就是棧的共享鄰接空間。雙向棧在一維數(shù)組中的實(shí)現(xiàn)。棧的共享中最常見(jiàn)的是兩棧的共享。假設(shè)兩個(gè)棧共享一維數(shù)組stack[MAXNUM]，則可以利用棧的“棧底位置不變，棧頂位置動(dòng)態(tài)變化”的特性，兩個(gè)棧均為空時(shí)，兩個(gè)棧頂分別為-1和MAXNUM，元素進(jìn)棧時(shí)，兩個(gè)棧頂都往中間方向延伸因此，只要整個(gè)數(shù)組stack[MAXNUM]未被占滿，無(wú)論哪個(gè)棧的入棧都不會(huì)發(fā)生上溢，3.1棧棧的存儲(chǔ)結(jié)構(gòu)2．雙向棧C語(yǔ)言定義的這種兩棧共享鄰接空間的結(jié)構(gòu)如下：typedefstruct{Elemtypestack[MAXNUM];intlefttop;//左棧棧頂位置intrighttop;//右棧棧頂位置}dupsqstack;為了識(shí)別左右棧，必須另外設(shè)定標(biāo)志：charstatus;status=’L’;//左棧status=’R’//右棧在進(jìn)行棧操作時(shí)，需要指定棧號(hào)：status=’L’為左棧，status=’R’為右棧；判斷棧滿的條件為：s->lefttop+1==s->righttop;3.1棧棧的存儲(chǔ)結(jié)構(gòu)2．雙向棧（1）初始化操作intInitDupStack(dupsqstack**s){if((s=(dupsqstack*)malloc(sizeof(dupsqstack)))==NULL)returnFALSE;(*s)->lefttop=-1;(*s)->righttop=MAXNUM;returnTRUE;}3.1棧棧的存儲(chǔ)結(jié)構(gòu)2．雙向棧（2）進(jìn)棧操作intPushDupStack(dupsqstack*s,charstatus,Elemtypex){if(s->lefttop+1==s->righttop)returnFALSE;//棧滿if(status==’L’)s->stack[++s->righttop]=x;//左棧進(jìn)棧elseif(status==’R’)s->stack[--s->righttop]=x;//右棧進(jìn)棧elsereturnFALSE;//參數(shù)錯(cuò)誤returnTRUE;}}3.1棧棧的存儲(chǔ)結(jié)構(gòu)2．雙向棧（3）出棧操作ElemtypePopDupStack(dupsqstack*s,charstatus){if(status==’L’){if(s->lefftop<0)returnNULL;//左棧為空elsereturn(s->stack[s->lefttop--]);//左棧出棧}elseif(status==’R’){if(s->righttop>MAXNUM-1)returnNULL;//右棧為空elsereturn(s->stack[s->righttop++]);//右棧出棧}elsereturnNULL;//參數(shù)錯(cuò)誤}3.1棧棧的存儲(chǔ)結(jié)構(gòu)2．雙向棧動(dòng)畫演示如下：

(1)鏈棧的定義：棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)(2)鏈棧類型定義如下：

typedefstructstacknode{ DataTypedata; structstacknode*next;}StackNode;(3)鏈棧的示意圖如下：

注：鏈棧采用的是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，不存在棧滿現(xiàn)象。3．鏈棧3.1棧棧的存儲(chǔ)結(jié)構(gòu)

3.1.3棧的存儲(chǔ)結(jié)構(gòu)(4)鏈棧的操作//初始化為棧空voidInitStack(StackNode**top){*top=NULL;}//判斷棧是否為空intStackEmpty(StackNode*top){returntop==NULL;}

3.1.3棧的存儲(chǔ)結(jié)構(gòu)(4)鏈棧的操作(進(jìn)棧)

3.1.3棧的存儲(chǔ)結(jié)構(gòu)(4)鏈棧的操作(進(jìn)棧)//進(jìn)棧操作voidPush(StackNode**top,DataTypex){ //將元素x插入鏈棧頭部

StackNode*p=(StackNode*)malloc(sizeof(StackNode)); p->data=x; p->next=*top; *top=p;}

3.1.3棧的存儲(chǔ)結(jié)構(gòu)(4)鏈棧的操作(出棧)topabcdep∧ppppNULLDataTypePop(StackNode**top)//出棧操作{DataTypex;StackNode*p=*top;//保存棧頂指針

if(StackEmpty(*top)){ printf("Stackunderflow.");//下溢

x='\0';}else{ x=(*top)->data;//保存棧頂結(jié)點(diǎn)數(shù)據(jù) *top=p->next;//將棧頂結(jié)點(diǎn)從鏈上摘下

free(p);}returnx;}

4．多個(gè)鏈棧3.1棧棧的存儲(chǔ)結(jié)構(gòu)在程序中同時(shí)使用兩個(gè)以上的棧時(shí)，若用多個(gè)單鏈棧時(shí)，操作極為方便。多個(gè)鏈棧的操作可以將多個(gè)單鏈棧的棧頂指針?lè)旁谝粋€(gè)一維數(shù)組slStacktype*top[M];中，讓top[0]，top[1]，…，top[M-1]指向M個(gè)不同的鏈棧，操作時(shí)只需確定棧號(hào)i，然后以top[i]為棧頂指針進(jìn)行棧操作即可實(shí)現(xiàn)各種操作。

4．多個(gè)鏈棧3.1棧棧的存儲(chǔ)結(jié)構(gòu)進(jìn)棧intPushDupLs(slStacktype*top[],intI,Elemtypex){slStacktype*p;if((p=(slStacktype*)malloc(sizeof(slStacktype)))==NULL)returnFALSE;//申請(qǐng)一個(gè)結(jié)點(diǎn)空間p->data=x;p->next=top[i];top[i]=p;returnTRUE;}

4．多個(gè)鏈棧3.1棧棧的存儲(chǔ)結(jié)構(gòu)（2）出棧ElemtypePopDupLs(slStacktype*top[],inti){slStacktype*p;Elemtypex;if(*top==NULL)returnNULL;//空棧

p=*top;*top=(*top)->next;x=p->data;free(p);returnx;}在上面的兩個(gè)算法中，當(dāng)指定棧號(hào)i（0≤i≤M-1）時(shí)，則只對(duì)第i個(gè)鏈棧操作，不會(huì)影響其他鏈隊(duì)列3.2數(shù)據(jù)結(jié)構(gòu)模塊二線性結(jié)構(gòu)棧和隊(duì)列3.2隊(duì)列例

隊(duì)列的例子3.2隊(duì)列例

隊(duì)列的例子隊(duì)列的定義3.2隊(duì)列例

計(jì)算機(jī)中的隊(duì)列隊(duì)列的定義無(wú)論是多進(jìn)程共享cpu的時(shí)間，還是用戶共享，打印機(jī)都需要借助隊(duì)列來(lái)實(shí)現(xiàn)優(yōu)化分配。操作系統(tǒng)中的作業(yè)排隊(duì)就是隊(duì)列數(shù)據(jù)結(jié)構(gòu)的典型應(yīng)用，計(jì)算機(jī)系統(tǒng)中，同時(shí)有幾個(gè)作業(yè)運(yùn)行如果運(yùn)行結(jié)果都需要通過(guò)通道輸出，那就按請(qǐng)求輸出的先后次序排隊(duì)。3.2隊(duì)列隊(duì)列的定義隊(duì)列（queue）是一種先進(jìn)先出（FIFO）的線性表，它限制表的插入在一端進(jìn)行，刪除在另一端進(jìn)行。允許插入的一端叫做隊(duì)尾（rear），允許刪除的一端則稱為隊(duì)頭（front）。3.2隊(duì)列隊(duì)列的定義

3.2隊(duì)列隊(duì)列的定義入隊(duì)、出隊(duì)動(dòng)畫演示：3.2隊(duì)列隊(duì)列的基本操作（1）InitQueue(&Q)名稱：初始化。操作結(jié)果：構(gòu)造一個(gè)空隊(duì)列Q。前置條件：無(wú)。（2）DestroyQueue(&Q)名稱：銷毀。操作結(jié)果：隊(duì)列Q被銷毀，不在存在。前置條件：隊(duì)列Q已經(jīng)存在。（3）ClearQueue(&Q)名稱：清空。操作結(jié)果：將Q清為空隊(duì)列。前置條件：隊(duì)列Q已經(jīng)存在。·3.2隊(duì)列隊(duì)列的基本操作（4）QueueEmpty(Q)名稱：判空。操作結(jié)果：若Q為空列隊(duì)，則返回TRUN，否則FALSE。前置條件：隊(duì)列Q已經(jīng)存在。（5）QueueLength(Q)名稱：長(zhǎng)度。操作結(jié)果：返回Q的元素個(gè)數(shù)，即隊(duì)列的長(zhǎng)度。前置條件：隊(duì)列Q已經(jīng)存在。（6）GetHead(&Q,e)名稱：獲取隊(duì)頭。操作結(jié)果：用e返回Q的隊(duì)頭元素。前置條件：Q為非空隊(duì)列。3.2隊(duì)列隊(duì)列的基本操作（7）EnQueue(&Q,e)名稱：插入隊(duì)尾（入隊(duì)）。操作結(jié)果：插入元素e為Q的新的隊(duì)尾元素。前置條件：隊(duì)列Q已存在。（8）DeQueue(&Q,&e)名稱：刪除隊(duì)頭（出隊(duì)）。操作結(jié)果：刪除Q的隊(duì)頭元素，并用e返回其值。前置條件：Q為非空隊(duì)列。（9）QueueTraverse(Q)名稱：遍歷。操作結(jié)果：從隊(duì)頭到隊(duì)尾，依次對(duì)Q的每一個(gè)數(shù)據(jù)元素進(jìn)行訪問(wèn)。前置條件：Q已存在且非空。隊(duì)列的存儲(chǔ)結(jié)構(gòu)3.2.3隊(duì)列的存儲(chǔ)結(jié)構(gòu)1順序隊(duì)列利用順序存儲(chǔ)方式表示的隊(duì)列稱為順序隊(duì)列。順序隊(duì)列利用一組地址連續(xù)的存儲(chǔ)單元依次存放隊(duì)列中的數(shù)據(jù)元素。通常使用一維數(shù)組來(lái)作為隊(duì)列的順序存儲(chǔ)空間，另外再設(shè)立兩個(gè)指示器：一個(gè)為指向隊(duì)頭元素位置的指針（front），另一個(gè)為指向隊(duì)尾元素位置的指針（rear）。初始化隊(duì)列時(shí)，令front=rear=-1，當(dāng)插入新的數(shù)據(jù)元素時(shí)，尾指示器rear加1，而當(dāng)隊(duì)頭元素出隊(duì)列時(shí)，隊(duì)頭指示器front加1。3.2.3隊(duì)列的存儲(chǔ)結(jié)構(gòu)1順序隊(duì)列用C語(yǔ)言定義的順序存儲(chǔ)結(jié)構(gòu)的隊(duì)列如下：#defineMAXSIZE1024 /*隊(duì)列的最大容量*/typedefstruct{

DataTypedata[MAXSIZE]; /*隊(duì)列的存儲(chǔ)空間*/ intrear,front; /*隊(duì)頭隊(duì)尾指針*/}SeQueue;

順序隊(duì)列類型定義如下：3.2.3隊(duì)列的存儲(chǔ)結(jié)構(gòu)1順序隊(duì)列定義一個(gè)指向隊(duì)列的指針變量：SeQueue*sq;隊(duì)列的數(shù)據(jù)區(qū)為sq->data[0]～sq->data[MAXSIZE?-?1]。隊(duì)頭指針：sq->front。隊(duì)尾指針：sq->rear。設(shè)隊(duì)頭指針指向當(dāng)前隊(duì)頭元素前面一個(gè)位置，隊(duì)尾指針指向隊(duì)尾元素(這樣的設(shè)置是為了某些運(yùn)算的方便，并不是唯一的方法)。置空隊(duì)則為：sq->front?=?-1;sq->rear?=?sq->front;不考慮溢出的情況下，入隊(duì)操作隊(duì)尾

指針加1，指向新位置后，元素入隊(duì)。

sq->rear++;

sq->data[sq->rear]?=?x;3.2.3隊(duì)列的存儲(chǔ)結(jié)構(gòu)1順序隊(duì)列不考慮隊(duì)空的情況下，出隊(duì)操作隊(duì)頭指針加1，表明隊(duì)頭元素出隊(duì)。sq->front++;x?=?sq->data[sq->front];隊(duì)中元素的個(gè)數(shù)：m?=?(sq->rear)?-?(q->front)。3.2.3隊(duì)列的存儲(chǔ)結(jié)構(gòu)1順序隊(duì)列請(qǐng)大家看圖思考GBCFEfrontrear0123456MAXSIZE-1DAH此時(shí)，再有元素入隊(duì)列就會(huì)溢出，可是從圖中看出隊(duì)列并不滿，請(qǐng)大家思考這是為什么呢？這種情況就稱為“假溢出”3.2.3隊(duì)列的存儲(chǔ)結(jié)構(gòu)1順序隊(duì)列解決假溢出的方法之一是將隊(duì)列的數(shù)據(jù)區(qū)看成頭尾相接的循環(huán)結(jié)構(gòu)，頭尾指針的關(guān)系不變，將其稱為“循環(huán)隊(duì)列”如圖所示：q->rear=(q->rear+1)%MAXSIZE;q->data[q->rear]=x;q->front=(q->front+1)%MAXSIZE;x=q->data[q->front];rear01234567EFGHIJfrontrearrearfrontfrontfrontfrontfrontrearrearLKfrontfrontfront入隊(duì)操作為：出隊(duì)操作為:3.2.3隊(duì)列的存儲(chǔ)結(jié)構(gòu)1順序隊(duì)列“隊(duì)滿”和“隊(duì)空”的條件相同。這顯然是必須要解決的一個(gè)問(wèn)題。解決方法：第一種是另設(shè)一個(gè)標(biāo)志位以區(qū)別隊(duì)列是空還是滿。第二種是少用一個(gè)元素空間，少用一個(gè)元素空間，此時(shí)隊(duì)滿的條件是：(sq->rear+1)%MAXSIZE==sq->front；隊(duì)空的條件是：sq->rear==sq->front。第三種方法是設(shè)置一個(gè)計(jì)數(shù)器用來(lái)記錄對(duì)列中的元素總數(shù)，也就是實(shí)際的對(duì)列長(zhǎng)度。下面我們就以第二種方法為例講解循環(huán)隊(duì)列的操作。3.2.3隊(duì)列的存儲(chǔ)結(jié)構(gòu)1順序隊(duì)列#defineMAXSIZE1024 /*隊(duì)列的最大容量*/typedefstruct{ DataTypedata[MAXSIZE]; /*隊(duì)列的存儲(chǔ)空間*/ intrear,front; /*隊(duì)頭隊(duì)尾指針*/}CirQueue;循環(huán)隊(duì)列的類型定義及基本運(yùn)算如下：

voidInitQueue(CirQueue*q){ q->front=-1; q->rear=-1;}循環(huán)隊(duì)列操作⑴置空隊(duì)3.2.3隊(duì)列的存儲(chǔ)結(jié)構(gòu)1順序隊(duì)列循環(huán)隊(duì)列操作

intQueueEmpty(CirQueue*q){ if(q->front==q->rear) return1;else return0;}

intQueueFull(CirQueue*q){ if(q->front==(q->rear+1)%MAXSIZE) return1; else return0;}⑵判隊(duì)空⑶判隊(duì)滿3.2.3隊(duì)列的存儲(chǔ)結(jié)構(gòu)1順序隊(duì)列循環(huán)隊(duì)列操作voidEnQueue(CirQueue*q,DataTypex){ if(QueueFull(q)) { printf("overflow!\n");//隊(duì)滿上溢

return; } else { q->data[q->rear]=x;q->rear=(q->rear+1)%MAXSIZE; }}⑷入隊(duì)3.2.3隊(duì)列的存儲(chǔ)結(jié)構(gòu)1順序隊(duì)列循環(huán)隊(duì)列操作DataTypeDeQueue(CirQueue*q){ DataTypex;if(QueueEmpty(q)) { printf("underflow!\n");//隊(duì)空下溢

x='\0'; } else { x=q->data[q->front];q->front=(q->front+1)%MAXSIZE; }returnx;}(5)出隊(duì)3.2.3隊(duì)列的存儲(chǔ)結(jié)構(gòu)1順序隊(duì)列3.2.3隊(duì)列的存儲(chǔ)結(jié)構(gòu)2鏈隊(duì)列判空條件：q->front->next==NULL;

或q->rear=q->front;為了操作的方便，給鏈隊(duì)列添加一個(gè)頭結(jié)點(diǎn)，并設(shè)定頭指針指向頭結(jié)點(diǎn)。frontrear^fronta1a2ai…an…rear^3.2.3隊(duì)列的存儲(chǔ)結(jié)構(gòu)2鏈隊(duì)列鏈隊(duì)的描述如下：typedefstructnode{ datatypedata; structnode*next;}QNode;typedefstruct{ QNnode*front,*rear;}LQueue;LQueue*q;定義一個(gè)指向鏈隊(duì)的指針：鏈隊(duì)結(jié)點(diǎn)的類型將頭尾指針?lè)庋b在一起的鏈隊(duì)3.2.3隊(duì)列的存儲(chǔ)結(jié)構(gòu)2鏈隊(duì)列按這種思想建立的帶頭結(jié)點(diǎn)的鏈隊(duì)如下圖所示：frontrear^qa1a2ai…an…^frontrearqvoidInit_LQueue(LQueue*q){ q->front=(QNode*)malloc(sizeof(Qnode)); q->rear=q->front; q->front->next=NULL; }鏈隊(duì)的基本運(yùn)算如下：(1)鏈隊(duì)列初始化。申請(qǐng)一個(gè)頭結(jié)點(diǎn)，令隊(duì)頭指針和隊(duì)尾指針都指向它，并令該結(jié)點(diǎn)的next域?yàn)镹ULL。frontrear^q3.2.3隊(duì)列的存儲(chǔ)結(jié)構(gòu)2鏈隊(duì)列鏈隊(duì)的基本運(yùn)算如下：(2)入隊(duì)voidIn_LQueue(LQueue*q,datatypex){ QNode*p; p=(QNode*)malloc(sizeof(QNode)); p->data=x; p->next=NULL; q->rear->next=p; q->rear=p;}a1a2ai…an…^frontrearq3.2.3隊(duì)列的存儲(chǔ)結(jié)構(gòu)2鏈隊(duì)列鏈隊(duì)的基本運(yùn)算如下：(3)判隊(duì)空intEmpty_LQueue(LQueue*q){ if(q->front==q->rear) return0; else return1;}frontrear^q3.2.3隊(duì)列的存儲(chǔ)結(jié)構(gòu)2鏈隊(duì)列鏈隊(duì)的基本運(yùn)算如下：(4)出隊(duì)a1a2ai…an…^frontrearq對(duì)頭元素x出隊(duì)3.2.3隊(duì)列的存儲(chǔ)結(jié)構(gòu)2鏈隊(duì)列鏈隊(duì)的基本運(yùn)算如下：voidOut_LQueue(LQueue*q,datatype*x){ QNode*p; if(Empty_LQueue(q)) printf(″隊(duì)空″); else { p=q->front->next; q->front->next=p->next; *x=p->data;/*隊(duì)頭元素放x中*/ free(p); if(q->front->next==NULL) q->rear=q->front;/*只有一個(gè)元素時(shí)，出隊(duì)后隊(duì)空，此時(shí)還要修改隊(duì)尾指針*/ }}對(duì)頭元素x出隊(duì)3.2.3隊(duì)列的存儲(chǔ)結(jié)構(gòu)2鏈隊(duì)列棧和隊(duì)列的應(yīng)用3.3數(shù)據(jù)結(jié)構(gòu)模塊二線性結(jié)構(gòu)棧和隊(duì)列

3.1.3棧的應(yīng)用利用棧的結(jié)構(gòu)實(shí)現(xiàn)十進(jìn)制轉(zhuǎn)換其他進(jìn)制的算法數(shù)制轉(zhuǎn)換問(wèn)題將十進(jìn)制數(shù)N轉(zhuǎn)換為r進(jìn)制的數(shù)，其轉(zhuǎn)換方法利用輾轉(zhuǎn)相除法：以N=3467，r=8為例轉(zhuǎn)換方法如下：

NN/8（整除）N%8（求余）

34674333低

4335415466606高所以：（3467）10=（6613）8

3.1.3棧的應(yīng)用算法思想：數(shù)制轉(zhuǎn)換問(wèn)題（1）初始化棧，初始化N為要轉(zhuǎn)換的數(shù)，r為進(jìn)制數(shù)（2）判斷N的值為0轉(zhuǎn)（4），否則N%r壓入棧s中（3）用N/r代替N轉(zhuǎn)（2）（4）出棧，出棧序列即為結(jié)果voidmultibase(intn,intb){ inti;

SeqStacks;

InitStack(&s); while(n!=0) { Push(&s,n%b);//進(jìn)棧

n=n/b; }

printf("轉(zhuǎn)換后的結(jié)果："); while(!StackEmpty(&s))

printf("%d",Pop(&s));//輸出出棧元素

printf("\n");}

3.1.3

隊(duì)列的應(yīng)用求迷宮的最短路徑。問(wèn)題：有一個(gè)迷宮,求從入口到出口的最短路徑,其中0表示通路,1表示受阻,規(guī)定向下是X軸,向右是Y軸輸入:第一個(gè)數(shù)迷宮x軸的長(zhǎng)度,第二個(gè)數(shù)迷宮y軸的長(zhǎng)度,緊接著入口點(diǎn)的坐標(biāo)和出口的坐標(biāo),之后是一個(gè)迷宮輸出:迷宮所走的路徑的坐標(biāo)

樣例:INPUT:681168011101111010101001001111011100111001100001100110OUT:(1,1)-->(2,2)-->(3,3)-->(3,4)-->(4,5)-->(4,6)-->(5,7)-->(6,8)

3.1.3

隊(duì)列的應(yīng)用算法思想：求迷宮的最短路徑。

從迷宮入口（1,1）出發(fā)，向四周搜索，記下所有一步能達(dá)到的坐標(biāo)點(diǎn)；然后依次再?gòu)倪@些點(diǎn)出發(fā)，再記下所有已不能達(dá)到的坐標(biāo)點(diǎn)；依次類推，直到迷宮的出口點(diǎn)（n，n）為止，然后從出口點(diǎn)沿搜索路徑回溯到入口。這樣就找到了一條迷宮的最短路徑。

由于先到達(dá)的點(diǎn)先向下搜索，故引入一個(gè)