數(shù)據(jù)結(jié)構(gòu)棧和隊(duì)列課件

數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容3.1棧（Stack）

第三章棧和隊(duì)列3.2隊(duì)列（Queue）1.定義2.邏輯結(jié)構(gòu)3.存儲(chǔ)結(jié)構(gòu)4.運(yùn)算規(guī)則5.實(shí)現(xiàn)方式1.定義2.邏輯結(jié)構(gòu)3.存儲(chǔ)結(jié)構(gòu)4.運(yùn)算規(guī)則5.實(shí)現(xiàn)方式3.1棧（Stack）第三章棧和隊(duì)列3.21.定義3.1棧與同線性表相同，仍為一對(duì)一關(guān)系。用順序?；蜴湕４鎯?chǔ)均可，但以順序棧更常見只能在棧頂(表尾)運(yùn)算，且訪問結(jié)點(diǎn)時(shí)依照后進(jìn)先出（LIFO）或先進(jìn)后出（FILO）的原則。關(guān)鍵是編寫入棧和出棧函數(shù)，具體實(shí)現(xiàn)依順序棧或鏈棧的不同而不同。基本操作有入棧、出棧、讀棧頂元素值、建棧、或判斷棧滿、棧空等。3.存儲(chǔ)結(jié)構(gòu)4.運(yùn)算規(guī)則5.實(shí)現(xiàn)方式

2.邏輯結(jié)構(gòu)限定只能在表的一端進(jìn)行插入和刪除運(yùn)算的線性表（只能在棧頂操作）1.定義3.1棧與同線性表相同，仍為一對(duì)一關(guān)系。用順問：堆棧是什么？它與一般線性表有什么不同？3.1棧答：堆棧是一種特殊的線性表，它只能在表的一端（即棧頂）進(jìn)行插入和刪除運(yùn)算。與一般線性表的區(qū)別：僅在于運(yùn)算規(guī)則不同。一般線性表堆棧邏輯結(jié)構(gòu)：一對(duì)一邏輯結(jié)構(gòu)：一對(duì)一存儲(chǔ)結(jié)構(gòu)：順序表、鏈表存儲(chǔ)結(jié)構(gòu)：順序棧、鏈棧運(yùn)算規(guī)則：隨機(jī)存取運(yùn)算規(guī)則：后進(jìn)先出(LIFO)“進(jìn)”＝壓入=PUSH（x)“出”＝彈出=POP(y)問：堆棧是什么？它與一般線性表有什么不同？3.1棧答：堆棧是僅在表尾進(jìn)行插入、刪除操作的線性表。表尾(即an端)稱為棧頂

top;表頭(即a1端)稱為棧底base例如：棧s=(a1,a2,a3,……….,an-1,an)a1稱為棧底元素

an

稱為棧頂元素插入元素到棧頂（即表尾）的操作，稱為入棧。從棧頂（即表尾）刪除最后一個(gè)元素的操作，稱為出棧。教材P44對(duì)棧有更詳細(xì)定義：強(qiáng)調(diào)：插入和刪除都只能在表的一端（棧頂）進(jìn)行！棧是僅在表尾進(jìn)行插入、刪除操作的線性表。例如：棧s=順序棧示意圖sa1a2a3dataa4(棧底)(棧頂)99...3210top順序棧示意圖sa1a2a3dataa4(棧底)(棧頂a1a2……an順序棧Sai……表和棧的操作區(qū)別——對(duì)線性表

s=(a1,a2,….,an-1,an)表頭表尾棧底base棧頂top低地址高地址寫入：v[i]=ai讀出：x=v[i]壓入：PUSH(an+1)彈出：POP(x)前提：一定要預(yù)設(shè)棧頂指針top！低地址高地址v[i]a1a2aian……順序表V[n]……an+1a1a2……an順序棧Sai……表和棧的操作區(qū)別——入棧操作——例如用堆棧存放（A，B，C，D）

（注意要遵循“后進(jìn)先出”原則）AACBABAtop核心語句：top=L;

順序棧中的PUSH函數(shù)statusPush(ElemTypex){if(top>M){上溢}elsev[top++]=x;}Push(B);Push(C);Push(D);toptoptoptop低地址LPush(A);高地址MBCD入棧操作——例如用堆棧存放（A，B，C，D）

（

出棧操作——例如從棧中取出‘B’

（注意要遵循“后進(jìn)先出”原則）DCBAtoptopDCABDCBAtopDCBAtop低地址L高地址MD核心語句：Pop();Pop();Printf(Pop());順序棧中的POP函數(shù)statusPop(){if(top=L){下溢}else{y=v[--top];return(y);}}出棧操作——例如從棧中取出‘B’

（注意要遵例1：一個(gè)棧的輸入序列是12345，若在入棧的過程中允許出棧，則棧的輸出序列43512可能實(shí)現(xiàn)嗎？12345的輸出呢？43512不可能實(shí)現(xiàn)，主要是其中的12順序不能實(shí)現(xiàn)；

12345的輸出可以實(shí)現(xiàn)，只需壓入一個(gè)立即彈出一個(gè)即可。

435612中到了12順序不能實(shí)現(xiàn)；

135426可以實(shí)現(xiàn)。例2：如果一個(gè)棧的輸入序列為123456，能否得到435612和135426的出棧序列？答：答：例1：一個(gè)棧的輸入序列是12345，若在入棧的過程中允許出棧例3（嚴(yán)題集3.1）一個(gè)棧的輸入序列為123，若在入棧的過程中允許出棧，則可能得到的出棧序列是什么？答：可以通過窮舉所有可能性來求解：①1入1出，2入2出，3入3出，即123；②1入1出，2、3入3、2出，即132；③1、2入，2出，3入3出，即231；④1、2入，2、1出，3入3出，即213；⑤1、2、3入，3、2、1出，即321；合計(jì)有5種可能性。例3（嚴(yán)題集3.1）一個(gè)棧的輸入序列為123，若在入棧的過程補(bǔ)充1：若入棧動(dòng)作使地址向高端增長(zhǎng)，稱為“向上生成”的棧；若入棧動(dòng)作使地址向低端增長(zhǎng)，稱為“向下生成”的棧；

對(duì)于向上生成的棧入?？谠E：堆棧指針top先壓后加（v[top++]=x）；出?？谠E：堆棧指針top先減后彈（y=v[--top])

。3.1棧補(bǔ)充2：

棧不存在的條件：base=NULL;

棧為空的條件：base=top;

棧滿的條件：top-base=stacksize;補(bǔ)充1：3.1棧補(bǔ)充2：棧不存在的條件：bas補(bǔ)充3：鏈棧

鏈棧示意圖s(棧底)(棧頂)topa3a2a4a1^補(bǔ)充3：鏈棧

鏈棧的入棧函數(shù)、出棧函數(shù)

（以頭指針為棧頂，在頭指針處插入或刪除?。┕舱f明部分：

typedefstructsnode{SElemTypedata;structsnode*link;}NODE;NODE*st,*p;intm=sizeof(NODE); 鏈棧的入棧函數(shù)、出棧函數(shù)

（以頭指針為棧頂，在頭指針處插入Push(SElemTypex){p=(NODE*)malloc(m);if(!p){上溢}else{p->data=x;p->link=st;st=p;}}

Statuspop()

{if(st==NULL){下溢}else{y=st->data;p=st;st=st->link; free(p);return(y);}}鏈棧入棧函數(shù)鏈棧出棧函數(shù)插入表頭從表頭刪除Push(SElemTypex)Statusp①鏈棧不必設(shè)頭結(jié)點(diǎn)，因?yàn)闂ｍ敚ū眍^）操作頻繁；②采用鏈棧存儲(chǔ)方式，可使多個(gè)棧共享空間；當(dāng)棧中元素個(gè)數(shù)變化較大，且存在多個(gè)棧的情況下，鏈棧是棧的首選存儲(chǔ)方式。說明①鏈棧不必設(shè)頭結(jié)點(diǎn)，因?yàn)闂ｍ敚ū眍^）操作頻繁；說明問：為什么要設(shè)計(jì)堆棧？它有什么獨(dú)特用途？調(diào)用函數(shù)或子程序非它莫屬；遞歸運(yùn)算的有力工具；用于保護(hù)現(xiàn)場(chǎng)和恢復(fù)現(xiàn)場(chǎng)；簡(jiǎn)化了程序設(shè)計(jì)的問題。答：?jiǎn)枺簽槭裁匆O(shè)計(jì)堆棧？它有什么獨(dú)特用途？調(diào)用函數(shù)或子程序非它

數(shù)制轉(zhuǎn)換（十轉(zhuǎn)N）——P48

設(shè)計(jì)思路：用棧暫存低位值例2：括號(hào)匹配的檢驗(yàn)————P49

設(shè)計(jì)思路：用棧暫存左括號(hào)例3

：表達(dá)式求值—————P52

設(shè)計(jì)思路：用棧暫存運(yùn)算符例4：漢諾儀（Hanoi）塔——P55

設(shè)計(jì)思路：用棧實(shí)現(xiàn)遞歸調(diào)用例1：數(shù)制轉(zhuǎn)換（十轉(zhuǎn)N）——P48例1：例3

表達(dá)式求值(這是棧應(yīng)用的典型例子)

這里，表達(dá)式求值的算法是“算符優(yōu)先法”。例如：3*（7–2）（1）要正確求值，首先了解算術(shù)四則運(yùn)算的規(guī)則：

a.

從左算到右

b.

先乘除，后加減

c.

先括號(hào)內(nèi)，后括號(hào)外由此，此表達(dá)式的計(jì)算順序?yàn)椋?/p>

3*（7–2）=3*5=15例3表達(dá)式求值(這是棧應(yīng)用的典型例子)例如（2）根據(jù)上述三條運(yùn)算規(guī)則，在運(yùn)算的每一步中，對(duì)任意相繼出現(xiàn)的算符1和2

，都要比較優(yōu)先權(quán)關(guān)系。算符優(yōu)先法所依據(jù)的算符間的優(yōu)先關(guān)系見教材P53表3.1

（是提供給計(jì)算機(jī)用的表?。┯杀砜煽闯?，右括號(hào))

和井號(hào)

#

作為2時(shí)級(jí)別最低；

由c規(guī)則得出：*，/，+，-為1時(shí)的優(yōu)先權(quán)低于‘（’，高于‘）’由a規(guī)則得出：‘（’=‘）’表明括號(hào)內(nèi)運(yùn)算，已算完?！?’=‘#’表明表達(dá)式求值完畢。棧的應(yīng)用（表達(dá)式求值）（2）根據(jù)上述三條運(yùn)算規(guī)則，在運(yùn)算的每一步中，對(duì)任意相繼出現(xiàn)（3）算法思想：設(shè)定兩棧：操作符棧OPTR，操作數(shù)棧OPND棧初始化：設(shè)操作數(shù)棧OPND為空；操作符棧OPTR的棧底元素為表達(dá)式起始符‘#’；依次讀入字符：是操作數(shù)則入OPND棧，是操作符則要判斷：

if棧頂元素>操作符，則退棧、計(jì)算，結(jié)果壓入OPND棧；棧頂元素=操作符且不為‘#’，脫括號(hào)（彈出左括號(hào)）；棧頂元素<操作符，壓入OPTR棧。棧的應(yīng)用（表達(dá)式求值）（3）算法思想：棧的應(yīng)用（表達(dá)式求值）棧的應(yīng)用（表達(dá)式求值）OPTROPNDINPUTOPERATE3*(7-2)#Push(opnd,’3’)

#*(7-2)#3#Push(optr,’*’)#,*3(7-2)#Push(optr,’(’)#,*,(37-2)#Push(opnd,’7’)#,*,(3,7-2)#Push(optr,’-’)#,*,(,－3,72)#Push(opnd,’2’)#,*,(,－3,7,2)#Operate(7-2)#,*,(3,5)#Pop(optr)#,*3,5#Operate(3*5)#15#GetTop(opnd)棧的應(yīng)用（表達(dá)式求值）OPTROPNDINPUTOPERATStatusEvaluateExpression(OperandType&result){InitStack(OPND);InitStack(OPTR);Push(OPTR,’#’);c=getchar();while((c!=‘#’)&&(GetTop(OPTR)!=‘#’)){if(!In(c,OP){Push(OPND,c);c=getchar();}elseswitch(compare(c,GetTop(OPTR))){case‘>’:Push(OPTR,c);c=getchar();break;case‘=’:Pop(OPTR);c=getchar();break;

case‘<’:temat=Pop(OPTR);b=Pop();a=Pop();

result=Operate(a,temat,b);Push(OPND,result);c=getchar();break;}//switch}//whileresult=GetTop(OPND);}//EvaluateExpression此函數(shù)在哪里？StatusEvaluateExpression(

定義3.2隊(duì)列與同線性表相同，仍為一對(duì)一關(guān)系。順序隊(duì)或鏈隊(duì)，以循環(huán)順序隊(duì)更常見。只能在隊(duì)首和隊(duì)尾運(yùn)算，且訪問結(jié)點(diǎn)時(shí)依照先進(jìn)先出（FIFO）的原則。關(guān)鍵是掌握入隊(duì)和出隊(duì)操作，具體實(shí)現(xiàn)依順序隊(duì)或鏈隊(duì)的不同而不同?；静僮饔腥腙?duì)或出隊(duì)，建空隊(duì)列，判隊(duì)空或隊(duì)滿等操作。3.存儲(chǔ)結(jié)構(gòu)4.運(yùn)算規(guī)則5.實(shí)現(xiàn)方式

2.邏輯結(jié)構(gòu)只能在表的一端進(jìn)行插入運(yùn)算，在表的另一端進(jìn)行刪除運(yùn)算的線性表（頭刪尾插）定義3.2隊(duì)列與同線性表相同，仍為一對(duì)一關(guān)系。隊(duì)列（Queue）是僅在表尾進(jìn)行插入操作，在表頭進(jìn)行刪除操作的線性表。表尾即an端，稱為隊(duì)尾

；表頭即a1端，稱為隊(duì)頭。它是一種先進(jìn)先出（ＦＩＦＯ）的線性表。例如：隊(duì)列Q=(a1,a2,a3,……….,an-1,an)插入元素稱為入隊(duì)；刪除元素稱為出隊(duì)。隊(duì)頭隊(duì)尾教材P59對(duì)隊(duì)列有更詳細(xì)定義：隊(duì)列的抽象數(shù)據(jù)類型定義見教材Ｐ59－60隊(duì)列的存儲(chǔ)結(jié)構(gòu)為鏈隊(duì)或順序隊(duì)

（常用循環(huán)順序隊(duì)）隊(duì)列（Queue）是僅在表尾進(jìn)行插入操作，在表頭進(jìn)行刪除操鏈隊(duì)列示意圖討論：空隊(duì)列的特征？Q(隊(duì)尾)(隊(duì)首)fronta1a2a3^rearpfront^rear③怎樣實(shí)現(xiàn)入隊(duì)和出隊(duì)操作？入隊(duì)（尾部插入）：rear->next=S;rear=S;出隊(duì)（頭部刪除）：front->next=p->next;完整動(dòng)作設(shè)計(jì)參見教材P61-62②隊(duì)列會(huì)滿嗎？front=rear一般不會(huì)，因?yàn)閯h除時(shí)有free動(dòng)作。除非內(nèi)存不足！鏈隊(duì)列示意圖討論：Q(隊(duì)尾)(隊(duì)首)fronta1a2a3^構(gòu)造一個(gè)空隊(duì)列StatusInitQuene(LinkQuene&Q){Q.front=Q.rear=(QuenePtr)malloc(sizeof(QNode));if(!Q.front)exit(OVERFLOW);Q.front—>next=NULL;returnOK;}構(gòu)造一個(gè)空隊(duì)列2)銷毀隊(duì)列StatusDestroyQuene(LinkQuene&Q){while(Q.front){Q.rear=Q.front—>next;free(Q.front);Q.front=Q.rear;}returnOK;}2)銷毀隊(duì)列3)入隊(duì)StatusEnQuene(LinkQuene&Q,QElemTypee){//插入元素e為Q的新的隊(duì)尾元素

p=(QuenePtr)malloc(sizeof(Qnode));if(!p)exit(OVERFLOW);p—>data=e;p—>next=NULL;Q.rear—>next=p;Q.rear=p;returnOK;}3)入隊(duì)4)出隊(duì)StatusDeQuene(LinkQuene&Q,QElemType&e){//若隊(duì)列不空，則刪除Q的隊(duì)頭元素，用e返回其值，并返回OK；

//否則返回ERRORif(Q.front==Q.rear)returnERROR;p=Q.front—>next;e=p—>data;Q.front—>next=p—>next;if(Q.rear==p)Q.rear=Q.front;free(p);returnOK;}4)出隊(duì)順序隊(duì)示意圖Q(隊(duì)尾)(隊(duì)首)fronta1a2a3dataa40.......99rear②隊(duì)列會(huì)滿嗎？很可能會(huì)，因?yàn)閿?shù)組前端空間無法釋放。因此數(shù)組應(yīng)當(dāng)有長(zhǎng)度限制。①空隊(duì)列的特征？約定：front=rear隊(duì)尾后地址入隊(duì)(尾部插入)：v[rear]=e;rear++;出隊(duì)(頭部刪除)：x=v[front];front++;討論：假溢出

有缺陷③怎樣實(shí)現(xiàn)入隊(duì)和出隊(duì)操作？3.2隊(duì)列順序隊(duì)示意圖Q(隊(duì)尾)(隊(duì)首)fronta1a2a3d問：什么叫“假溢出”？如何解決？答：在順序隊(duì)中，當(dāng)尾指針已經(jīng)到了數(shù)組的上界，不能再有入隊(duì)操作，但其實(shí)數(shù)組中還有空位置，這就叫“假溢出”。3.2隊(duì)列解決假溢出的途徑———采用循環(huán)隊(duì)列問：什么叫“假溢出”？如何解決？答：在順序隊(duì)中，當(dāng)尾指針已a(bǔ)3a2a10123N-1rearfront循環(huán)隊(duì)列（臆造）順序隊(duì)列a3a2a1frontrear0123..N-1新問題：在循環(huán)隊(duì)列中，空隊(duì)特征是front=rear；隊(duì)滿時(shí)也會(huì)有front=rear；判決條件將出現(xiàn)二義性！解決方案有三：①加設(shè)標(biāo)志位，讓刪除動(dòng)作使其為1,插入動(dòng)作使其為0,則可識(shí)別當(dāng)前front=rear②使用一個(gè)計(jì)數(shù)器記錄隊(duì)列中元素個(gè)數(shù)（即隊(duì)列長(zhǎng)度）；③人為浪費(fèi)一個(gè)單元，令隊(duì)滿特征為front=(rear+1)%N；a3a2a10123N-1rearfront循環(huán)隊(duì)列（臆造）隊(duì)空條件:front=rear(初始化時(shí)：front=rear)隊(duì)滿條件：front=(rear+1)%N(N=maxsize)隊(duì)列長(zhǎng)度：L=（N＋rear－front）%N

J2

J3

J1

J4

J5frontrear

選用空閑單元法：即front和rear之一指向?qū)嵲?，另一指向空閑元素。

問3：在具有n個(gè)單元的循環(huán)隊(duì)列中，隊(duì)滿時(shí)共有多少個(gè)元素？n-1個(gè)5

問2：左圖中隊(duì)列長(zhǎng)度L=？問1：左圖中隊(duì)列容量

maxsizeN=？6隊(duì)空條件:front=rear(初始注意：循環(huán)隊(duì)列中的“長(zhǎng)度”到底是指總長(zhǎng)度還是數(shù)據(jù)元素個(gè)數(shù)？

答：一般情況下的長(zhǎng)度（L）是指元素個(gè)數(shù)（不含頭結(jié)點(diǎn)或空閑單元），而maxsizeN才是指所有單元總數(shù)，即“容量”。注意：J6

J5J7J8

J9例1：一循環(huán)隊(duì)列如下圖所示，若先刪除4個(gè)元素，接著再插入4個(gè)元素，請(qǐng)問隊(duì)頭和隊(duì)尾指針分別指向哪個(gè)位置?J2

J3

J1

J4

J5frontrear解：由圖可知，隊(duì)頭和隊(duì)尾指針的初態(tài)分別為front=1和rear=6。frontrear刪除4個(gè)元素后front=5；再插入4個(gè)元素后，rear=4。frontfrontfrontfrontfrontJ6J5J7J8J9例1：例2：數(shù)組Ｑ[n]用來表示一個(gè)循環(huán)隊(duì)列，f為當(dāng)前隊(duì)列頭元素的前一位置，r為隊(duì)尾元素的位置。假定隊(duì)列中元素的個(gè)數(shù)小于n，計(jì)算隊(duì)列中元素的公式為:（Ａ）r－f（Ｂ）（n＋f－r）%n（Ｃ）n＋r－f（Ｄ）（n＋r－f）%n4種公式哪種合理？當(dāng)r≥f時(shí)（A）合理；當(dāng)r<f時(shí)（C）合理；分析：綜合2種情況，以（D）的表達(dá)最為合理例3：在一個(gè)循環(huán)隊(duì)列中，若約定隊(duì)首指針指向隊(duì)首元素的前一個(gè)位置。那么，從循環(huán)隊(duì)列中刪除一個(gè)元素時(shí)，其操作是先

，后

。

移動(dòng)隊(duì)首指針取出元素√例2：數(shù)組Ｑ[n]用來表示一個(gè)循環(huán)隊(duì)列，f為當(dāng)前隊(duì)列頭元問：為什么要設(shè)計(jì)隊(duì)列？它有什么獨(dú)特用途？離散事件的模擬（模擬事件發(fā)生的先后順序）；操作系統(tǒng)中多道作業(yè)的處理（一個(gè)CPU執(zhí)行多個(gè)作業(yè)）；3.簡(jiǎn)化程序設(shè)計(jì)。答：循環(huán)隊(duì)列的操作實(shí)現(xiàn)見教材P64問：為什么要設(shè)計(jì)隊(duì)列？它有什么獨(dú)特用途？離散事件的模擬（模擬循環(huán)隊(duì)列的操作實(shí)現(xiàn)1）初始化一空隊(duì)列算法要求：生成一空隊(duì)列算法操作：為隊(duì)列分配基本容量空間設(shè)置隊(duì)列為空隊(duì)列，即front=rear=0（也可為任意單元，如2，或4）;循環(huán)隊(duì)列的操作實(shí)現(xiàn)1）初始化一空隊(duì)列算法要求：生成一空隊(duì)列算法：StatusInitQueue(SqQueue&q){//初始化空循環(huán)隊(duì)列qq.base=(QElemType*)malloc(sizeof(QElemType）*QUEUE_MAXSIZE);

//分配空間if(!q.base)exit(OVERFLOW);

//失敗，退出程序q.front=q.rear=0;

//置空隊(duì)列returnOK;}//InitQueue;新開單元的地址為0則表示內(nèi)存不足算法：StatusInitQueue(SqQu算法說明：向循環(huán)隊(duì)列的隊(duì)尾插入一個(gè)元素分析：(1)插入前應(yīng)當(dāng)先判斷隊(duì)列是否滿

if((q.rear+1)%

QUEUE_MAXSIZE)==q.front)returnERROR;(2）插入動(dòng)作

q.base[q.rear]=e;q.rear=(q.rear+1)%QUEUE_MAXSIZE;

2）入隊(duì)操作算法說明：向循環(huán)隊(duì)列的隊(duì)尾插入一個(gè)元素2）入隊(duì)操作StatusEnQueue(SqQueue&q,QElemTypee){//向循環(huán)隊(duì)列q的隊(duì)尾加入一個(gè)元素eif((q.rear+1)%QUEUE_MAXSIZE==q.front)returnERROR;q.base[q.rear]=e;//存儲(chǔ)

q.rear=(q.rear+1)%QUEUE_MAXSIZE;//指針后移returnOK;}//EnQueue;2）入隊(duì)操作（完整函數(shù)）StatusEnQueue(SqQueue&q,3）出隊(duì)操作算法說明：刪除隊(duì)頭元素，返回其值e分析：（1）在刪除前應(yīng)當(dāng)判斷隊(duì)列是否空；

if(q.front=q.rear)returnERROR;

（2）插入動(dòng)作分析；因?yàn)殛?duì)頭指針front指向隊(duì)頭元素的位置，所以：

e=q.base[q.front];q.front=(q.front+1)%QUEUE_MAXSIZE;

3）出隊(duì)操作算法說明：刪除隊(duì)頭元素，返回其值eStatusDeQueue

(SqQueue&q,QElemType&e){//若隊(duì)列不空，刪除循環(huán)隊(duì)列q的隊(duì)頭元素，

//由e返回其值，并返回OKif(q.front==q.rear)returnERROR;//隊(duì)列空e=q.base[q.front];

//隊(duì)頭元素出隊(duì)q.front=(q.front+1)%QUEUE_MAXSIZE;

//指針后移returnOK;}//DeQueue算法：StatusDeQueue(SqQueue討論（代本章小結(jié)）線性表、棧與隊(duì)的異同點(diǎn)相同點(diǎn)：邏輯結(jié)構(gòu)相同，都是線性的；都可以用順序存儲(chǔ)或鏈表存儲(chǔ)；棧和隊(duì)列是兩種特殊的線性表，即受限的線性表（只是對(duì)插入、刪除運(yùn)算加以限制）。不同點(diǎn)：①運(yùn)算規(guī)則不同，線性表為隨機(jī)存取，而棧是只允許在一端進(jìn)行插入和刪除運(yùn)算，因而是后進(jìn)先出表LIFO；隊(duì)列是只允許在一端進(jìn)行插入、另一端進(jìn)行刪除運(yùn)算，因而是先進(jìn)先出表FIFO。②用途不同，線性表比較通用；堆棧用于函數(shù)調(diào)用、遞歸和簡(jiǎn)化設(shè)計(jì)等；隊(duì)列用于離散事件模擬、多道作業(yè)處理和簡(jiǎn)化設(shè)計(jì)等。討論（代本章小結(jié)）線性表、棧與隊(duì)的異同點(diǎn)數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容3.1棧（Stack）

第三章棧和隊(duì)列3.2隊(duì)列（Queue）1.定義2.邏輯結(jié)構(gòu)3.存儲(chǔ)結(jié)構(gòu)4.運(yùn)算規(guī)則5.實(shí)現(xiàn)方式1.定義2.邏輯結(jié)構(gòu)3.存儲(chǔ)結(jié)構(gòu)4.運(yùn)算規(guī)則5.實(shí)現(xiàn)方式3.1棧（Stack）第三章棧和隊(duì)列3.21.定義3.1棧與同線性表相同，仍為一對(duì)一關(guān)系。用順序棧或鏈棧存儲(chǔ)均可，但以順序棧更常見只能在棧頂(表尾)運(yùn)算，且訪問結(jié)點(diǎn)時(shí)依照后進(jìn)先出（LIFO）或先進(jìn)后出（FILO）的原則。關(guān)鍵是編寫入棧和出棧函數(shù)，具體實(shí)現(xiàn)依順序棧或鏈棧的不同而不同。基本操作有入棧、出棧、讀棧頂元素值、建棧、或判斷棧滿、?？盏?。3.存儲(chǔ)結(jié)構(gòu)4.運(yùn)算規(guī)則5.實(shí)現(xiàn)方式

2.邏輯結(jié)構(gòu)限定只能在表的一端進(jìn)行插入和刪除運(yùn)算的線性表（只能在棧頂操作）1.定義3.1棧與同線性表相同，仍為一對(duì)一關(guān)系。用順問：堆棧是什么？它與一般線性表有什么不同？3.1棧答：堆棧是一種特殊的線性表，它只能在表的一端（即棧頂）進(jìn)行插入和刪除運(yùn)算。與一般線性表的區(qū)別：僅在于運(yùn)算規(guī)則不同。一般線性表堆棧邏輯結(jié)構(gòu)：一對(duì)一邏輯結(jié)構(gòu)：一對(duì)一存儲(chǔ)結(jié)構(gòu)：順序表、鏈表存儲(chǔ)結(jié)構(gòu)：順序棧、鏈棧運(yùn)算規(guī)則：隨機(jī)存取運(yùn)算規(guī)則：后進(jìn)先出(LIFO)“進(jìn)”＝壓入=PUSH（x)“出”＝彈出=POP(y)問：堆棧是什么？它與一般線性表有什么不同？3.1棧答：堆棧是僅在表尾進(jìn)行插入、刪除操作的線性表。表尾(即an端)稱為棧頂

top;表頭(即a1端)稱為棧底base例如：棧s=(a1,a2,a3,……….,an-1,an)a1稱為棧底元素

an

稱為棧頂元素插入元素到棧頂（即表尾）的操作，稱為入棧。從棧頂（即表尾）刪除最后一個(gè)元素的操作，稱為出棧。教材P44對(duì)棧有更詳細(xì)定義：強(qiáng)調(diào)：插入和刪除都只能在表的一端（棧頂）進(jìn)行！棧是僅在表尾進(jìn)行插入、刪除操作的線性表。例如：棧s=順序棧示意圖sa1a2a3dataa4(棧底)(棧頂)99...3210top順序棧示意圖sa1a2a3dataa4(棧底)(棧頂a1a2……an順序棧Sai……表和棧的操作區(qū)別——對(duì)線性表

s=(a1,a2,….,an-1,an)表頭表尾棧底base棧頂top低地址高地址寫入：v[i]=ai讀出：x=v[i]壓入：PUSH(an+1)彈出：POP(x)前提：一定要預(yù)設(shè)棧頂指針top！低地址高地址v[i]a1a2aian……順序表V[n]……an+1a1a2……an順序棧Sai……表和棧的操作區(qū)別——入棧操作——例如用堆棧存放（A，B，C，D）

（注意要遵循“后進(jìn)先出”原則）AACBABAtop核心語句：top=L;

順序棧中的PUSH函數(shù)statusPush(ElemTypex){if(top>M){上溢}elsev[top++]=x;}Push(B);Push(C);Push(D);toptoptoptop低地址LPush(A);高地址MBCD入棧操作——例如用堆棧存放（A，B，C，D）

（

出棧操作——例如從棧中取出‘B’

（注意要遵循“后進(jìn)先出”原則）DCBAtoptopDCABDCBAtopDCBAtop低地址L高地址MD核心語句：Pop();Pop();Printf(Pop());順序棧中的POP函數(shù)statusPop(){if(top=L){下溢}else{y=v[--top];return(y);}}出棧操作——例如從棧中取出‘B’

（注意要遵例1：一個(gè)棧的輸入序列是12345，若在入棧的過程中允許出棧，則棧的輸出序列43512可能實(shí)現(xiàn)嗎？12345的輸出呢？43512不可能實(shí)現(xiàn)，主要是其中的12順序不能實(shí)現(xiàn)；

12345的輸出可以實(shí)現(xiàn)，只需壓入一個(gè)立即彈出一個(gè)即可。

435612中到了12順序不能實(shí)現(xiàn)；

135426可以實(shí)現(xiàn)。例2：如果一個(gè)棧的輸入序列為123456，能否得到435612和135426的出棧序列？答：答：例1：一個(gè)棧的輸入序列是12345，若在入棧的過程中允許出棧例3（嚴(yán)題集3.1）一個(gè)棧的輸入序列為123，若在入棧的過程中允許出棧，則可能得到的出棧序列是什么？答：可以通過窮舉所有可能性來求解：①1入1出，2入2出，3入3出，即123；②1入1出，2、3入3、2出，即132；③1、2入，2出，3入3出，即231；④1、2入，2、1出，3入3出，即213；⑤1、2、3入，3、2、1出，即321；合計(jì)有5種可能性。例3（嚴(yán)題集3.1）一個(gè)棧的輸入序列為123，若在入棧的過程補(bǔ)充1：若入棧動(dòng)作使地址向高端增長(zhǎng)，稱為“向上生成”的棧；若入棧動(dòng)作使地址向低端增長(zhǎng)，稱為“向下生成”的棧；

對(duì)于向上生成的棧入?？谠E：堆棧指針top先壓后加（v[top++]=x）；出?？谠E：堆棧指針top先減后彈（y=v[--top])

。3.1棧補(bǔ)充2：

棧不存在的條件：base=NULL;

棧為空的條件：base=top;

棧滿的條件：top-base=stacksize;補(bǔ)充1：3.1棧補(bǔ)充2：棧不存在的條件：bas補(bǔ)充3：鏈棧

鏈棧示意圖s(棧底)(棧頂)topa3a2a4a1^補(bǔ)充3：鏈棧

鏈棧的入棧函數(shù)、出棧函數(shù)

（以頭指針為棧頂，在頭指針處插入或刪除?。┕舱f明部分：

typedefstructsnode{SElemTypedata;structsnode*link;}NODE;NODE*st,*p;intm=sizeof(NODE); 鏈棧的入棧函數(shù)、出棧函數(shù)

（以頭指針為棧頂，在頭指針處插入Push(SElemTypex){p=(NODE*)malloc(m);if(!p){上溢}else{p->data=x;p->link=st;st=p;}}

Statuspop()

{if(st==NULL){下溢}else{y=st->data;p=st;st=st->link; free(p);return(y);}}鏈棧入棧函數(shù)鏈棧出棧函數(shù)插入表頭從表頭刪除Push(SElemTypex)Statusp①鏈棧不必設(shè)頭結(jié)點(diǎn)，因?yàn)闂ｍ敚ū眍^）操作頻繁；②采用鏈棧存儲(chǔ)方式，可使多個(gè)棧共享空間；當(dāng)棧中元素個(gè)數(shù)變化較大，且存在多個(gè)棧的情況下，鏈棧是棧的首選存儲(chǔ)方式。說明①鏈棧不必設(shè)頭結(jié)點(diǎn)，因?yàn)闂ｍ敚ū眍^）操作頻繁；說明問：為什么要設(shè)計(jì)堆棧？它有什么獨(dú)特用途？調(diào)用函數(shù)或子程序非它莫屬；遞歸運(yùn)算的有力工具；用于保護(hù)現(xiàn)場(chǎng)和恢復(fù)現(xiàn)場(chǎng)；簡(jiǎn)化了程序設(shè)計(jì)的問題。答：?jiǎn)枺簽槭裁匆O(shè)計(jì)堆棧？它有什么獨(dú)特用途？調(diào)用函數(shù)或子程序非它

數(shù)制轉(zhuǎn)換（十轉(zhuǎn)N）——P48

設(shè)計(jì)思路：用棧暫存低位值例2：括號(hào)匹配的檢驗(yàn)————P49

設(shè)計(jì)思路：用棧暫存左括號(hào)例3

：表達(dá)式求值—————P52

設(shè)計(jì)思路：用棧暫存運(yùn)算符例4：漢諾儀（Hanoi）塔——P55

設(shè)計(jì)思路：用棧實(shí)現(xiàn)遞歸調(diào)用例1：數(shù)制轉(zhuǎn)換（十轉(zhuǎn)N）——P48例1：例3

表達(dá)式求值(這是棧應(yīng)用的典型例子)

這里，表達(dá)式求值的算法是“算符優(yōu)先法”。例如：3*（7–2）（1）要正確求值，首先了解算術(shù)四則運(yùn)算的規(guī)則：

a.

從左算到右

b.

先乘除，后加減

c.

先括號(hào)內(nèi)，后括號(hào)外由此，此表達(dá)式的計(jì)算順序?yàn)椋?/p>

3*（7–2）=3*5=15例3表達(dá)式求值(這是棧應(yīng)用的典型例子)例如（2）根據(jù)上述三條運(yùn)算規(guī)則，在運(yùn)算的每一步中，對(duì)任意相繼出現(xiàn)的算符1和2

，都要比較優(yōu)先權(quán)關(guān)系。算符優(yōu)先法所依據(jù)的算符間的優(yōu)先關(guān)系見教材P53表3.1

（是提供給計(jì)算機(jī)用的表?。┯杀砜煽闯?，右括號(hào))

和井號(hào)

#

作為2時(shí)級(jí)別最低；

由c規(guī)則得出：*，/，+，-為1時(shí)的優(yōu)先權(quán)低于‘（’，高于‘）’由a規(guī)則得出：‘（’=‘）’表明括號(hào)內(nèi)運(yùn)算，已算完?！?’=‘#’表明表達(dá)式求值完畢。棧的應(yīng)用（表達(dá)式求值）（2）根據(jù)上述三條運(yùn)算規(guī)則，在運(yùn)算的每一步中，對(duì)任意相繼出現(xiàn)（3）算法思想：設(shè)定兩棧：操作符棧OPTR，操作數(shù)棧OPND棧初始化：設(shè)操作數(shù)棧OPND為空；操作符棧OPTR的棧底元素為表達(dá)式起始符‘#’；依次讀入字符：是操作數(shù)則入OPND棧，是操作符則要判斷：

if棧頂元素>操作符，則退棧、計(jì)算，結(jié)果壓入OPND棧；棧頂元素=操作符且不為‘#’，脫括號(hào)（彈出左括號(hào)）；棧頂元素<操作符，壓入OPTR棧。棧的應(yīng)用（表達(dá)式求值）（3）算法思想：棧的應(yīng)用（表達(dá)式求值）棧的應(yīng)用（表達(dá)式求值）OPTROPNDINPUTOPERATE3*(7-2)#Push(opnd,’3’)

#*(7-2)#3#Push(optr,’*’)#,*3(7-2)#Push(optr,’(’)#,*,(37-2)#Push(opnd,’7’)#,*,(3,7-2)#Push(optr,’-’)#,*,(,－3,72)#Push(opnd,’2’)#,*,(,－3,7,2)#Operate(7-2)#,*,(3,5)#Pop(optr)#,*3,5#Operate(3*5)#15#GetTop(opnd)棧的應(yīng)用（表達(dá)式求值）OPTROPNDINPUTOPERATStatusEvaluateExpression(OperandType&result){InitStack(OPND);InitStack(OPTR);Push(OPTR,’#’);c=getchar();while((c!=‘#’)&&(GetTop(OPTR)!=‘#’)){if(!In(c,OP){Push(OPND,c);c=getchar();}elseswitch(compare(c,GetTop(OPTR))){case‘>’:Push(OPTR,c);c=getchar();break;case‘=’:Pop(OPTR);c=getchar();break;

case‘<’:temat=Pop(OPTR);b=Pop();a=Pop();

result=Operate(a,temat,b);Push(OPND,result);c=getchar();break;}//switch}//whileresult=GetTop(OPND);}//EvaluateExpression此函數(shù)在哪里？StatusEvaluateExpression(

定義3.2隊(duì)列與同線性表相同，仍為一對(duì)一關(guān)系。順序隊(duì)或鏈隊(duì)，以循環(huán)順序隊(duì)更常見。只能在隊(duì)首和隊(duì)尾運(yùn)算，且訪問結(jié)點(diǎn)時(shí)依照先進(jìn)先出（FIFO）的原則。關(guān)鍵是掌握入隊(duì)和出隊(duì)操作，具體實(shí)現(xiàn)依順序隊(duì)或鏈隊(duì)的不同而不同?；静僮饔腥腙?duì)或出隊(duì)，建空隊(duì)列，判隊(duì)空或隊(duì)滿等操作。3.存儲(chǔ)結(jié)構(gòu)4.運(yùn)算規(guī)則5.實(shí)現(xiàn)方式

2.邏輯結(jié)構(gòu)只能在表的一端進(jìn)行插入運(yùn)算，在表的另一端進(jìn)行刪除運(yùn)算的線性表（頭刪尾插）定義3.2隊(duì)列與同線性表相同，仍為一對(duì)一關(guān)系。隊(duì)列（Queue）是僅在表尾進(jìn)行插入操作，在表頭進(jìn)行刪除操作的線性表。表尾即an端，稱為隊(duì)尾

；表頭即a1端，稱為隊(duì)頭。它是一種先進(jìn)先出（ＦＩＦＯ）的線性表。例如：隊(duì)列Q=(a1,a2,a3,……….,an-1,an)插入元素稱為入隊(duì)；刪除元素稱為出隊(duì)。隊(duì)頭隊(duì)尾教材P59對(duì)隊(duì)列有更詳細(xì)定義：隊(duì)列的抽象數(shù)據(jù)類型定義見教材Ｐ59－60隊(duì)列的存儲(chǔ)結(jié)構(gòu)為鏈隊(duì)或順序隊(duì)

（常用循環(huán)順序隊(duì)）隊(duì)列（Queue）是僅在表尾進(jìn)行插入操作，在表頭進(jìn)行刪除操鏈隊(duì)列示意圖討論：空隊(duì)列的特征？Q(隊(duì)尾)(隊(duì)首)fronta1a2a3^rearpfront^rear③怎樣實(shí)現(xiàn)入隊(duì)和出隊(duì)操作？入隊(duì)（尾部插入）：rear->next=S;rear=S;出隊(duì)（頭部刪除）：front->next=p->next;完整動(dòng)作設(shè)計(jì)參見教材P61-62②隊(duì)列會(huì)滿嗎？front=rear一般不會(huì)，因?yàn)閯h除時(shí)有free動(dòng)作。除非內(nèi)存不足！鏈隊(duì)列示意圖討論：Q(隊(duì)尾)(隊(duì)首)fronta1a2a3^構(gòu)造一個(gè)空隊(duì)列StatusInitQuene(LinkQuene&Q){Q.front=Q.rear=(QuenePtr)malloc(sizeof(QNode));if(!Q.front)exit(OVERFLOW);Q.front—>next=NULL;returnOK;}構(gòu)造一個(gè)空隊(duì)列2)銷毀隊(duì)列StatusDestroyQuene(LinkQuene&Q){while(Q.front){Q.rear=Q.front—>next;free(Q.front);Q.front=Q.rear;}returnOK;}2)銷毀隊(duì)列3)入隊(duì)StatusEnQuene(LinkQuene&Q,QElemTypee){//插入元素e為Q的新的隊(duì)尾元素

p=(QuenePtr)malloc(sizeof(Qnode));if(!p)exit(OVERFLOW);p—>data=e;p—>next=NULL;Q.rear—>next=p;Q.rear=p;returnOK;}3)入隊(duì)4)出隊(duì)StatusDeQuene(LinkQuene&Q,QElemType&e){//若隊(duì)列不空，則刪除Q的隊(duì)頭元素，用e返回其值，并返回OK；

//否則返回ERRORif(Q.front==Q.rear)returnERROR;p=Q.front—>next;e=p—>data;Q.front—>next=p—>next;if(Q.rear==p)Q.rear=Q.front;free(p);returnOK;}4)出隊(duì)順序隊(duì)示意圖Q(隊(duì)尾)(隊(duì)首)fronta1a2a3dataa40.......99rear②隊(duì)列會(huì)滿嗎？很可能會(huì)，因?yàn)閿?shù)組前端空間無法釋放。因此數(shù)組應(yīng)當(dāng)有長(zhǎng)度限制。①空隊(duì)列的特征？約定：front=rear隊(duì)尾后地址入隊(duì)(尾部插入)：v[rear]=e;rear++;出隊(duì)(頭部刪除)：x=v[front];front++;討論：假溢出

有缺陷③怎樣實(shí)現(xiàn)入隊(duì)和出隊(duì)操作？3.2隊(duì)列順序隊(duì)示意圖Q(隊(duì)尾)(隊(duì)首)fronta1a2a3d問：什么叫“假溢出”？如何解決？答：在順序隊(duì)中，當(dāng)尾指針已經(jīng)到了數(shù)組的上界，不能再有入隊(duì)操作，但其實(shí)數(shù)組中還有空位置，這就叫“假溢出”。3.2隊(duì)列解決假溢出的途徑———采用循環(huán)隊(duì)列問：什么叫“假溢出”？如何解決？答：在順序隊(duì)中，當(dāng)尾指針已a(bǔ)3a2a10123N-1rearfront循環(huán)隊(duì)列（臆造）順序隊(duì)列a3a2a1frontrear0123..N-1新問題：在循環(huán)隊(duì)列中，空隊(duì)特征是front=rear；隊(duì)滿時(shí)也會(huì)有front=rear；判決條件將出現(xiàn)二義性！解決方案有三：①加設(shè)標(biāo)志位，讓刪除動(dòng)作使其為1,插入動(dòng)作使其為0,則可識(shí)別當(dāng)前front=rear②使用一個(gè)計(jì)數(shù)器記錄隊(duì)列中元素個(gè)數(shù)（即隊(duì)列長(zhǎng)度）；③人為浪費(fèi)一個(gè)單元，令隊(duì)滿特征為front=(rear+1)%N；a3a2a10123N-1rearfront循環(huán)隊(duì)列（臆造）隊(duì)空條件:front=rear(初始化時(shí)：front=rear)隊(duì)滿條件：front=(rear+1)%N(N=maxsize)隊(duì)列長(zhǎng)度：L=（N＋rear－front）%N

J2

J3

J1

J4

J5frontrear

選用空閑單元法：即front和rear之一指向?qū)嵲兀硪恢赶蚩臻e元素。

問3：在具有n個(gè)單元的循環(huán)隊(duì)列中，隊(duì)滿時(shí)共有多少個(gè)元素？n-1個(gè)5

問2：左圖中隊(duì)列長(zhǎng)度L=？問1：左圖中隊(duì)列容量

maxsizeN=？6隊(duì)空條件:front=rear(初始注意：循環(huán)隊(duì)列中的“長(zhǎng)度”到底是指總長(zhǎng)度還是數(shù)據(jù)元素個(gè)數(shù)？

答：一般情況下的長(zhǎng)度（L）是指元素個(gè)數(shù)（不含頭結(jié)點(diǎn)或空閑單元），而maxsizeN才是指所有單元總數(shù)，即“容量”。注意：J6

J5J7J8

J9例1：一循環(huán)隊(duì)列如下圖所示，若先刪除4個(gè)元素，接著再插入4個(gè)元素，請(qǐng)問隊(duì)頭和隊(duì)尾指針分別指向哪個(gè)位置?J2

J3

J1

J4

J5frontrear解：由圖可知，隊(duì)頭和隊(duì)尾指針的初態(tài)分別為front=1和rear=6。frontrear刪除4個(gè)元素后front=5；再插入4個(gè)元素后，rear=4。frontfrontfrontfrontfrontJ6J5J7J8J9例1：例2：數(shù)組Ｑ[n]用來表示一個(gè)循環(huán)隊(duì)列，f為當(dāng)前隊(duì)列頭元素的前一位置，r為隊(duì)尾元素的位置。假定隊(duì)列中元素的個(gè)數(shù)小于n，計(jì)算隊(duì)列中元素的公式為:（Ａ）r－f（Ｂ）（n＋f－r）%n（Ｃ）n＋r－f（Ｄ）（n＋r－f）%n4種公式哪種合理？當(dāng)r≥f時(shí)（A）合理；當(dāng)r<f時(shí)（C）合