堆棧知識詳解(簡單易懂).ppt

《堆棧知識詳解(簡單易懂).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