數(shù)據(jù)結構棧和隊列課件

數(shù)據(jù)結構課程的內容數(shù)據(jù)結構課程的內容3.1棧（Stack）

第三章棧和隊列3.2隊列（Queue）1.定義2.邏輯結構3.存儲結構4.運算規(guī)則5.實現(xiàn)方式1.定義2.邏輯結構3.存儲結構4.運算規(guī)則5.實現(xiàn)方式3.1棧（Stack）第三章棧和隊列3.21.定義3.1棧與同線性表相同，仍為一對一關系。用順序?；蜴湕４鎯?，但以順序棧更常見只能在棧頂(表尾)運算，且訪問結點時依照后進先出（LIFO）或先進后出（FILO）的原則。關鍵是編寫入棧和出棧函數(shù)，具體實現(xiàn)依順序?；蜴湕５牟煌煌??；静僮饔腥霔?、出棧、讀棧頂元素值、建棧、或判斷棧滿、棧空等。3.存儲結構4.運算規(guī)則5.實現(xiàn)方式

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

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

an

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

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

（注意要遵循“后進先出”原則）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’

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

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

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

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

135426可以實現(xiàn)。例2：如果一個棧的輸入序列為123456，能否得到435612和135426的出棧序列？答：答：例1：一個棧的輸入序列是12345，若在入棧的過程中允許出棧例3（嚴題集3.1）一個棧的輸入序列為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；合計有5種可能性。例3（嚴題集3.1）一個棧的輸入序列為123，若在入棧的過程補充1：若入棧動作使地址向高端增長，稱為“向上生成”的棧；若入棧動作使地址向低端增長，稱為“向下生成”的棧；

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

。3.1棧補充2：

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

棧為空的條件：base=top;

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

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

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

（以頭指針為棧頂，在頭指針處插入或刪除！）公共說明部分：

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ù)變化較大，且存在多個棧的情況下，鏈棧是棧的首選存儲方式。說明①鏈棧不必設頭結點，因為棧頂（表頭）操作頻繁；說明問：為什么要設計堆棧？它有什么獨特用途？調用函數(shù)或子程序非它莫屬；遞歸運算的有力工具；用于保護現(xiàn)場和恢復現(xiàn)場；簡化了程序設計的問題。答：問：為什么要設計堆棧？它有什么獨特用途？調用函數(shù)或子程序非它

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

設計思路：用棧暫存低位值例2：括號匹配的檢驗————P49

設計思路：用棧暫存左括號例3

：表達式求值—————P52

設計思路：用棧暫存運算符例4：漢諾儀（Hanoi）塔——P55

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

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

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

a.

從左算到右

b.

先乘除，后加減

c.

先括號內，后括號外由此，此表達式的計算順序為：

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

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

（是提供給計算機用的表?。┯杀砜煽闯?，右括號)

和井號

#

作為2時級別最低；

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

if棧頂元素>操作符，則退棧、計算，結果壓入OPND棧；棧頂元素=操作符且不為‘#’，脫括號（彈出左括號）；棧頂元素<操作符，壓入OPTR棧。棧的應用（表達式求值）（3）算法思想：棧的應用（表達式求值）棧的應用（表達式求值）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)棧的應用（表達式求值）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隊列與同線性表相同，仍為一對一關系。順序隊或鏈隊，以循環(huán)順序隊更常見。只能在隊首和隊尾運算，且訪問結點時依照先進先出（FIFO）的原則。關鍵是掌握入隊和出隊操作，具體實現(xiàn)依順序隊或鏈隊的不同而不同。基本操作有入隊或出隊，建空隊列，判隊空或隊滿等操作。3.存儲結構4.運算規(guī)則5.實現(xiàn)方式

2.邏輯結構只能在表的一端進行插入運算，在表的另一端進行刪除運算的線性表（頭刪尾插）定義3.2隊列與同線性表相同，仍為一對一關系。隊列（Queue）是僅在表尾進行插入操作，在表頭進行刪除操作的線性表。表尾即an端，稱為隊尾

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

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

p=(QuenePtr)malloc(sizeof(Qnode));if(!p)exit(OVERFLOW);p—>data=e;p—>next=NULL;Q.rear—>next=p;Q.rear=p;returnOK;}3)入隊4)出隊StatusDeQuene(LinkQuene&Q,QElemType&e){//若隊列不空，則刪除Q的隊頭元素，用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)出隊順序隊示意圖Q(隊尾)(隊首)fronta1a2a3dataa40.......99rear②隊列會滿嗎？很可能會，因為數(shù)組前端空間無法釋放。因此數(shù)組應當有長度限制。①空隊列的特征？約定：front=rear隊尾后地址入隊(尾部插入)：v[rear]=e;rear++;出隊(頭部刪除)：x=v[front];front++;討論：假溢出

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

J2

J3

J1

J4

J5frontrear

選用空閑單元法：即front和rear之一指向實元素，另一指向空閑元素。

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

問2：左圖中隊列長度L=？問1：左圖中隊列容量

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

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

J5J7J8

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

J3

J1

J4

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

，后

。

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

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

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

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

if((q.rear+1)%

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

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

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

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

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

（2）插入動作分析；因為隊頭指針front指向隊頭元素的位置，所以：

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

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

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

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

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

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

第三章棧和隊列3.2隊列（Queue）1.定義2.邏輯結構3.存儲結構4.運算規(guī)則5.實現(xiàn)方式1.定義2.邏輯結構3.存儲結構4.運算規(guī)則5.實現(xiàn)方式3.1棧（Stack）第三章棧和隊列3.21.定義3.1棧與同線性表相同，仍為一對一關系。用順序?；蜴湕４鎯?，但以順序棧更常見只能在棧頂(表尾)運算，且訪問結點時依照后進先出（LIFO）或先進后出（FILO）的原則。關鍵是編寫入棧和出棧函數(shù)，具體實現(xiàn)依順序?；蜴湕５牟煌煌??；静僮饔腥霔！⒊鰲！⒆x棧頂元素值、建棧、或判斷棧滿、?？盏?。3.存儲結構4.運算規(guī)則5.實現(xiàn)方式

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

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

an

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

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

（注意要遵循“后進先出”原則）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’

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

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

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

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

135426可以實現(xiàn)。例2：如果一個棧的輸入序列為123456，能否得到435612和135426的出棧序列？答：答：例1：一個棧的輸入序列是12345，若在入棧的過程中允許出棧例3（嚴題集3.1）一個棧的輸入序列為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；合計有5種可能性。例3（嚴題集3.1）一個棧的輸入序列為123，若在入棧的過程補充1：若入棧動作使地址向高端增長，稱為“向上生成”的棧；若入棧動作使地址向低端增長，稱為“向下生成”的棧；

對于向上生成的棧入棧口訣：堆棧指針top先壓后加（v[top++]=x）；出棧口訣：堆棧指針top先減后彈（y=v[--top])

。3.1棧補充2：

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

棧為空的條件：base=top;

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

鏈棧示意圖s(棧底)(棧頂)topa3a2a4a1^補充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ù)變化較大，且存在多個棧的情況下，鏈棧是棧的首選存儲方式。說明①鏈棧不必設頭結點，因為棧頂（表頭）操作頻繁；說明問：為什么要設計堆棧？它有什么獨特用途？調用函數(shù)或子程序非它莫屬；遞歸運算的有力工具；用于保護現(xiàn)場和恢復現(xiàn)場；簡化了程序設計的問題。答：問：為什么要設計堆棧？它有什么獨特用途？調用函數(shù)或子程序非它

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

設計思路：用棧暫存低位值例2：括號匹配的檢驗————P49

設計思路：用棧暫存左括號例3

：表達式求值—————P52

設計思路：用棧暫存運算符例4：漢諾儀（Hanoi）塔——P55

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

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

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

a.

從左算到右

b.

先乘除，后加減

c.

先括號內，后括號外由此，此表達式的計算順序為：

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

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

（是提供給計算機用的表！）由表可看出，右括號)

和井號

#

作為2時級別最低；

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

if棧頂元素>操作符，則退棧、計算，結果壓入OPND棧；棧頂元素=操作符且不為‘#’，脫括號（彈出左括號）；棧頂元素<操作符，壓入OPTR棧。棧的應用（表達式求值）（3）算法思想：棧的應用（表達式求值）棧的應用（表達式求值）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)棧的應用（表達式求值）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隊列與同線性表相同，仍為一對一關系。順序隊或鏈隊，以循環(huán)順序隊更常見。只能在隊首和隊尾運算，且訪問結點時依照先進先出（FIFO）的原則。關鍵是掌握入隊和出隊操作，具體實現(xiàn)依順序隊或鏈隊的不同而不同?；静僮饔腥腙牷虺鲫?，建空隊列，判隊空或隊滿等操作。3.存儲結構4.運算規(guī)則5.實現(xiàn)方式

2.邏輯結構只能在表的一端進行插入運算，在表的另一端進行刪除運算的線性表（頭刪尾插）定義3.2隊列與同線性表相同，仍為一對一關系。隊列（Queue）是僅在表尾進行插入操作，在表頭進行刪除操作的線性表。表尾即an端，稱為隊尾

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

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

p=(QuenePtr)malloc(sizeof(Qnode));if(!p)exit(OVERFLOW);p—>data=e;p—>next=NULL;Q.rear—>next=p;Q.rear=p;returnOK;}3)入隊4)出隊StatusDeQuene(LinkQuene&Q,QElemType&e){//若隊列不空，則刪除Q的隊頭元素，用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)出隊順序隊示意圖Q(隊尾)(隊首)fronta1a2a3dataa40.......99rear②隊列會滿嗎？很可能會，因為數(shù)組前端空間無法釋放。因此數(shù)組應當有長度限制。①空隊列的特征？約定：front=rear隊尾后地址入隊(尾部插入)：v[rear]=e;rear++;出隊(頭部刪除)：x=v[front];front++;討論：假溢出

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

J2

J3

J1

J4

J5frontrear

選用空閑單元法：即front和rear之一指向實元素，另一指向空閑元素。

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

問2：左圖中隊列長度L=？問1：左圖中隊列容量

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

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

J5J7J8

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

J3

J1

J4

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