資源描述:
《堆棧知識詳解(簡單易懂).ppt》由會員上傳分享,免費在線閱讀,更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。
1、第5章堆棧----后進先出:一種操作受限的線性表主要內(nèi)容堆棧的定義堆棧的描述公式化描述鏈表描述堆棧的應(yīng)用括號匹配、漢諾塔、火車車廂重排迷宮、開關(guān)盒布線、離線等價類2堆棧定義DCBA棧頂EpushABCDE棧頂ABCDE棧頂ExtopABCDE棧頂popExtopABCD棧頂棧底堆棧(stack)是一個線性表,其插入和刪除操作都在表的同一端進行,這端被稱為棧頂(top),另一端被稱為棧底(bottom)LIFOLastin,Firstout5抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型Stack{實例元素線性表,棧底,棧頂操作Create():創(chuàng)建一個空的堆棧IsEmpty():如果堆棧為空,則返回tru
2、e,否則返回falseIsFull():如果堆棧滿,則返回true,否則返回falseTop():返回棧頂元素Push(x):向堆棧中添加元素xPop(x):刪除棧頂元素,并將它傳遞給x}主要內(nèi)容堆棧的定義堆棧的描述公式化描述鏈表描述堆棧的應(yīng)用括號匹配、漢諾塔、火車車廂重排迷宮、開關(guān)盒布線、離線等價類7公式化描述:繼承線性表templateclassStack:privateLinearList{//LIFOobjectspublic:Stack(intMaxStackSize=10):LinearList(MaxStackSize){}boolIsEmpty
3、()const{returnLinearList::IsEmpty();}boolIsFull()const{return(Length()==GetMaxSize());}線性表尾部作為棧頂公式化描述(續(xù))TTop()const{if(IsEmpty())throwOutOfBounds();Tx;Find(Length(),x);returnx;}Stack&Push(constT&x){Insert(Length(),x);return*this;}Stack&Pop(T&x){Delete(Length(),x);return*this;}};取棧頂——提取最后
4、一個元素壓棧——添加到表尾出?!崛∽詈笠粋€元素實現(xiàn)方法分析IsFull需要獲取數(shù)組大小方法一將類LinearList的成員MaxSize變?yōu)閜rotected類型方法二:LinearList類增加函數(shù)protected:intGetMaxSize()const{returnMaxSize;}LinearList類的變化不會影響Stack類,更好!實現(xiàn)方法分析繼承方式為什么是private?private繼承會把基類的所有成員變?yōu)榕缮惖乃接谐蓡T棧雖可看作線性表的特例,但畢竟不是用戶使用Stack類,我們希望他們使用Push、Pop…,而不是Insert、Delete而privat
5、e繼承恰好可使Insert、Delete成為Stack的私有成員,用戶無法看到Stack的效率構(gòu)造函數(shù)、析構(gòu)函數(shù)與LinearList相同T:基本類型,Θ(1)T:用戶自定義類,Θ(MaxStackSize)其他函數(shù):Θ(1)H1.自定義的Stack類templateclassStack{public:Stack(intMaxStackSize=10);~Stack(){delete[]stack;}boolIsEmpty()const{returntop==-1;}boolIsFull()const{returntop==MaxTop;}TTop()const;Stac
6、k&Push(constT&x);Stack&Pop(T&x);private:inttop;//currenttopofstackintMaxTop;//maxvaluefortopT*stack;//elementarray};構(gòu)造函數(shù)templateStack::Stack(intMaxStackSize){//Stackconstructor.MaxTop=MaxStackSize-1;stack=newT[MaxStackSize];top=-1;}空棧Top函數(shù)templateTStack::Top()const{//R
7、eturntopelement.if(IsEmpty())throwOutOfBounds();returnstack[top];}Push函數(shù)templateStack&Stack::Push(constT&x){//Pushxtostack.if(IsFull())throwNoMem();//Pushfailsstack[++top]=x;return*this;}Pop函數(shù)template