數(shù)據(jù)結(jié)構(gòu) 第三章 棧和隊列

13.1棧（Stack）第三章棧和隊列1.定義2.邏輯結(jié)構(gòu)3.存儲結(jié)構(gòu)4.運算規(guī)則5.實現(xiàn)方式23.2隊列（Queue）第三章棧和隊列1.定義2.邏輯結(jié)構(gòu)3.存儲結(jié)構(gòu)4.運算規(guī)則5.實現(xiàn)方式3數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容41.定義3.1棧與線性表相同，仍為一對一(1:1)關(guān)系。用順序棧或鏈棧存儲均可，但以順序棧更常見3.存儲結(jié)構(gòu)2.邏輯結(jié)構(gòu)限定只能在表的一端進行插入和刪除運算的線性表。即棧頂53.1棧只能在棧頂運算，且訪問結(jié)點時依照后進先出（LIFO）或先進后出（FILO）的原則。關(guān)鍵是編寫入棧和出棧函數(shù)，具體實現(xiàn)依順序?；蜴湕５拇鎯Y(jié)構(gòu)有別而不同。4.運算規(guī)則5.實現(xiàn)方式

基本操作有：建棧、判斷棧滿或棧空、入棧、出棧、讀棧頂元素值，等等。6棧是僅在表尾進行插入、刪除操作的線性表。表尾(即an端)稱為棧頂

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

)插入元素到棧頂?shù)牟僮?，稱為入棧。從棧頂刪除最后一個元素的操作，稱為出棧。an稱為棧頂元素a1稱為棧底元素想一想：要從棧中取出a1，應當如何操作？強調(diào)：插入和刪除都只能在表的一端（棧頂）進行！1、棧是一種特殊的線性表7Q1：堆棧是什么？它與一般線性表有什么不同？

堆棧是一種特殊的線性表，它只能在表的一端（即棧頂）進行插入和刪除運算。與一般線性表的區(qū)別：僅在于運算規(guī)則不同。一般線性表堆棧邏輯結(jié)構(gòu)：1:1邏輯結(jié)構(gòu)：1:1存儲結(jié)構(gòu)：順序表、鏈表存儲結(jié)構(gòu)：順序棧、鏈棧運算規(guī)則：隨機存取運算規(guī)則：后進先出(LIFO)“進”＝插入=壓入=PUSH（an+1)“出”＝刪除=彈出=POP(an)8a1a2……an順序棧Sai……Q2：順序表和順序棧的操作有何區(qū)別？表頭表尾低地址高地址寫入：S[i]=ai讀出：e=S[i]壓入(PUSH):S[top++]=an+1彈出(POP):e=S[--top]低地址高地址S[i]a1a2aian……順序表S……an+1以線性表

S=(a1,a2,….,an-1,an)為例棧底base棧頂top前提：一定要預設(shè)棧頂指針top棧頂top9棧不存在的條件：base=NULL;棧為空的條件：base=top;棧滿的條件：top-base=stacksize;a1a2……an順序棧Sai……低地址高地址棧底base棧頂topQ2：順序表和順序棧的操作有何區(qū)別？10若入棧動作使地址向高端增長，稱為“向上生成”的棧；若入棧動作使地址向低端增長，稱為“向下生成”的棧；

對于向上生成的堆棧:入棧口訣：堆棧指針top“先壓后加”:S[top++]=an+1出?？谠E：堆棧指針top“先減后彈”:e=S[--top]Q3：什么叫“向上生成”的棧？“向下生成”又是何意？11Q4：為什么要設(shè)計堆棧？它有什么獨特用途？調(diào)用函數(shù)或子程序非它莫屬；遞歸運算的有力工具；用于保護現(xiàn)場和恢復現(xiàn)場；簡化了程序設(shè)計的問題。下面用4個例子來幫助理解堆棧：12voidtest(int&sum){①intx;②scanf(x);if(x==0)③sum=0;else{④test(sum);⑤sum+=x;}⑥printf(sum);⑦}斷點地址入棧例1

閱讀下列遞歸過程，說明其功能。輸入x1≠0輸入x5＝0輸入x2輸入x3輸入x4輸出sum＝0輸出sum＝0+x4輸出sum＝x4+x3輸出sum＝x4+x3+x2輸出sum＝x4+x3+x2+x1注意：最先輸入的數(shù)據(jù)x1

最后才被累加程序功能：對鍵盤輸入數(shù)據(jù)求和，直到輸入0結(jié)束2、堆棧舉例13答：可以通過窮舉所有可能性來求解：①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；合計有5種可能性。例2

一個棧的輸入序列為1,2,3，若在入棧的過程中允許出棧，則可能得到的出棧序列是什么？14例3：一個棧的輸入序列是12345，若在入棧的過程中允許出棧，則棧的輸出序列43512可能實現(xiàn)嗎？12345的輸出呢？答：43512不可能實現(xiàn)，主要是其中的12順序不能實現(xiàn)；12345的輸出可以實現(xiàn)，每壓入一數(shù)便立即彈出即可。思考：有無通用的判別原則？2、堆棧舉例15例4：設(shè)依次進入一個棧的元素序列為c，a，b，d，則可得到出棧的元素序列是：

Ａ）a，b，c，dＢ）c，d，a，b

Ｃ）b，c，d，aＤ）a，c，d，bA）、D）可以，

B）、C）不行。討論：有無通用的判別原則？有！若輸入序列是…,Pi…Pj…Pk…(i<j<k,輸入序號)，一定不存在這樣的輸出序列

…,Pk…Pi…Pj…答：即對于輸入序列1，2，3，不存在輸出序列3，1，22、堆棧舉例16棧的抽象數(shù)據(jù)類型定義:(教材P44-45）ADTStack{數(shù)據(jù)對象：D=……數(shù)據(jù)關(guān)系：R=……基本操作：……}ADTStack入棧、出棧、建棧初始化、判斷棧滿或棧空、讀棧頂元素值等。本節(jié)重點：順序棧和鏈棧的基本操作17

#defineSTACK-INIT-SIZE100

//存儲空間初始分配量

#defineSTACKINCREMENT10

//存儲空間分配增量

typedefstruct{

SElemType*base;

//棧的基址即棧底指針

SElemType*top;

//棧頂指針

intstacksize;

//當前分配的空間

}SqStack;SqStacks;動態(tài)數(shù)組3、順序棧的存儲表示（教材P46)

18順序棧的入棧操作——例如用堆棧存放（A，B，C，D）AACBABAtop核心語句：top=L;

順序棧入棧函數(shù)PUSH（）見教材Push(B);Push(C);Push(D);toptoptoptop低地址LPush(A);高地址MBCD19順序棧出棧操作——例如從棧中取出‘B’DCBAtoptopDCABDCBAtopDCBAtop低地址L高地址MD核心語句：Pop();順序棧出棧函數(shù)POP()見教材Pop();Printf(Pop());20鏈棧的入棧操作和出棧操作（教材省略）(1)鏈棧的構(gòu)造方式——以頭指針為棧頂，在頭指針處插入或刪除.Node*st,*p;intm=sizeof(Node);棧頂棧底棧也可以用鏈式結(jié)構(gòu)來表示，用鏈式結(jié)構(gòu)來表示的棧就是鏈棧sta1a2an-1annextdata鏈棧中每個結(jié)點由兩個域構(gòu)成：data域和next域，其定義為：typedefStructSNode{SElemTypedata;StructSNode*next;}Node;21Push(SElemTypee){p=(Node*)malloc(m);if(!p){上溢}else{p->data=e;p->link=st;st=p;}}StatusPop(){if(st==NULL){下溢}else{e=st->data;p=st;st=st->link; free(p);return(e);}}鏈棧入棧函數(shù)（包括建棧）鏈棧出棧函數(shù)插入表頭從表頭刪除(2)入、出棧操作由此可以看出：一個鏈棧由其棧頂指針唯一指定設(shè)st指向棧頂元素，則st=NULL表示棧空22鏈棧不必設(shè)頭結(jié)點，因為棧頂（表頭）操作頻繁；鏈棧一般不會出現(xiàn)棧滿情況，除非沒有空間導致malloc分配失敗。鏈棧的入棧、出棧操作就是棧頂?shù)牟迦肱c刪除操作，修改指針即可完成。采用鏈棧存儲方式的優(yōu)點是，可使多個棧共享空間；當棧中元素個數(shù)變化較大，且存在多個棧的情況下，鏈棧是棧的首選存儲方式。幾點說明:23例1：數(shù)制轉(zhuǎn)換（十轉(zhuǎn)N）——見教材設(shè)計思路：用棧暫存低位值例2：括號匹配的檢驗————見教材設(shè)計思路：用棧暫存左括號例3

：表達式求值—-————見教材設(shè)計思路：用棧暫存運算符例4：漢諾（Hanoi）塔-———見教材設(shè)計思路：用棧實現(xiàn)遞歸調(diào)用4、棧的應用舉例24例3

表達式求值(這是棧應用的典型例子)

這里，表達式求值的算法是

“算符優(yōu)先法”。例如：編寫算法，用棧實現(xiàn)表達式3*（7–2）求值。一個算術(shù)表達式是由操作數(shù)（x，y，z…）和算符（*，/，+，-，（，），#）組成.表達式的起止符號棧的應用舉例25例3

表達式求值(這是棧應用的典型例子)

這里，表達式求值的算法是

“算符優(yōu)先法”。教材表3.1給出了算符之間的優(yōu)先級專為計算機處理而設(shè)計的表!(1)

表達式求值必須滿足算術(shù)四則運算規(guī)則：

a.從左算到右

b.先乘除，后加減

c.先括號內(nèi)，后括號外棧的應用舉例為了實現(xiàn)算符優(yōu)先算法，可以設(shè)定兩個工作棧，OPND—存放操作數(shù)或運算結(jié)果，OPTR—存放運算符號。26(2)算法思想1）首先置操作數(shù)棧OPND為空棧，表達式的起始符#為運算符棧OPTR的棧底元素2）依次讀入表達式中的每個字符，若運算符是‘#’或棧頂是‘#’，結(jié)束計算，返回OPND棧頂值。

if（是操作數(shù)）→則PUSH（OPND，操作數(shù)）；

if（是運算符）→則與OPTR棧頂元素進行比較，按優(yōu)先級(規(guī)定詳見表3.1）進行操作；if棧頂元素<輸入算符，則算符壓入OPTR棧，并接收下一字符

if棧頂元素=運算符但≠‘#’，則脫括號(彈出左括號)并收下一字；if棧頂元素>運算符，則退棧、按棧頂計算，將結(jié)果壓入OPND棧。且該未入棧的運算符要保留，繼續(xù)與下一個棧頂元素比較！棧的應用舉例273）直到整個表達式求值完畢（當前讀入的字符和OPTR棧的棧頂元素均為#

）

(2)算法思想棧的應用舉例28問：教材表3.1中，1和2哪個對應棧頂元素，哪個對應鍵盤輸入值？答：根據(jù)Precede()函數(shù)可知，1對應棧頂元素由表3.1可看出，右括號)

和井號

#作為2時級別最低；由c規(guī)則得出：*，/，+，-為1時的優(yōu)先權(quán)低于‘（’，高于‘）’由a規(guī)則得出：‘（’=‘）’表明括號內(nèi)的運算已完成；‘#’=‘#’表明表達式求值完畢。附：棧的應用舉例29表達式求值過程的描述：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)3*（7–2）30StatusEvaluateExpression(OperandType&result){InitStack(OPND);InitStack(OPTR);Push(OPTR,’#’);c=getchar();while((c!=‘#’)&&(GetTop(OPTR)!=‘#’)){if(!In(c,OP){Push(OPND,c);c=getchar();}elseswitch(precede(GetTop(OPTR),c)){case‘<’:Push(OPTR,c);c=getchar();break;case‘=’:Pop(OPTR);c=getchar();break;

case‘>’:Pop(OPTR,theta);Pop(OPND,b);a=Pop();Push(OPND,Operate(a,theta,b));break;;}//switch}//while

result=GetTop(OPND);}//EvaluateExpressionOperate=abC是操作符嗎？運算符與棧頂比較并查3.1表程序清單遞歸算法的設(shè)計步驟第一步驟（遞歸步驟）：將規(guī)模較大的原問題分解為一個或多個規(guī)模更小、但具有類似于原問題特性的子問題。即較大的問題遞歸地用較小的子問題來描述，解原問題的方法同樣可用來解這些子問題。第二步驟：確定一個或多個無須分解、可直接求解的最小子問題（稱為遞歸的終止條件）。【例】非負整數(shù)n的階乘可遞歸定義為：31

32傳說在創(chuàng)世紀時，在一個叫Brahma的寺廟里，有三個柱子，其中一柱上有64個盤子從小到大依次疊放，僧侶的工作是將這64個盤子從一根柱子移到另一個柱子上。xyznn–1移動時的規(guī)則：每次只能移動一個盤子；只能小盤子在大盤子上面；可以使用任一柱子。當工作做完之后，就標志著世界末日到來。例4漢諾（Hanoi）塔33分析：設(shè)三根柱子分別為x,y,z,盤子在x柱上，要移到z柱上。1、當n=1時，盤子直接從x柱移到z柱上；2、當n>1

時,則:①

設(shè)法將前n–1個盤子從x移到y(tǒng)柱上（借助z），則盤子n就能從x移到z柱上；②再設(shè)法把n–1個盤子從y移到z柱上(這又是一個與原來相同的問題，只是規(guī)模少１了）。xyznn–1例4漢諾（Hanoi）塔34VoidHanoi(intn,charx,chary,charz){//將n個編號從上到下為1…n的盤子從x柱，借助y柱移到z柱if(n==1)move(x,1,z);//將編號為1的盤子從x柱移到z柱

else{//將n-1個編號從上到下為1…n-1的盤子從x柱，借助y柱移到z柱

Hanoi(n-1,x,z,y);move(x,n,z);//將編號為n的盤子從x柱移到z柱

//將n-1個編號從上到下為1…n-1的盤子從y柱，借助x柱移到z柱

Hanoi(n-1,y,x,z);}}//Hanoi程序設(shè)計如下誰能畫出Hanoi塔的遞歸函數(shù)運行示意圖？棧在遞歸算法的內(nèi)部實現(xiàn)中所起的作用①調(diào)用函數(shù)時：系統(tǒng)將會為調(diào)用者構(gòu)造一個由返回地址、參數(shù)表（實參）和中間變量組成的活動記錄，并將其壓入到由系統(tǒng)提供的運行時刻棧的棧頂，然后將程序的控制權(quán)轉(zhuǎn)移到被調(diào)函數(shù)。若被調(diào)函數(shù)有局部變量，則在運行時刻棧的棧頂也要為其分配相應的空間。因此，活動記錄和這些局部變量形成了一個可供被調(diào)函數(shù)使用的活動結(jié)構(gòu)。

35棧在遞歸算法的內(nèi)部實現(xiàn)中所起的作用注意：

參數(shù)表的內(nèi)容為實參，返回地址是函數(shù)調(diào)用語句的下一指令的位置。②被調(diào)函數(shù)執(zhí)行完畢時：系統(tǒng)將運行時刻棧棧頂?shù)幕顒咏Y(jié)構(gòu)退棧，并根據(jù)退棧的活動結(jié)構(gòu)中所保存的返回地址將程序的控制權(quán)轉(zhuǎn)移給調(diào)用者繼續(xù)執(zhí)行。36遞歸算法的執(zhí)行過程是不斷地自調(diào)用，直到到達遞歸出口才結(jié)束自調(diào)用過程；到達遞歸出口后，遞歸算法開始按最后調(diào)用的過程最先返回的次序返回；返回到最外層的調(diào)用語句時遞歸算法執(zhí)行過程結(jié)束。37堆棧遞歸調(diào)用總結(jié)383.2隊列與線性表相同，仍為一對一關(guān)系。順序隊或鏈隊，以循環(huán)順序隊更常見。存儲結(jié)構(gòu)邏輯結(jié)構(gòu)只能在表的一端進行插入運算，在表的另一端進行刪除運算的線性表。尾部插入首部刪除隊列定義393.2隊列只能在隊首和隊尾運算，且訪問結(jié)點時依照先進先出（FIFO）的原則。關(guān)鍵是掌握入隊和出隊操作，具體實現(xiàn)依順序隊或鏈隊的不同而不同。運算規(guī)則實現(xiàn)方式基本操作：入隊或出隊，建空隊列，判隊空或隊滿等操作。40隊列（Queue）是僅在表尾進行插入操作，在表頭進行刪除操作的線性表。它是一種先進先出（ＦＩＦＯ）的線性表。例如：隊列Q=(a1

,a2,a3,……….,an-1,an)在隊尾插入元素稱為入隊；在隊首刪除元素稱為出隊。隊首隊尾1、隊列是一種特殊線性表41問：為什么要設(shè)計隊列？它有什么獨特用途？離散事件的模擬（模擬事件發(fā)生的先后順序,例如CPU芯片中的指令譯碼隊列）；操作系統(tǒng)中的作業(yè)調(diào)度（一個CPU執(zhí)行多個作業(yè)）；3.簡化程序設(shè)計。答：3.2.1、隊列是一種特殊線性表42隊的實現(xiàn)方式是本節(jié)重點，關(guān)鍵是掌握入隊和出隊操作。

具體實現(xiàn)依存儲結(jié)構(gòu)（鏈隊或順序隊）的不同而不同。隊的抽象數(shù)據(jù)類型定義：ADTQueue{數(shù)據(jù)對象：D=……數(shù)據(jù)關(guān)系：R=……基本操作：……}ADTQueue建隊、入隊或出隊、判隊空或隊滿等，教材P59-60羅列了9種基本操作。3.2.2、隊列實現(xiàn)方式隊列存儲方式431、鏈隊列2、順序隊44鏈隊列類型定義：

typedefstruct{QueuePtrfront;//隊首指針

QueuePtr

rear;//隊尾指針

}LinkQueue;結(jié)點類型定義：

typedefStructQNode{QElemTypedata;//元素StructQNode*next;//指向下一結(jié)點的指針}Qnode,*QueuePtr;關(guān)于整個鏈隊的總體描述鏈隊中任一結(jié)點的結(jié)構(gòu)1.鏈隊列45討論：空鏈隊的特征？Q(隊尾)(隊首)fronta1a2a3^rearpfront^rear③怎樣實現(xiàn)鏈隊的入隊和出隊操作？②鏈隊會滿嗎？front=rear一般不會，因為刪除時有free動作。除非內(nèi)存不足！入隊（尾部插入）：rear->next=s;rear=s;出隊（頭部刪除）：front->next=front->next->next;SD^鏈隊示意圖：完整操作函數(shù)見教材46采用動態(tài)分配空間的形式順序隊類型定義：建隊核心語句：q.base=(QElemType*)malloc(sizeof(QElemType）*QUEUE_MAXSIZE);

//分配空間關(guān)于整個順序隊的總體描述#defineQUEUE-MAXSIZE100//最大隊列長度

typedefstruct{QElemType*base;//隊列的基址

intfront;//隊首指針

intrear;//隊尾指針

}SqQueue2.順序隊47Q(隊尾)(隊首)fronta1a2a3dataa40.......99rear②隊列會滿嗎？極易裝滿！因為數(shù)組通常有長度限制，而其前端空間無法釋放。①空隊列的特征？約定：front=rear隊尾后地址入隊(尾部插入)：Q[rear]=e;rear++

;

出隊(頭部刪除)：e=Q[front];front++;

討論：假溢出！有缺陷③怎樣實現(xiàn)入隊和出隊操作？核心語句如下：用base做數(shù)組名e順序隊示意圖：48解決假溢出的途徑———采用循環(huán)隊列答：在順序隊中，當尾指針已經(jīng)到了數(shù)組的上界，不能再有入隊操作，但其實數(shù)組中還有空位置，這就叫“假溢出”。問：什么叫“假溢出”？如何解決？2.順序隊49a3a2a10123N-1rearfront循環(huán)隊列（臆造）順序隊列a3a2a1frontrear0123..N-1順序隊列轉(zhuǎn)化為循環(huán)隊列50新問題：在循環(huán)隊列中，空隊特征是front=rear；隊滿時也會有front=rear；判決條件將出現(xiàn)二義性！解決方案有三：①使用一個計數(shù)器記錄隊列中元素個數(shù)（即隊列長度）；②加設(shè)標志位，刪除時置1,插入時置0,則可識別當前front=rear屬于何種情況③人為浪費一個單元，則隊滿特征可改為front=(rear+1)%N；順序隊列轉(zhuǎn)化為循環(huán)隊列51隊空條件:front=rear(初始化時：front=rear)隊滿條件：front=(rear+1)%N(N=maxsize)隊列長度（即數(shù)據(jù)元素個數(shù)）：L=（N＋rear－front）%NJ2J3 J1J4

J5frontrear

實際中常選用方案3（人為浪費一個單元）：即front和rear二者之一指向?qū)嵲?，另一個指向空閑元素。

問3：在具有n個單元的循環(huán)隊列中，隊滿時共有多少個元素？N-1個6

問1：左圖中隊列maxsizeN=？問2：左圖中隊列長度L=？5順序隊列轉(zhuǎn)化為循環(huán)隊列52（Ａ）r－f（Ｂ）（n＋f－r）%n（Ｃ）n＋r－f（Ｄ）（n＋r－f）%n要分析4種公式哪種最合理？當r≥f時（A）合理；當r<f時（C）合理；答：綜合2種情況，以（D）的表達最為合理例2：在一個循環(huán)隊列中，若約定隊首指針指向隊首元素的前一個位置。那么，從循環(huán)隊列中刪除一個元素時，其操作是先移動隊首指針取出元素√，后。例1：數(shù)組Ｑ[n]用來表示一個循環(huán)隊列，f為當前隊列頭元素的前一位置，r為隊尾元素的位置。假定隊列中元素的個數(shù)小于n，計算隊列中元素的公式為:示例53例3：一循環(huán)隊列如下圖所示，若先刪除4個元素，接著再插入4個元素，請問隊頭和隊尾指針分別指向哪個位置?J2J3 J1J4

J5front=1rear=0解：由圖可知，隊頭和隊尾指針的初態(tài)分別為front=1和rear=0。刪除4個元素后f=5；再插入4個元素后，r=(0+4)%6=4

front=5J6J5J7J8J9rear=4rear=0front=554討論：循環(huán)隊列的基本操作如何實現(xiàn)？以建隊、入隊和出隊三種基本操作為例1）初始化一個空隊列算法要求：生成一空隊列算法操作：為隊列分配基本容量空間設(shè)置隊列為空隊列，其特征即：

front=rear=0（也可為任意單元，如1，2，…甚至-1）循環(huán)隊列操作551)建隊的完整算法StatusInitQueue(SqQueue&q)//初始化空循環(huán)隊列q{q.base=(QElemType*)malloc(sizeof(QElemType）*QUEUE_MAXSIZE);//分配空間if(!q.base)exit(OVERFLOW);//內(nèi)存分配失敗，退出程序q.front=q.rear=0;//置空隊列returnOK;}//InitQueue;56算法說明：向循環(huán)隊列的隊尾插入一個元素分析：(1)插入前應當先判斷隊列是否滿？

if((q.rear+1)%QUEUE_MAXSIZE)==q.front)retur