第3章棧和隊列

1、第第3章章 棧和隊列棧和隊列3.1 棧棧3.2 棧的應(yīng)用舉例棧的應(yīng)用舉例3.3 棧與遞歸的實現(xiàn)棧與遞歸的實現(xiàn)3.4 隊列隊列3.1 棧棧3.1.1 抽象數(shù)據(jù)類型棧的定義抽象數(shù)據(jù)類型棧的定義 棧的定義棧的定義l棧棧(stack)，又稱堆棧，是限制線性表中元素的插入和刪除只，又稱堆棧，是限制線性表中元素的插入和刪除只能在線性表的同一端進(jìn)行的一種特殊線性表。允許插入和刪能在線性表的同一端進(jìn)行的一種特殊線性表。允許插入和刪除的一端，為變化的一端，稱為除的一端，為變化的一端，稱為棧頂棧頂(Top)，另一端為固定，另一端為固定的一端，稱為的一端，稱為棧底棧底(Bottom)。l根據(jù)棧的定義可知，最先根據(jù)棧

2、的定義可知，最先放入棧中元素在棧底，最放入棧中元素在棧底，最后放入的元素在棧頂，而后放入的元素在棧頂，而刪除元素剛好相反，最后刪除元素剛好相反，最后放入的元素最先刪除，最放入的元素最先刪除，最先放入的元素最后刪除。先放入的元素最后刪除。l也就是說，棧是一種后進(jìn)也就是說，棧是一種后進(jìn)先出先出(Last In First Out)的線性表，簡稱為的線性表，簡稱為LIFO表。表。l棧的插入操作被形象地稱棧的插入操作被形象地稱為為進(jìn)棧進(jìn)?；蛉霔?，刪除操作或入棧，刪除操作稱為稱為出棧出?；蚧蛲藯Ｍ藯?。例：例：l入棧順序：入棧順序：123l可能出棧順序：可能出棧順序：123，132，213，231，321

3、l不可能出棧順序：不可能出棧順序：312 棧的抽象數(shù)據(jù)類型棧的抽象數(shù)據(jù)類型lADT Stack lData：含有：含有n個元素個元素a1,a2,a3,an，按，按LIFO規(guī)則存放，每個元素的類型規(guī)則存放，每個元素的類型都為都為ElemType。lOperation:l /初始化棧初始化棧svoid initStack(Stack& s); l/清除棧清除棧s的所有元素，使之成為空棧的所有元素，使之成為空棧void clearStack(Stack& s); l /判斷棧判斷棧s是否為空，若是則返回是否為空，若是則返回true，否則返回，否則返回falsebool isEmpty(Stack&

4、s);l /若棧已滿則返回若棧已滿則返回true，否則返回，否則返回false，此操作為順序棧所特有，此操作為順序棧所特有bool isFull(Stack& s);l/返回棧頂元素，但不移動棧頂指針返回棧頂元素，但不移動棧頂指針ElemType peek(Stack& s); l/元素元素e進(jìn)棧，即插入到棧頂進(jìn)棧，即插入到棧頂void push(Stack& s,const ElemType& e); l/刪除棧頂元素并返回之刪除棧頂元素并返回之ElemType pop(Stack& s); lend Stack3.1.2 棧的表示和實現(xiàn)棧的表示和實現(xiàn)3.1.2.1 順序棧順序棧-棧的順序存

5、儲結(jié)構(gòu)棧的順序存儲結(jié)構(gòu)l和線性表類似，棧也有兩種存儲表示，其順和線性表類似，棧也有兩種存儲表示，其順序存儲結(jié)構(gòu)簡稱為序存儲結(jié)構(gòu)簡稱為。順序棧類型定義：順序棧類型定義：sqstack.hl#include lusing namespace std;lconst int MAXSIZE=50;lstruct Elemlint data;l;ltypedef Elem ElemType;lstruct lElemType baseMAXSIZE;lint top;l;lvoid initStack(SqStack& s);lvoid clearStack(SqStack& s);lbool isEm

6、pty(SqStack& s);lbool isFull(SqStack& s);lElemType peek(SqStack& s);lvoid push(SqStack& s,const ElemType& e);lElemType pop(SqStack& s);ls.base 始終指向棧底始終指向棧底ls.base=NULL 表示棧結(jié)構(gòu)不存在表示棧結(jié)構(gòu)不存在ls.top=0 表示?？毡硎緱？誰s.top 始終指向棧頂元素的下一個位置始終指向棧頂元素的下一個位置順序?；静僮鞯膶崿F(xiàn)：順序棧基本操作的實現(xiàn)：sqstack.cppl#include sqstack.hlvoid initSt

7、ack(SqStack& s)ls.top=0;llvoid clearStack(SqStack& s)ls.top=0;llbool isEmpty(SqStack& s)lreturn s.top=0;llbool isFull(SqStack& s)lreturn s.top=MAXSIZE;llElemType peek(SqStack& s)lif(s.top=0)lcerrStack is empty!endl;lexit(1);llreturn s.bases.top-1;llvoid push(SqStack& s,const ElemType& e)lif(s.top=MA

8、XSIZE)lcerrStack overflow!endl;lexit(1);lls.bases.top=e;l+s.top;llElemType pop(SqStack& s)lif(s.top=0)lcerrStack is empty!endl;lexit(1);ll-s.top;lElemType temp=s.bases.top;lreturn temp;l3.1.2.2 棧的鏈接存儲結(jié)構(gòu)棧的鏈接存儲結(jié)構(gòu)-鏈棧鏈棧 （Linked-stack）l棧的鏈?zhǔn)酱尜A結(jié)構(gòu)，也稱為鏈棧，它是一種限制運棧的鏈?zhǔn)酱尜A結(jié)構(gòu)，也稱為鏈棧，它是一種限制運算的鏈表，即規(guī)定鏈表中的插入和刪除運算只能在算的鏈

9、表，即規(guī)定鏈表中的插入和刪除運算只能在鏈表鏈表進(jìn)行。鏈棧結(jié)構(gòu)見下圖進(jìn)行。鏈棧結(jié)構(gòu)見下圖注： 只能在鏈表頭部進(jìn)行操作 表示同線性表 頭指針-棧頂指針鏈棧的結(jié)構(gòu)可用鏈棧的結(jié)構(gòu)可用C+語言定義如下：語言定義如下：lstruct LNodel ElemType data;l Lnode * next; l;lLNode* top;3.2 棧的應(yīng)用舉例棧的應(yīng)用舉例l由于棧的操作具有后進(jìn)先出的固有特性，致由于棧的操作具有后進(jìn)先出的固有特性，致使棧成為程序設(shè)計中的有用工具。凡應(yīng)用問使棧成為程序設(shè)計中的有用工具。凡應(yīng)用問題求解的過程具有題求解的過程具有后進(jìn)先出后進(jìn)先出的天然特性的的天然特性的話，則求解的算法中

10、也必然需要利用話，則求解的算法中也必然需要利用棧棧。3.2.1 數(shù)制轉(zhuǎn)換數(shù)制轉(zhuǎn)換l假設(shè)要將十進(jìn)制數(shù)假設(shè)要將十進(jìn)制數(shù)N轉(zhuǎn)換為轉(zhuǎn)換為d進(jìn)制數(shù)：（如進(jìn)制數(shù)：（如8進(jìn)制）進(jìn)制）轉(zhuǎn)換結(jié)果：2504 問題很明確，就是要輸出計算過程中所得到的各個八進(jìn)制數(shù)位。然而這八進(jìn)制的各個數(shù)位產(chǎn)生的順序是從低位到高位的，而打印輸出的順序，一般來說應(yīng)從高位到低位，這恰好和計算過程相反。因此，需要先保存在計算過程中得到的八進(jìn)制數(shù)的各位，然后逆序輸出，因為它是按后進(jìn)先出的規(guī)律進(jìn)行的，所以用棧最合適。ltypedef int ElemType;lvoid conversion(int n,int r)lSqStack s;lin

11、itStack(s);lwhile(n)lpush(s,n%r);ln=n/r;llwhile(!isEmpty(s)lcoutpop(s);lcoutendl;l3.2.2 括號匹配問題括號匹配問題l假設(shè)表達(dá)式中允許包含兩種括號：圓括號和假設(shè)表達(dá)式中允許包含兩種括號：圓括號和方括號，其嵌套的順序隨意，如方括號，其嵌套的順序隨意，如( ( ) )或或 ( ) 等為正確的匹配，等為正確的匹配， ( )或或( ( )或或 ( ( ) ) )均為錯誤的匹配。均為錯誤的匹配。l現(xiàn)在的問題是，要求檢驗一個給定表達(dá)式中現(xiàn)在的問題是，要求檢驗一個給定表達(dá)式中的括弧是否正確匹配？的括弧是否正確匹配？l檢驗括號

12、是否匹配的方法可用檢驗括號是否匹配的方法可用期待的急迫程期待的急迫程度度這個概念來描述。即后出現(xiàn)的這個概念來描述。即后出現(xiàn)的左括弧左括弧，它等待與其匹配的它等待與其匹配的右括弧右括弧出現(xiàn)的出現(xiàn)的急迫急迫心心情要比先出現(xiàn)的左括弧高。情要比先出現(xiàn)的左括弧高。l在檢驗算法中可設(shè)置一個棧，每讀入一個括號：在檢驗算法中可設(shè)置一個棧，每讀入一個括號：l若是左括號，則直接入棧，等待相匹配的同類右若是左括號，則直接入棧，等待相匹配的同類右括號；括號；l若讀入的是右括號，且與當(dāng)前棧頂?shù)淖罄ㄌ柾惾糇x入的是右括號，且與當(dāng)前棧頂?shù)淖罄ㄌ柾愋?，如二者匹配，則將棧頂?shù)淖罄ㄌ柍鰲?；否則屬型，如二者匹配，則將棧頂?shù)淖罄ㄌ?/p>

13、出棧；否則屬于不合法的情況；于不合法的情況；l如果輸入序列已讀盡，而棧中仍有等待匹配的左如果輸入序列已讀盡，而棧中仍有等待匹配的左括號，不合法；括號，不合法；l讀入了一個右括號，而棧中已無等待匹配的左括讀入了一個右括號，而棧中已無等待匹配的左括號，不合法。號，不合法。ltypedef char ElemType;lbool bracketsCheck(char* c)lSqStack s;linitStack(s);lfor(int i=0;ci!=0;+i)lswitch(ci)lcase :lcase (:lpush(s,ci);lbreak;lcase :lif(!isEmpty(s)&

14、peek(s)=)lpop(s);lelselreturn false;lbreak;lcase ):lif(!isEmpty(s)&peek(s)=()lpop(s);lelselreturn false;lbreak;l default:l break;lllif(isEmpty(s)lreturn true;lelselreturn false;l3.2.3 迷宮（迷宮（Maze）求解）求解l一個迷宮包含有一個迷宮包含有m行行n列個小方格，每個方格用列個小方格，每個方格用1表示可通行，用表示可通行，用0表示墻壁，即不可通行，迷宮中通表示墻壁，即不可通行，迷宮中通常有一個入口和一個出口。求

15、解迷宮問題是從入口常有一個入口和一個出口。求解迷宮問題是從入口點出發(fā)尋找一條通向出口點的路徑，并輸出這條路點出發(fā)尋找一條通向出口點的路徑，并輸出這條路徑。徑。12345110010211101301011411010501110l計算機(jī)解迷宮問題時，通常用的是計算機(jī)解迷宮問題時，通常用的是窮舉求解窮舉求解法：法： 從入口出發(fā)，順某一方向向前搜索，若能走通，從入口出發(fā)，順某一方向向前搜索，若能走通，則繼續(xù)往前走，否則則繼續(xù)往前走，否則，換一個方向再，換一個方向再繼續(xù)搜索，直至所有可能的通路都探索到為止。繼續(xù)搜索，直至所有可能的通路都探索到為止。l在一個迷宮中，中間的每個方格位置都有四個可選擇的移

16、動在一個迷宮中，中間的每個方格位置都有四個可選擇的移動方向，而在四個頂點只有兩個方向，并且每個頂點的兩個方方向，而在四個頂點只有兩個方向，并且每個頂點的兩個方向均有差別，每條邊線上除頂點外的每個位置只有三個方向，向均有差別，每條邊線上除頂點外的每個位置只有三個方向，并且也有差別。并且也有差別。，如圖（，如圖（b）所示。）所示。012345600000000101001002011101030010110401101005001110060000000l當(dāng)從迷宮中的一個位置（稱之為當(dāng)前位置）當(dāng)從迷宮中的一個位置（稱之為當(dāng)前位置）前進(jìn)到下一個位置時，下一個位置相對于當(dāng)前進(jìn)到下一個位置時，下一個位置

17、相對于當(dāng)前位置的位移量（包括行位移量和列位移量）前位置的位移量（包括行位移量和列位移量）隨著前進(jìn)的方向的不同而不同，東、南、西、隨著前進(jìn)的方向的不同而不同，東、南、西、北（即右、下、左、上）各方向的位移量依北（即右、下、左、上）各方向的位移量依次為（次為（0,1）、（）、（1,0）、（）、（0,-1）和（）和（-1,0）。）。l為了尋找從入口點到出口點的一條通路，首先從入為了尋找從入口點到出口點的一條通路，首先從入口點出發(fā)，按照口點出發(fā)，按照東南西北東南西北各方向的次序試探前進(jìn)，各方向的次序試探前進(jìn)，若向東可通行，若向東可通行，則向東前進(jìn)一，則向東前進(jìn)一個方格；否則表明向東沒有通向出口的路徑，

18、接著個方格；否則表明向東沒有通向出口的路徑，接著向南方向試著前進(jìn)，若向南可通行同時沒有被訪問向南方向試著前進(jìn)，若向南可通行同時沒有被訪問過，應(yīng)向南前進(jìn)一步；否則依次向西和向北試探。過，應(yīng)向南前進(jìn)一步；否則依次向西和向北試探。若試探完當(dāng)前位置上的所有方向后都沒有通路，則若試探完當(dāng)前位置上的所有方向后都沒有通路，則應(yīng)退回一步，從到達(dá)當(dāng)前位置的下一個方向試探著應(yīng)退回一步，從到達(dá)當(dāng)前位置的下一個方向試探著前進(jìn)。因此每前進(jìn)一步都前進(jìn)。因此每前進(jìn)一步都要記錄其上一步的坐標(biāo)位要記錄其上一步的坐標(biāo)位置以及前進(jìn)到此步的方向置以及前進(jìn)到此步的方向，以便退回之用。這正好，以便退回之用。這正好需要用棧來解決。需要用棧

19、來解決。l算法見教材算法見教材P51。sqstack.hl#include lusing namespace std;lconst int MAXSIZE=100;lstruct PosType / 迷宮坐標(biāo)位置類型迷宮坐標(biāo)位置類型l lint x; / 行值行值lint y; / 列值列值l;struct Elem / 棧的元素類型棧的元素類型 int ord; / 通道塊在路徑上的序號通道塊在路徑上的序號PosType seat; / 通道塊在迷宮中的坐標(biāo)位置通道塊在迷宮中的坐標(biāo)位置int di; / 從此通道塊走向下一通道塊的方向從此通道塊走向下一通道塊的方向(03表表示東北示東北);t

20、ypedef Elem ElemType;struct SqStackElemType baseMAXSIZE;int top;sqstack.cpplvoid initStack(SqStack& s);lvoid clearStack(SqStack& s);lbool isEmpty(SqStack& s);lbool isFull(SqStack& s);lElemType peek(SqStack& s);lvoid push(SqStack& s,const ElemType& e);lElemType pop(SqStack& s);同前main.cppl#include l#i

21、nclude l#include sqstack.h lconst int MAXLENGTH=25; / 設(shè)迷宮的最大行列為設(shè)迷宮的最大行列為25ltypedef int MAXLENGTHMAXLENGTH; / 迷宮數(shù)組迷宮數(shù)組行行列列l(wèi)MazeType m; / 迷宮數(shù)組迷宮數(shù)組lint curstep=1; / 當(dāng)前足跡當(dāng)前足跡,初值為初值為1l l/ 定義墻元素值為定義墻元素值為0,可通過路徑為可通過路徑為1,不能通過路徑為不能通過路徑為-1,通過路徑為足跡通過路徑為足跡lbool pass(PosType b)l / 當(dāng)迷宮當(dāng)迷宮m的的b點的序號為點的序號為1(可通過路徑可通過路

22、徑)，返回，返回 truel /否則，返回否則，返回false lif(mb.xb.y=1)lreturn true;lelselreturn false;llvoid footPrint(PosType a)l / 使迷宮使迷宮m的的a點的序號變?yōu)樽阚E點的序號變?yōu)樽阚E(curstep)lma.xa.y=curstep;ll / 根據(jù)當(dāng)前位置及移動方向，返回下一位置根據(jù)當(dāng)前位置及移動方向，返回下一位置lPosType nextPos(PosType c,int di)llPosType direc4=0,1,1,0,0,-1,-1,0; l / 行增量行增量,列增量列增量l/ 移動方向移動方向

23、,依次為東南西北依次為東南西北lc.x+=direcdi.x;lc.y+=direcdi.y;lreturn c;ll/ 使迷宮使迷宮m的的b點的序號變?yōu)辄c的序號變?yōu)?1(不能通過的路徑不能通過的路徑)lvoid markPrint(PosType b)l lmb.xb.y=-1;llbool mazePath(PosType start,PosType end)l l/若迷宮若迷宮maze中存在從入口中存在從入口start到出口到出口end的通的通道，則求得一條存放在棧中道，則求得一條存放在棧中(從棧底到棧頂從棧底到棧頂)，并返，并返回回true；否則返回；否則返回falselSqStack

24、 s;lPosType curpos;lElemType e;linitStack(s);lcurpos=start;doif(pass(curpos) / 當(dāng)前位置可以通過，即是未曾走到過的通道塊當(dāng)前位置可以通過，即是未曾走到過的通道塊 footPrint(curpos); / 留下足跡留下足跡push(s,e); / 入棧當(dāng)前位置及狀態(tài)入棧當(dāng)前位置及狀態(tài)curstep+; / 足跡加足跡加1if(curpos.x=end.x&curpos.y=end.y) / 到達(dá)終點到達(dá)終點 return true;curpos=nextPos(curpos,e.di); /向前走一步向前走一步else

25、 / 當(dāng)前位置不能通過當(dāng)前位置不能通過 if(!isEmpty(s)e=pop(s); / 退棧到前一位置退棧到前一位置curstep-;while(e.di=3&!isEmpty(s) / 前一位置處于最后一個方向前一位置處于最后一個方向 markPrint(e.seat); / 留下不能通過的標(biāo)記留下不能通過的標(biāo)記(-1)e=pop(s); / 退回一步退回一步curstep-;if(e.di3) / 沒到最后一個方向沒到最后一個方向(北北)e.di+; / 換下一個方向探索換下一個方向探索push(s,e);curstep+;curpos=nextPos(e.seat,e.di); wh

26、ile(!isEmpty(s);return false;void print(int x,int y) / 輸出迷宮的解輸出迷宮的解 for(int i=0;ix;i+)for(int j=0;jy;j+)coutsetw(3)mij;coutendl;int main()PosType begin,end;begin.x=1;begin.y=1;end.x=6;end.y=8;ifstream infile;infile.open(data.txt); /打開文件打開文件for(int i=0;i8;i+)for(int j=0;jmij;infile.close(); /關(guān)閉文件關(guān)閉文件

27、cout迷宮結(jié)構(gòu)如下迷宮結(jié)構(gòu)如下:n;printM(m); if(mazePath(begin,end) / 求得一條通路求得一條通路 cout此迷宮從入口到出口的一條路徑如下此迷宮從入口到出口的一條路徑如下:n;printM(m); / 輸出此通路輸出此通路elsecout此迷宮沒有從入口到出口的路徑此迷宮沒有從入口到出口的路徑n;3.2.4 表達(dá)式求值表達(dá)式求值l程序設(shè)計語言中都有計算表達(dá)式的問題，這程序設(shè)計語言中都有計算表達(dá)式的問題，這是語言編譯中的典型問題，是棧的典型應(yīng)用是語言編譯中的典型問題，是棧的典型應(yīng)用實例。實例。3.2.4.1 算術(shù)表達(dá)式的兩種表示算術(shù)表達(dá)式的兩種表示l通常書寫

28、的算術(shù)表達(dá)式是由操作數(shù)（又叫運通常書寫的算術(shù)表達(dá)式是由操作數(shù)（又叫運算對象或運算量）和運算符以及改變運算次算對象或運算量）和運算符以及改變運算次序的圓括號連接而成。如序的圓括號連接而成。如l16-9*(4+3)l這種算術(shù)表達(dá)式稱為這種算術(shù)表達(dá)式稱為。在中綴表。在中綴表達(dá)式的計算過程中，即要考慮括號的作用，達(dá)式的計算過程中，即要考慮括號的作用，又要考慮運算符的優(yōu)先級，還要考慮運算符又要考慮運算符的優(yōu)先級，還要考慮運算符出現(xiàn)的先后次序，用計算機(jī)來處理非常困難。出現(xiàn)的先后次序，用計算機(jī)來處理非常困難。l波蘭科學(xué)家謝維奇提出了算術(shù)表達(dá)式的另一種表示，波蘭科學(xué)家謝維奇提出了算術(shù)表達(dá)式的另一種表示，即后綴

29、表示，又稱逆波蘭式，其定義是把運算符放即后綴表示，又稱逆波蘭式，其定義是把運算符放在兩個運算對象的后面。采用后綴表示的算術(shù)表達(dá)在兩個運算對象的后面。采用后綴表示的算術(shù)表達(dá)式稱為式稱為后綴表達(dá)式后綴表達(dá)式。如。如l16 9 4 3 + * -l在后綴表達(dá)式中，不存在括號，也不存在優(yōu)先級的在后綴表達(dá)式中，不存在括號，也不存在優(yōu)先級的差別，計算過程完全差別，計算過程完全進(jìn)進(jìn)行，整個計算過程僅需一遍便可完成，顯然比中綴行，整個計算過程僅需一遍便可完成，顯然比中綴表達(dá)式的計算要簡單得多。表達(dá)式的計算要簡單得多。3.2.4.2 把中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式把中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式l設(shè)以設(shè)以字符作為結(jié)束

30、的中綴表達(dá)式保存在字符作為結(jié)束的中綴表達(dá)式保存在s1字符串中，轉(zhuǎn)換后得到的后綴表達(dá)式擬存于字符串中，轉(zhuǎn)換后得到的后綴表達(dá)式擬存于s2字符串中。字符串中。l由中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式的規(guī)則可知：由中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式的規(guī)則可知：轉(zhuǎn)換前后，轉(zhuǎn)換前后，表達(dá)式中的數(shù)值項的次序不變表達(dá)式中的數(shù)值項的次序不變，而而運算符的次序發(fā)生了變化運算符的次序發(fā)生了變化，由處在兩個運，由處在兩個運算對象的中間變?yōu)樘幵趦蓚€運算對象的后面，算對象的中間變?yōu)樘幵趦蓚€運算對象的后面，同時去掉了所有的括號。同時去掉了所有的括號。l為了使轉(zhuǎn)換正確，必須設(shè)定一個運算符棧，為了使轉(zhuǎn)換正確，必須設(shè)定一個運算符棧，并在棧底放入一

31、個特殊運算符，假定為并在棧底放入一個特殊運算符，假定為字字符，讓它具有最低的運算符優(yōu)先級，假定數(shù)符，讓它具有最低的運算符優(yōu)先級，假定數(shù)值為值為0。此棧用來保存掃描中中綴表達(dá)式得到。此棧用來保存掃描中中綴表達(dá)式得到的暫不能放入后綴表達(dá)式中的運算符，待它的暫不能放入后綴表達(dá)式中的運算符，待它的兩個運算符對象都放入到后綴表達(dá)式以后，的兩個運算符對象都放入到后綴表達(dá)式以后，再令其出棧并寫入到后綴表達(dá)式中。再令其出棧并寫入到后綴表達(dá)式中。算法的基本思路：算法的基本思路：l從頭到尾地掃描中綴表達(dá)式中的每個字符，不同的從頭到尾地掃描中綴表達(dá)式中的每個字符，不同的類型的字符按不同的情況處理。類型的字符按不同的

32、情況處理。若遇到的是空格，則認(rèn)為是分隔符，不需要進(jìn)行若遇到的是空格，則認(rèn)為是分隔符，不需要進(jìn)行處理；處理；若遇到的是數(shù)字或小數(shù)點，則直接寫入若遇到的是數(shù)字或小數(shù)點，則直接寫入s2中，并中，并在每個數(shù)值最后寫入一個空格；在每個數(shù)值最后寫入一個空格；若遇到的是左括號，則應(yīng)把它壓入到運算符棧中，若遇到的是左括號，則應(yīng)把它壓入到運算符棧中，待以它開始的括號內(nèi)的表達(dá)式轉(zhuǎn)換完畢后再出棧；待以它開始的括號內(nèi)的表達(dá)式轉(zhuǎn)換完畢后再出棧；若遇到的是右括號，則表明括號內(nèi)的中綴表達(dá)式若遇到的是右括號，則表明括號內(nèi)的中綴表達(dá)式已經(jīng)掃描完畢，把從棧頂直到保存著的對應(yīng)左括號已經(jīng)掃描完畢，把從棧頂直到保存著的對應(yīng)左括號之間的

33、運算符依次退棧并寫入之間的運算符依次退棧并寫入s2串中；串中；若遇到的是運算符：若遇到的是運算符： a. 當(dāng)該運算符的優(yōu)先級大于棧頂運算符的優(yōu)先級時，表明當(dāng)該運算符的優(yōu)先級大于棧頂運算符的優(yōu)先級時，表明該運算符的后一個運算對象還沒有被放入到該運算符的后一個運算對象還沒有被放入到s2串中，應(yīng)把它串中，應(yīng)把它暫存于運算棧中；暫存于運算棧中； b. 當(dāng)該運算符的優(yōu)先級小于棧頂運算符的優(yōu)先級時，表明當(dāng)該運算符的優(yōu)先級小于棧頂運算符的優(yōu)先級時，表明棧頂運算符的兩個運算對象已經(jīng)被保存到棧頂運算符的兩個運算對象已經(jīng)被保存到s2串中，應(yīng)將棧頂串中，應(yīng)將棧頂運算符退棧并寫入到運算符退棧并寫入到s2串中，對于新的

34、棧頂運算符仍繼續(xù)進(jìn)串中，對于新的棧頂運算符仍繼續(xù)進(jìn)行比較和處理，直到被處理的運算符的優(yōu)先級大于棧頂運算行比較和處理，直到被處理的運算符的優(yōu)先級大于棧頂運算符的優(yōu)先級為止，然后令該運算符進(jìn)棧即可。符的優(yōu)先級為止，然后令該運算符進(jìn)棧即可。l按照以上過程掃描到中綴表達(dá)式結(jié)束符按照以上過程掃描到中綴表達(dá)式結(jié)束符時，把棧中剩余時，把棧中剩余的運算符依次退棧并寫入到后綴表達(dá)式中，再向的運算符依次退棧并寫入到后綴表達(dá)式中，再向s2寫入表達(dá)寫入表達(dá)式結(jié)束符式結(jié)束符和字符串結(jié)束符和字符串結(jié)束符0，整個轉(zhuǎn)換過程就處理完畢，整個轉(zhuǎn)換過程就處理完畢，在在s2中就得到了轉(zhuǎn)換成的后綴表達(dá)式。中就得到了轉(zhuǎn)換成的后綴表達(dá)式。

35、change.cppl#include sqstack.hlint precede(char op)llswitch(op)l lcase +:lcase -:lreturn 1;lcase *:lcase /:lreturn 2;lcase (:lcase :ldefault:lreturn 0;llvoid change(char* s1,char* s2) /將字符串將字符串s1中的中綴表達(dá)式轉(zhuǎn)換為在于中的中綴表達(dá)式轉(zhuǎn)換為在于s2中的后綴表達(dá)式中的后綴表達(dá)式SqStack r;initStack(r); /初始化棧初始化棧push(r,); /給棧底放入給棧底放入字符，它具有最低優(yōu)先級字

36、符，它具有最低優(yōu)先級int i,j;i=0;j=0;char ch=s1i;while(ch!=)if(ch= )ch=s1+i;else if(ch=()push(r,ch);ch=s1+i;else if(ch=)while(peek(r)!=()s2j+=pop(r);pop(r);ch=s1+i;else if(ch=+|ch=-|ch=*|ch=/)char w=peek(r);while(precede(w)=precede(ch)s2j+=w;pop(r);w=peek(r);push(r,ch);ch=s1+i;elsewhile(isdigit(ch)|ch=.)s2j+=c

37、h;ch=s1+i;s2j+= ;ch=pop(r);while(ch!=)if(ch=()cerrexpression error!endl;exit(1);elses2j+=ch;ch=pop(r);s2j+=;s2j+=0;3.2.4.3 后綴表達(dá)式求值后綴表達(dá)式求值l后綴表達(dá)式的求值比較簡單，掃描一遍即可后綴表達(dá)式的求值比較簡單，掃描一遍即可完成。它需要使用一個棧，用以存儲后綴表完成。它需要使用一個棧，用以存儲后綴表達(dá)式中的操作數(shù)、計算的中間結(jié)果以及最后達(dá)式中的操作數(shù)、計算的中間結(jié)果以及最后結(jié)果。結(jié)果。l假定一個后綴表達(dá)式以字符假定一個后綴表達(dá)式以字符作為結(jié)束符，作為結(jié)束符，并且以字符

38、串方式提供。并且以字符串方式提供。后綴表達(dá)式求值算法的基本思路：后綴表達(dá)式求值算法的基本思路：l把包含后綴表達(dá)式的字符串定義為一個輸入字符把包含后綴表達(dá)式的字符串定義為一個輸入字符串流對象，每次從中讀入一個字符時，若它是串流對象，每次從中讀入一個字符時，若它是運算運算符符，則表明它的兩個操作數(shù)已經(jīng)在棧中，把它們彈，則表明它的兩個操作數(shù)已經(jīng)在棧中，把它們彈出后進(jìn)行運算即可，然后把運算結(jié)果再壓入棧中；出后進(jìn)行運算即可，然后把運算結(jié)果再壓入棧中；l否則，讀入的字符必為否則，讀入的字符必為操作數(shù)操作數(shù)的最高位數(shù)字，應(yīng)的最高位數(shù)字，應(yīng)把它重新送回輸入流中，然后把下一個數(shù)據(jù)作為浮把它重新送回輸入流中，然后

39、把下一個數(shù)據(jù)作為浮點數(shù)輸入，并把它壓入到棧中；點數(shù)輸入，并把它壓入到棧中；l依次掃描每一個字符并進(jìn)行上述處理，直到遇到依次掃描每一個字符并進(jìn)行上述處理，直到遇到結(jié)束符結(jié)束符為止，表明后綴表達(dá)式計算完畢，最終結(jié)為止，表明后綴表達(dá)式計算完畢，最終結(jié)果保存在棧中，并且棧中僅存一個值，把它彈出返果保存在棧中，并且棧中僅存一個值，把它彈出返回即可?；丶纯?。compute.cppl#include sqstack.hl#include ldouble compute(char* str)lSqStack s;linitStack(s);listringstream ins(str); l /把把str定義

40、為定義為string流對象流對象inslchar ch; /用于輸入字符用于輸入字符ldouble x; /用于輸入浮點數(shù)用于輸入浮點數(shù)linsch;lwhile(ch!=)lswitch(ch)lcase +:lx=pop(s)+pop(s);lbreak;lcase -:lx=pop(s); /pop(s)彈出減數(shù)彈出減數(shù)lx=pop(s)-x; /pop(s)彈出被減數(shù)彈出被減數(shù)lbreak;lcase *:lx=pop(s)*pop(s);lbreak;case /:x=pop(s);if(x!=0.0)x=pop(s)/x;cerrDivide by 0!x; /從字符串輸入流中讀入

41、一個浮點數(shù)從字符串輸入流中讀入一個浮點數(shù)push(s,x); /把讀入的數(shù)或進(jìn)行相應(yīng)運算的結(jié)果壓入到把讀入的數(shù)或進(jìn)行相應(yīng)運算的結(jié)果壓入到s棧中棧中insch;if(!isEmpty(s)x=pop(s);if(isEmpty(s)return x;elsecerrexpression error!endl;exit(1);elsecerrStack is emppty!endl;exit(1);棧定義如下：棧定義如下：sqstack.hl#include lusing namespace std;lconst int MAXSIZE=100;ltemplate lstruct SqStackl

42、ElemType baseMAXSIZE;lint top;l;ltemplate lvoid initStack(SqStack& s)ls.top=0;lltemplate lvoid clearStack(SqStack& s)ls.top=0;lltemplate lbool isEmpty(SqStack& s)lreturn s.top=0;lltemplate lbool isFull(SqStack& s)lreturn s.top=MAXSIZE;lltemplate lElemType peek(SqStack& s)lif(s.top=0)lcerrStack is em

43、pty!endl;lexit(1);llreturn s.bases.top-1;lltemplate lvoid push(SqStack& s,const ElemType& e)lif(s.top=MAXSIZE)lcerrStack overflow!endl;lexit(1);lls.bases.top=e;l+s.top;lltemplate lElemType pop(SqStack& s)lif(s.top=0)lcerrStack is empty!endl;lexit(1);ll-s.top;lElemType temp=s.bases.top;lreturn temp;l

44、main.cppl#include lusing namespace std;lint precede(char op);lvoid change(char* s1,char* s2);ldouble compute(char* str);lint main()lchar s1=34*(2+5)+3;lchar s230;lchange(s1,s2);lcouts2endl;ldouble r=compute(s2);lcoutr0實現(xiàn)遞歸調(diào)用，由實現(xiàn)遞歸調(diào)用，由n的值乘以的值乘以f(n-1)的返的返回值求出回值求出f(n)。10( )(1)0nf nn f nnl用用C+語言編寫出求解語言編

45、寫出求解n!的遞歸函數(shù)為：的遞歸函數(shù)為：llong f(int n)lif(n=0)lreturn 1;lelselreturn n*f(n-1);ll在計算機(jī)系統(tǒng)內(nèi)，執(zhí)行遞歸函數(shù)是通過在計算機(jī)系統(tǒng)內(nèi)，執(zhí)行遞歸函數(shù)是通過棧棧來實現(xiàn)的，來實現(xiàn)的，棧中的每個元素包含有遞歸函數(shù)的每個棧中的每個元素包含有遞歸函數(shù)的每個參數(shù)域參數(shù)域、每、每個個局部變量域局部變量域和調(diào)用后的和調(diào)用后的返回地址域返回地址域。每次進(jìn)行函。每次進(jìn)行函數(shù)調(diào)用時，都把相應(yīng)的值壓入棧。每次調(diào)用結(jié)束時，數(shù)調(diào)用時，都把相應(yīng)的值壓入棧。每次調(diào)用結(jié)束時，都按照本次返回地址返回到指定位置執(zhí)行，并且自都按照本次返回地址返回到指定位置執(zhí)行，并且自

46、動作一次退棧操作，使得上一次調(diào)用所使用的參數(shù)動作一次退棧操作，使得上一次調(diào)用所使用的參數(shù)成為新的棧頂，繼續(xù)被使用。成為新的棧頂，繼續(xù)被使用。l棧和遞歸是可以相互轉(zhuǎn)換的，當(dāng)編寫遞歸算法時，棧和遞歸是可以相互轉(zhuǎn)換的，當(dāng)編寫遞歸算法時，雖然表面上沒有使用棧，但系統(tǒng)執(zhí)行時會雖然表面上沒有使用棧，但系統(tǒng)執(zhí)行時會自動自動建立建立和使用棧。和使用棧。l求解迷宮問題也是一個遞歸問題，適合采用遞歸算求解迷宮問題也是一個遞歸問題，適合采用遞歸算法來解決。法來解決。l若迷宮中的當(dāng)前位置（初始上入口點）就是出若迷宮中的當(dāng)前位置（初始上入口點）就是出口位置，則表示找到了通向出口的一條路徑，應(yīng)返口位置，則表示找到了通向出

47、口的一條路徑，應(yīng)返回回true；l若從當(dāng)前位置按東、南、西、北方向的次序前若從當(dāng)前位置按東、南、西、北方向的次序前進(jìn)到下一個位置，該位置可通行且沒有被訪問過，進(jìn)到下一個位置，該位置可通行且沒有被訪問過，則以該位置為參數(shù)進(jìn)行遞歸調(diào)用，若返回則以該位置為參數(shù)進(jìn)行遞歸調(diào)用，若返回true的話，的話，表明從該位置到出口點有通路，標(biāo)記該位置后向上表明從該位置到出口點有通路，標(biāo)記該位置后向上一個位置返回一個位置返回true，結(jié)束遞歸。，結(jié)束遞歸。l若當(dāng)前位置上的所有方向都試探完畢，表明從若當(dāng)前位置上的所有方向都試探完畢，表明從當(dāng)前位置出發(fā)沒有尋找到通向出口點的路徑，返回當(dāng)前位置出發(fā)沒有尋找到通向出口點的路

48、徑，返回false結(jié)束遞歸。結(jié)束遞歸。l#include l#include l#include lusing namespace std;lconst int MAXLENGTH=25; / 設(shè)迷宮的最大行列為設(shè)迷宮的最大行列為25ltypedef int MazeTypeMAXLENGTHMAXLENGTH; / 迷宮數(shù)組迷宮數(shù)組行行列列l(wèi)struct PosType / 迷宮坐標(biāo)位置類型迷宮坐標(biāo)位置類型lint x; / 行值行值lint y; / 列值列值l;lstruct Elem / 元素類型元素類型lint ord; / 通道塊在路徑上的序號通道塊在路徑上的序號lPosType

49、seat; / 通道塊在迷宮中的坐標(biāo)位置通道塊在迷宮中的坐標(biāo)位置lint di; / 從此通道塊走向下一通道塊的方向從此通道塊走向下一通道塊的方向(03表示東北表示東北)l;lMazeType m; / 迷宮數(shù)組迷宮數(shù)組lint curstep=0; / 當(dāng)前足跡當(dāng)前足跡,初值為初值為1l l/ 定義墻元素值為定義墻元素值為0,可通過路徑為可通過路徑為1,不能通過路徑為不能通過路徑為-1,通過路徑為足跡通過路徑為足跡lbool pass(PosType b) l/ 當(dāng)迷宮當(dāng)迷宮m的的b點的序號為點的序號為1(可通過路徑可通過路徑)，返回，返回 true; 否則，返回否則，返回 false。li

50、f(mb.xb.y=1)lreturn true;lelselreturn false;llvoid footPrint(PosType a) / 使迷宮使迷宮m的的a點的序號變?yōu)樽阚E點的序號變?yōu)樽阚E(curstep)lma.xa.y=curstep;ll / 根據(jù)當(dāng)前位置及移動方向，返回下一位置根據(jù)當(dāng)前位置及移動方向，返回下一位置lPosType nextPos(PosType c,int di)PosType direc4=0,1,1,0,0,-1,-1,0; l / 行增量行增量,列增量列增量l/ 移動方向移動方向,依次為東南西北依次為東南西北lc.x+=direcdi.x;lc.y+=

51、direcdi.y;lreturn c;ll/ 使迷宮使迷宮m的的b點的序號變?yōu)辄c的序號變?yōu)?1(不能通過的路徑不能通過的路徑)lvoid markPrint(PosType b)lmb.xb.y=-1;llvoid print(int x,int y) / 輸出迷宮的解輸出迷宮的解lfor(int i=0;ix;i+)lfor(int j=0;jy;j+)lcoutsetw(3)mij;lcoutendl;lllbool mazePath(PosType curpos,PosType end) l/若存在從當(dāng)前位置到出口若存在從當(dāng)前位置到出口end的通道，則返回的通道，則返回TRUE；否則返

52、回；否則返回FALSElif(curpos.x=end.x&curpos.y=end.y) / 到達(dá)終點到達(dá)終點(出口出口)lreturn true;lPosType nextpos;lfor(int i=0;i4;+i)lnextpos=nextPos(curpos,i);lif(pass(nextpos)lmarkPrint(nextpos);lif(mazePath(nextpos,end)lcurstep+; / 足跡加足跡加1lfootPrint(nextpos);lreturn true;llllreturn false;llint main()lPosType begin,end

53、;lint x=8,y=10;lbegin.x=1;lbegin.y=1;lend.x=6;lend.y=8;lifstream infile;linfile.open(data.txt); /打開文件打開文件lfor(int i=0;i8;i+)lfor(int j=0;jmij;linfile.close(); /關(guān)閉文件關(guān)閉文件if(mazePath(begin,end) / 求得一條通路求得一條通路cout此迷宮從入口到出口的一條路徑如此迷宮從入口到出口的一條路徑如下下:n;print(x,y); / 輸出此通路輸出此通路elsecout此迷宮沒有從入口到出口的路徑此迷宮沒有從入口到出

54、口的路徑n;3.4 隊列隊列3.4.1 抽象數(shù)據(jù)類型隊列的定義抽象數(shù)據(jù)類型隊列的定義l僅允許在一端進(jìn)行插入，另一端進(jìn)行刪除的線性表，僅允許在一端進(jìn)行插入，另一端進(jìn)行刪除的線性表，稱為隊列稱為隊列(queue)。允許插入的一端稱為。允許插入的一端稱為隊尾隊尾(rear)，允許刪除的一端稱為允許刪除的一端稱為隊頭隊頭（front）。）。隊列是一種先進(jìn)先出（First In First Out）的特殊線性表，或稱FIFO表。若隊列中沒有任何元素，則稱為空隊列，否則稱為非空隊列。l例：購物排隊例：購物排隊 -新來的成員總是加入隊尾（不允新來的成員總是加入隊尾（不允許許加塞加塞），每次離開的成員總是隊列

55、頭上的（不），每次離開的成員總是隊列頭上的（不允許中途離隊）。允許中途離隊）。l例：解決主機(jī)與外部設(shè)備之間速度不匹配問題。例：解決主機(jī)與外部設(shè)備之間速度不匹配問題。l例：操作系統(tǒng)中資源競爭。例：操作系統(tǒng)中資源競爭。隊列的抽象數(shù)據(jù)類型定義如下：隊列的抽象數(shù)據(jù)類型定義如下：lADT Queue islData：l采用順序或鏈接方式存儲的隊列，假定其存儲類型用采用順序或鏈接方式存儲的隊列，假定其存儲類型用QueueType表示。表示。lOperation：lvoid initQueue(QueueType& q,int maxsize); /初始化隊列初始化隊列q，置為空，置為空lvoid dest

56、royQueue(QueueType& q);/銷毀隊列銷毀隊列q，不再存在，不再存在lvoid clearQueue(QueueType& q); /清空隊列清空隊列l(wèi)bool isEmpty(QueueType q); /若若q為空，返回為空，返回true，否則返回，否則返回falselint getLength(QueueType q); /返回隊列返回隊列q的長度的長度lElemType getHead(QueueType q); /返回返回q的隊頭元素的隊頭元素lvoid insertElem(QueueType& q,ElemType e); /在在q的隊尾插入元素的隊尾插入元素e

57、lElemType deleteElem(QueueType& q); /刪除隊頭元素，并將之返回刪除隊頭元素，并將之返回lvoid traverseQueue(QueueType q,void (*visit)(ElemType&);l/從隊頭到隊尾，依次對每個元素調(diào)用函數(shù)從隊頭到隊尾，依次對每個元素調(diào)用函數(shù)visit()3.4.2 鏈隊列隊列的鏈?zhǔn)奖硎竞蛯崿F(xiàn)鏈隊列隊列的鏈?zhǔn)奖硎竞蛯崿F(xiàn)l用鏈表表示的隊列稱為用鏈表表示的隊列稱為鏈隊列鏈隊列，一個鏈隊列，一個鏈隊列需要兩個分別指示需要兩個分別指示隊頭隊頭和和隊尾隊尾的的指針指針才能唯才能唯一確定。為操作方便，可給鏈隊列添加一個一確定。為操作方便

58、，可給鏈隊列添加一個頭結(jié)點并令頭結(jié)點并令頭指針指向頭結(jié)點頭指針指向頭結(jié)點。由此，。由此，空的空的鏈隊列的判決條件為頭指針和尾指針均指向鏈隊列的判決條件為頭指針和尾指針均指向頭結(jié)點。頭結(jié)點。插入元素刪除元素刪除最后一個元素鏈隊列的實現(xiàn)如下：鏈隊列的實現(xiàn)如下：linkqueue.hl#include lusing namespace std;lstruct ElemTypelint d;l;lstruct QNodelElemType data;lQNode* next;l;lstruct LinkQueuelQNode* front;lQNode* rear;l;void initQueue(L

59、inkQueue& q);void destroyQueue(LinkQueue& q);void clearQueue(LinkQueue& q);bool isEmpty(LinkQueue q);int getLength(LinkQueue q);ElemType getHead(LinkQueue q);void insertElem(LinkQueue& q,ElemType e);ElemType deleteElem(LinkQueue& q);void traverseQueue(LinkQueue q,void (*visit)(ElemType&);linkqueue.c

60、ppl#include linkqueue.hlvoid initQueue(LinkQueue& q)lq.front=q.rear=new QNode;lif(!q.front)lexit(1);lq.front-next=NULL;llvoid destroyQueue(LinkQueue& q)lwhile(q.front)lq.rear=q.front-next;ldelete q.front;lq.front=q.rear;lllvoid clearQueue(LinkQueue& q)lQNode* p=q.front-next;lwhile(p)lq.rear=p-next;l