邊第3講 棧和隊列

《邊第3講 棧和隊列》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、約瑟夫問題這是17世紀(jì)的法國數(shù)學(xué)家加斯帕在《數(shù)目的游戲問題》中講的一個故事：15個教徒和15個非教徒在深海上遇險，必須將一半的人投入海中，其余的人才能幸免于難，于是想了一個辦法：30個人圍成一圓圈，從第一個人開始依次報數(shù)，每數(shù)到第九個人就將他扔入大海，如此循環(huán)進(jìn)行直到僅余15個人為止。問怎樣排法，才能使每次投入大海的都是非教徒。第3章棧和隊列迷宮問題迷宮問題取自于心理學(xué)古典實(shí)驗(yàn)。心理學(xué)家把一只老鼠從一個無頂蓋的大盒子的入口趕進(jìn)迷宮，迷宮中設(shè)置很多隔壁，對前進(jìn)方向形成了多處障礙，心理學(xué)家在迷宮的唯一出口放置了一塊奶酪，吸引老鼠在迷宮中尋

2、找通路以到達(dá)出口老鼠能夠記住已經(jīng)走過的路，不會反復(fù)走重復(fù)的路徑.棧和隊列是限定插入和刪除只能在表的“端點(diǎn)”進(jìn)行的線性表。棧和隊列是兩種常用的數(shù)據(jù)類型棧只允許在一端插入和刪除的線性表允許插入和刪除的一端稱為棧頂(top)，另一端稱為棧底(bottom)特點(diǎn)后進(jìn)先出(LIFO)棧(Stack)退棧進(jìn)棧a1anan-1?topbottom1．intLength()const初始條件：棧已存在。操作結(jié)果：返回棧元素個數(shù)。2．boolEmpty()const初始條件：棧已存在。操作結(jié)果：如棧為空，則返回true，否則返回false3．voi

3、dClear()初始條件：棧已存在。操作結(jié)果：清空棧。4．voidPrt()const初始條件：棧已存在。操作結(jié)果：從棧底到棧頂依次輸出棧的每個元素5．voidPush(constElemTypex)初始條件：棧已存在。操作結(jié)果：插入元素e為新的棧頂元素。a1a2ane……6．ElemTypeTop()初始條件：棧已存在且非空。操作結(jié)果：返回棧頂元素。a1a2an……7．voidPop()初始條件：棧已存在且非空。操作結(jié)果：刪除棧頂元素。a1a2anan-1……棧的應(yīng)用函數(shù)調(diào)用表達(dá)式計算棧的數(shù)組表示—順序棧top空棧topt

4、optoptoptopa進(jìn)棧b進(jìn)棧aababcdee進(jìn)棧abcdef進(jìn)棧溢出abdee退棧ctopc退棧b退棧abaa退?？諚opabdd退棧ctopabctoptop//文件名SqStack.h#includeusingnamespacestd;template//模板聲明，數(shù)據(jù)元素虛擬類型為TclassSqStack//順序棧類{private://數(shù)據(jù)成員intmaxSize;//存儲空間容量inttop;//棧頂指針T*s;//順序棧存儲空間首地址public://成員函數(shù)SqStack(

5、int);//構(gòu)造函數(shù)，建立空棧,即棧初始化voidPrt();//順序輸出棧中的元素與棧頂指針intflag();//檢測順序棧的狀態(tài)voidPush(T);//入棧TPop();//退棧TTop();//讀棧頂元素};//建立容量為mm的空棧templateSqStack::SqStack(intm){maxSize=m;//存儲空間容量s=newT[maxSize];//動態(tài)申請存儲空間top=0;//棧頂指針為0，即建立空棧return;}//順序輸出棧中的元素與棧頂指針templatev

6、oidSqStack::Prt(){inti;cout<<"top="<0;i--)cout<intSqStack::flag(){if(top==maxSize)return(-1);//存儲空間已滿，返回-1if(top==0)return(0);//棧為空，返回0return(1);//正常返回1}//入棧templatevoidSqStack::Push

7、(Tx){if(top==maxSize)//存儲空間已滿，上溢錯誤{cout<<"Stackoverflow!"<TSqStack::Pop(){Ty;if(top==0)//棧為空，下溢錯誤{cout<<"Stackunderflow!"<

8、//返回退出棧的元素}//讀棧頂元素templateTSqStack::Top(){if(top==0)//棧為空{(diào)cout<<"Stackempty!"<