2.1-第三章 棧和隊(duì)列ppt課件

1、進(jìn)棧示例進(jìn)棧示例 出棧示例出棧示例 例例: 假定有假定有4個(gè)元素個(gè)元素A，B，C，D，按所列次序進(jìn)棧，試寫出所有可按所列次序進(jìn)棧，試寫出所有可能的出棧序列。注意，每一個(gè)元能的出棧序列。注意，每一個(gè)元素進(jìn)棧后都允許出棧，如素進(jìn)棧后都允許出棧，如ACDB就是一種出棧序列。就是一種出棧序列。 解：可能的出棧序列有解：可能的出棧序列有ABCD，ABDC，ACBD，ACDB，ADCB，BACD，BADC，BCAD，BCDA，BDCA，CBAD，CBDA，CDBA，DCBA。棧的基本操作棧的基本操作1、初始化、初始化2、進(jìn)棧、進(jìn)棧PUSH3、出棧、出棧POP4、取棧頂元素、取棧頂元素GetTop5、判棧是

2、否非空、判棧是否非空3.2 棧的存儲結(jié)構(gòu)棧的存儲結(jié)構(gòu)順序存儲順序存儲-順序棧順序棧鏈?zhǔn)酱鎯︽準(zhǔn)酱鎯?鏈棧鏈棧 template class SeqStack T dataMaxSize; /存放棧元存放棧元素素 int top; /棧頂指針棧頂指針 public: SeqStack( ) ; /構(gòu)造函數(shù)構(gòu)造函數(shù) void Push(T x); /入棧入棧 T Pop( ); /出棧出棧 T Top( ); /取棧頂元素取棧頂元素 bool Empty( ); /判斷棧是判斷棧是否為空否為空 ; template class LinkStack Node *top; /棧頂指針 public:

3、LinkStack( ); /構(gòu)造函數(shù) LinkStack( ); /析構(gòu)函數(shù) void Push(T x); /入棧 T Pop( ); /出棧 T Top( ); /取棧頂元素 bool Empty( ); /判斷鏈棧是否為空棧 ;3.3 棧的操作算法棧的操作算法 1. 順序棧的操作算法順序棧的操作算法 2. 鏈?zhǔn)綏５牟僮魉惴ㄦ準(zhǔn)綏５牟僮魉惴? 順序棧的操作算法順序棧的操作算法 順序棧的初始化順序棧的初始化 template SeqStack:SeqStack( ) top=-1; (2) 順序棧的入棧操作順序棧的入棧操作 template void SeqStack:Push(T x)

4、if (top= MaxSize-1) cerr上溢; exit(1); top+; datatop=x; (3) 順序棧的出棧操作 template T SeqStack:Pop( ) if (top=-1) cerr下溢下溢; exit(1); x=datatop; top-; return x; (4) 取棧頂元素操作取棧頂元素操作 template T SeqStack:Top( ) if (top=-1) cerr下溢; exit(1);return datatop; (5) 判斷順序棧是否為空判斷順序棧是否為空 template bool SeqStack:Empty( ) ret

5、urn top=-1; 2 鏈棧的操作算法鏈棧的操作算法 (6) 鏈棧初始化 template LinkStack:LinkStack( ) top=NULL; 鏈棧入棧操作鏈棧入棧操作 template void LinkStack:Push( T x) s=new Node; s-data=x; s-next=top; top=s; (8) 鏈棧出棧操作鏈棧出棧操作template T LinkStack:Pop( ) if (top=NULL) cerrdata; p=top; top=top-next; delete p;return x;(9) 取棧頂元素操作取棧頂元素操作 temp

6、late T LinkStack:Top( ) if (top=NULL) cerrdata; (10) 判斷鏈棧是否為空判斷鏈棧是否為空 template bool LinkStack:Empty( ) return top=NULL; (11) (11) 鏈棧的析構(gòu)函數(shù)鏈棧的析構(gòu)函數(shù)template template LinkStack:LinkStack( )LinkStack:LinkStack( ) p=top;p=top;while (p)while (p) q=p;q=p;p=p-next;p=p-next;delete q;delete q; top=NULL;top=NULL

7、; 考慮：兩個(gè)棧共享同一段內(nèi)容空間，為了使得空考慮：兩個(gè)棧共享同一段內(nèi)容空間，為了使得空間利用率最高，應(yīng)如何分配棧空間？間利用率最高，應(yīng)如何分配棧空間？-兩個(gè)堆棧共享空間兩個(gè)堆棧共享空間0maxsize-1lefttoprighttop3.4 棧的應(yīng)用舉例棧的應(yīng)用舉例1. 棧的應(yīng)用之一棧的應(yīng)用之一: 遞歸調(diào)用遞歸調(diào)用例例: Hanoi塔問題塔問題. void Hanoi(int n, char a, char b, char c) if (n=1) Move (a, c); else Hanoi(n-1,a,c,b); Move(a,c); Hanoi(n-1,b,a,c); 一定要搞清執(zhí)行過

8、程一定要搞清執(zhí)行過程2. 棧的應(yīng)用之二棧的應(yīng)用之二: 算術(shù)表達(dá)式求值算術(shù)表達(dá)式求值 表達(dá)式求值是程序設(shè)計(jì)語言編譯中的一個(gè)最基本問題。它的實(shí)現(xiàn)需要借助棧來完成。這里介紹一種簡單直觀的算法，即“算符優(yōu)先法”。 輸入包含+、*、/、圓括號和正整數(shù)組成的中綴算術(shù)表達(dá)式，以“”作為表達(dá)式結(jié)束符。計(jì)算該表達(dá)式的運(yùn)算結(jié)果。 運(yùn)算優(yōu)先級運(yùn)算優(yōu)先級()(=當(dāng)前運(yùn)算符棧頂運(yùn)算符算法思想：算法思想： 為實(shí)現(xiàn)算符優(yōu)先算法，使用兩個(gè)工作為實(shí)現(xiàn)算符優(yōu)先算法，使用兩個(gè)工作棧。棧。 1.運(yùn)算符運(yùn)算符OPTR棧棧, 用以寄存運(yùn)算符用以寄存運(yùn)算符； 2.操作數(shù)操作數(shù)OPND棧棧, 用以寄存操作數(shù)用以寄存操作數(shù) 或運(yùn)或運(yùn)算結(jié)果。算

9、結(jié)果。 （1首先置操作數(shù)棧首先置操作數(shù)棧OPND為空棧，表為空棧，表達(dá)式起始符達(dá)式起始符“”“”為運(yùn)算符的棧底元素；為運(yùn)算符的棧底元素； （2從左到右掃描，依次讀入中綴表達(dá)從左到右掃描，依次讀入中綴表達(dá)式中的每個(gè)字符，依次讀入表達(dá)式中每個(gè)式中的每個(gè)字符，依次讀入表達(dá)式中每個(gè)字符字符, 若是操作數(shù)若是操作數(shù),則進(jìn)則進(jìn)OPND棧，若是運(yùn)棧，若是運(yùn)算符，則與算符，則與OPTR棧的棧頂運(yùn)算符進(jìn)行比棧的棧頂運(yùn)算符進(jìn)行比較，作相應(yīng)操作，直至整個(gè)表達(dá)式求值完較，作相應(yīng)操作，直至整個(gè)表達(dá)式求值完畢即畢即OPTR棧的棧頂元素和當(dāng)前讀入的棧的棧頂元素和當(dāng)前讀入的字符均為字符均為“”“”）。）。 若讀到的是操作符若

10、讀到的是操作符c），則應(yīng)與操作符），則應(yīng)與操作符棧的棧頂元素棧的棧頂元素pre_op進(jìn)行比較，會進(jìn)行比較，會出現(xiàn)以下三種情況：出現(xiàn)以下三種情況： 若若pre_opc，則，則pre_op出棧，并在出棧，并在操作數(shù)棧中退棧操作數(shù)棧中退棧2次，依次得到操作數(shù)次，依次得到操作數(shù)b和和a，然后進(jìn)行，然后進(jìn)行a pre_op b運(yùn)算，并將運(yùn)算，并將運(yùn)算的結(jié)果壓入操作數(shù)棧中。運(yùn)算的結(jié)果壓入操作數(shù)棧中。 (舉例舉例)double Expression_Eval() SeqStack OPTR; / 運(yùn)算符棧運(yùn)算符棧SeqStack OPND; / 運(yùn)算數(shù)棧運(yùn)算數(shù)棧OPTR.Push();ch=getchar(

11、); while (ch!= | OPTR.Top( )!=) if (!InOPTR(ch,OP) OPND.Push(ch); ch=getchar( ); /讀到的是操作數(shù)則入棧讀到的是操作數(shù)則入棧else /讀到的是操作符讀到的是操作符 pre_op=OPTR.Top( ); switch (Precede(pre_op,ch) case : /情況情況b=OPND.Pop( ); a=OPND.Pop( ); pre_op=OPTR.Pop( );OPND.Push(Operate(a, pre_op, b); break; return OPND.Top( ); 后綴表達(dá)式求值后綴

12、表達(dá)式求值 中綴表達(dá)式中綴表達(dá)式后綴表達(dá)式后綴表達(dá)式求值求值 將中綴表達(dá)式變成等價(jià)的后綴表達(dá)式時(shí)，將中綴表達(dá)式變成等價(jià)的后綴表達(dá)式時(shí)，表達(dá)式中操作數(shù)次序不變，而操作符次表達(dá)式中操作數(shù)次序不變，而操作符次序會發(fā)生變化，同時(shí)去掉圓括號。因此序會發(fā)生變化，同時(shí)去掉圓括號。因此設(shè)置一個(gè)棧設(shè)置一個(gè)棧OPTR用以存放操作符。用以存放操作符。 中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式的基本思路中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式的基本思路: 從左到右掃描中綴表達(dá)式，依次讀入表達(dá)從左到右掃描中綴表達(dá)式，依次讀入表達(dá)式中的每個(gè)字符，對于不同類型的字符按不式中的每個(gè)字符，對于不同類型的字符按不情況進(jìn)行處理。情況進(jìn)行處理。 若讀到的是操作

13、數(shù)，則輸出該操作數(shù)，并若讀到的是操作數(shù)，則輸出該操作數(shù)，并讀入下一個(gè)字符。讀入下一個(gè)字符。 若讀到的是左括號，則把它壓入到若讀到的是左括號，則把它壓入到OPTR棧中，并讀入下一個(gè)字符。棧中，并讀入下一個(gè)字符。 若讀到的是右括號，則表明括號內(nèi)的中綴若讀到的是右括號，則表明括號內(nèi)的中綴表達(dá)式已經(jīng)掃描完畢，將表達(dá)式已經(jīng)掃描完畢，將OPTR棧從棧頂頂棧從棧頂頂直到左括號之前的操作符依次出棧并輸出，直到左括號之前的操作符依次出棧并輸出，然后將左括號也出棧，并讀入下一個(gè)字符。然后將左括號也出棧，并讀入下一個(gè)字符。 若讀到的是操作符若讀到的是操作符c），則應(yīng)與操作符），則應(yīng)與操作符棧的棧頂元素棧的棧頂元素p

14、re_op進(jìn)行比較：進(jìn)行比較： 若若cpre_op，則將，則將c入棧，并讀下一個(gè)字符入棧，并讀下一個(gè)字符; 若若c= pre_op，則將，則將pre_op出棧并輸出。出棧并輸出。 按照以上過程掃描到中綴表達(dá)式結(jié)束符時(shí)，按照以上過程掃描到中綴表達(dá)式結(jié)束符時(shí)，把棧中剩余的操作符依次出棧并輸出，就得把棧中剩余的操作符依次出棧并輸出，就得到了轉(zhuǎn)換后的后綴表達(dá)式。到了轉(zhuǎn)換后的后綴表達(dá)式。 書中例子書中例子: 后綴表達(dá)式求值時(shí)，不需要再考慮操作后綴表達(dá)式求值時(shí)，不需要再考慮操作符的優(yōu)先級，只需從左到右掃描一遍后符的優(yōu)先級，只需從左到右掃描一遍后綴表達(dá)式即可?？稍O(shè)置一個(gè)棧綴表達(dá)式即可。可設(shè)置一個(gè)棧OPND用

15、用以存放操作數(shù)。以存放操作數(shù)。 后綴表達(dá)式求值算法的基本思路：后綴表達(dá)式求值算法的基本思路： 從左到右掃描，依次讀入表達(dá)式中的每從左到右掃描，依次讀入表達(dá)式中的每個(gè)字符，直至表達(dá)式結(jié)束。個(gè)字符，直至表達(dá)式結(jié)束。 若讀到的是操作數(shù)，則入棧OPND。 若讀到的是操作符，則在OPND棧中退出2個(gè)元素先退出的在操作符右，后退出的在操作符左），然后用該操作符進(jìn)行運(yùn)算，并將運(yùn)算結(jié)果壓入OPND棧中。 后綴表達(dá)式掃描完畢時(shí)，OPND棧中僅有一個(gè)元素，即為運(yùn)算的結(jié)果。 書中例子:隊(duì)列的基本操作隊(duì)列的基本操作1、構(gòu)造一個(gè)隊(duì)列、構(gòu)造一個(gè)隊(duì)列2、進(jìn)隊(duì)操作、進(jìn)隊(duì)操作-將新元素插入隊(duì)將新元素插入隊(duì)尾尾3、出隊(duì)操作、出隊(duì)

16、操作-隊(duì)列頭元素出隊(duì)列頭元素出隊(duì)隊(duì)4、取隊(duì)列頭元素、取隊(duì)列頭元素5、判定隊(duì)列是否為空、判定隊(duì)列是否為空3.6 隊(duì)列的存儲結(jié)構(gòu) 順序存儲順序存儲-循環(huán)隊(duì)列循環(huán)隊(duì)列 鏈?zhǔn)酱鎯︽準(zhǔn)酱鎯?鏈隊(duì)鏈隊(duì) 考慮考慮: 為什么要構(gòu)造循環(huán)隊(duì)列為什么要構(gòu)造循環(huán)隊(duì)列? template class SeqQueue T data MaxSize; /存放隊(duì)列元存放隊(duì)列元素素 int front, rear; /隊(duì)頭和隊(duì)尾隊(duì)頭和隊(duì)尾指針指針 public: SeqQueue( ); /構(gòu)造函數(shù)，置構(gòu)造函數(shù)，置空隊(duì)空隊(duì) void EnQueue(T x); /將元素將元素x入隊(duì)入隊(duì) T DeQueue( ); /將隊(duì)頭元

17、素出將隊(duì)頭元素出隊(duì)隊(duì) T GetQueue( ); /取隊(duì)頭元素取隊(duì)頭元素 bool Empty( ); /判斷隊(duì)列是否判斷隊(duì)列是否為空為空 ;n 進(jìn)隊(duì)時(shí)隊(duì)尾指針進(jìn)隊(duì)時(shí)隊(duì)尾指針 rear = rear + 1，將新元素，將新元素按按 rear 指示位置加入。指示位置加入。n 出隊(duì)時(shí)隊(duì)頭指針出隊(duì)時(shí)隊(duì)頭指針 front = front + 1，再將下，再將下標(biāo)為標(biāo)為 front 的元素取出。的元素取出。n 考慮：上圖中，元素再進(jìn)隊(duì)，將如何？考慮：上圖中，元素再進(jìn)隊(duì)，將如何？呈現(xiàn)呈現(xiàn)“假上溢假上溢現(xiàn)象現(xiàn)象 解決辦法解決辦法: 將存儲數(shù)據(jù)元素的一維數(shù)組看成是頭尾將存儲數(shù)據(jù)元素的一維數(shù)組看成是頭尾相接的

18、循環(huán)結(jié)構(gòu)相接的循環(huán)結(jié)構(gòu) 即循環(huán)隊(duì)列即循環(huán)隊(duì)列 循環(huán)隊(duì)列的隊(duì)空隊(duì)滿問題循環(huán)隊(duì)列的隊(duì)空隊(duì)滿問題為了方便起見，約定：為了方便起見，約定：初始化建空隊(duì)時(shí)，令初始化建空隊(duì)時(shí)，令front=rear=0, 當(dāng)隊(duì)空時(shí)：當(dāng)隊(duì)空時(shí)：front=rear 當(dāng)隊(duì)滿時(shí)：當(dāng)隊(duì)滿時(shí)：front=rear 亦成立亦成立 因而，只憑等式因而，只憑等式front=rear 無法判斷隊(duì)空還是隊(duì)滿。無法判斷隊(duì)空還是隊(duì)滿。 有三種方法處理上述問題：有三種方法處理上述問題： 浪費(fèi)一個(gè)單元。當(dāng)使用MaxSize-1個(gè)單元時(shí)即認(rèn)為是隊(duì)滿, 此時(shí) (rear+1) % MaxSize=front 設(shè)置一個(gè)布爾變量flag。當(dāng)flag=fla

19、se時(shí)為空，當(dāng)flag=true時(shí)為滿。 使用一個(gè)計(jì)數(shù)器記錄隊(duì)列中元素的個(gè)數(shù)。如num，當(dāng)num=0時(shí)隊(duì)空， 當(dāng)num=MaxSize時(shí)隊(duì)滿。2隊(duì)列的鏈?zhǔn)酱鎯Y(jié)構(gòu)隊(duì)列的鏈?zhǔn)酱鎯Y(jié)構(gòu) template class LinkQueue private: Node *front, *rear; public: LinkQueue( ); /構(gòu)造函數(shù)構(gòu)造函數(shù) LinkQueue( ); /析構(gòu)函數(shù)析構(gòu)函數(shù) void EnQueue(T x); /將元素將元素x入隊(duì)入隊(duì) T DeQueue( ); /將隊(duì)頭元素出隊(duì)將隊(duì)頭元素出隊(duì) T GetQueue( ); /取鏈隊(duì)列的隊(duì)頭元素取鏈隊(duì)列的隊(duì)頭元素 bo

20、ol Empty( ); /判斷鏈隊(duì)列是否為空判斷鏈隊(duì)列是否為空 ;3.7 隊(duì)列的操作算法 1循環(huán)隊(duì)列的操作循環(huán)隊(duì)列的操作 2鏈隊(duì)列的操作鏈隊(duì)列的操作1循環(huán)隊(duì)列的操作循環(huán)隊(duì)列的操作（1循環(huán)隊(duì)列的初始化循環(huán)隊(duì)列的初始化template SeqQueue: SeqQueue () front=rear=0; （2循環(huán)隊(duì)列的入隊(duì)操作循環(huán)隊(duì)列的入隊(duì)操作 template void SeqQueue: EnQueue(T x) if (rear+1) % MaxSize =front) cerr上溢上溢; exit(1);rear=(rear+1) % MaxSize; datarear=x; 隊(duì)尾處插

21、入元素隊(duì)尾處插入元素 （3循環(huán)隊(duì)列的出隊(duì)操作循環(huán)隊(duì)列的出隊(duì)操作 template T SeqQueue:DeQueue( ) if (rear=front) cerr下溢下溢; exit(1);front=(front+1) % MaxSize; return datafront; （4判斷循環(huán)隊(duì)列是否為空判斷循環(huán)隊(duì)列是否為空 template bool SeqQueue:Empty( ) return rear=front; 2鏈隊(duì)列的操作鏈隊(duì)列的操作 (1) 鏈隊(duì)列的初始化鏈隊(duì)列的初始化 template LinkQueue:LinkQueue( )s=new Node;s-next=NU

22、LL;front=rear=s;（2鏈隊(duì)列入隊(duì)操作鏈隊(duì)列入隊(duì)操作 template void LinkQueue:EnQueue(T x) s=new Node; s-data=x;s-next=NULL;rear-next=s; /將結(jié)點(diǎn)將結(jié)點(diǎn)s插入到隊(duì)插入到隊(duì)尾尾rear=s; /將隊(duì)尾指針指向結(jié)點(diǎn)將隊(duì)尾指針指向結(jié)點(diǎn)s (3) 鏈隊(duì)列的出隊(duì)操作 template T LinkQueue:DeQueue() if (rear=front) cerrnext; x=p-data; front-next=p-next; if (p-next=NULL) rear=front; delete p;return x; （1問題描述問題描述 設(shè)有設(shè)有n個(gè)人排成一列，從前往后個(gè)人排成一列，從前往后“0，1連續(xù)報(bào)數(shù)。凡是報(bào)到連續(xù)報(bào)數(shù)。凡是報(bào)到“0的人出列，凡的人出列，凡是報(bào)到是報(bào)到“1的人立即站到隊(duì)伍的最后。的人立即站到隊(duì)伍的最后。反復(fù)進(jìn)行報(bào)數(shù)，直到所有人均出列