棧（Stack）隊列（Queue）優(yōu)先隊列（PriorityQueue）小結(jié)

《棧（Stack）隊列（Queue）優(yōu)先隊列（PriorityQueue）小結(jié)》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、棧(Stack)隊列(Queue)優(yōu)先隊列(PriorityQueue)小結(jié)第四章棧和隊列棧(Stack)只允許在一端插入和刪除的順序表允許插入和刪除的一端稱為棧頂(top)，另一端稱為棧底(bottom)特點后進(jìn)先出(LIFO)templateclassStack{public:Stack(int=10);//構(gòu)造函數(shù)voidPush(constType&item);//進(jìn)棧TypePop();//出棧TypeGetTop();//取棧頂元素voidMakeEmpty();//置空棧intIsEmpty()const;//判?？辗駃ntIsF

2、ull()const;//判棧滿否}棧的抽象數(shù)據(jù)類型#includetemplateclassStack{public:Stack(int=10);//構(gòu)造函數(shù)~Stack(){delete[]elements;}//析構(gòu)函數(shù)voidPush(constType&item);//進(jìn)棧TypePop();//出棧TypeGetTop();//取棧頂voidMakeEmpty(){top=-1;}//置空棧intIsEmpty()const{returntop==-1;}棧的數(shù)組表示—順序棧intIsFull()const{re

3、turntop==maxSize-1;}private:inttop;//棧頂數(shù)組指針Type*elements;//棧數(shù)組intmaxSize;//棧最大容量}templateStack::Stack(ints):top(-1),maxSize(s){elements=newType[maxSize];assert(elements!=0);//斷言}進(jìn)棧示例退棧示例templatevoidStack::Push(constType&item){assert(!IsFull());//先決條件斷言

4、elements[++top]=item;//加入新元素}templateTypeStack::Pop(){assert(!IsEmpty());//先決條件斷言returnelements[top--];//退出棧頂元素}templateTypestack::GetTop(){assert(!IsEmpty());//先決條件斷言returnelements[top];//取出棧頂元素}雙棧共享一個棧空間多棧處理棧浮動技術(shù)n個棧共享一個數(shù)組空間V[m]設(shè)立棧頂指針數(shù)組t[n+1]和棧底指針數(shù)組b[

5、n+1]t[i]和b[i]分別指示第i個棧的棧頂與棧底b[n]作為控制量，指到數(shù)組最高下標(biāo)各棧初始分配空間s=?m/n?指針初始值t[0]=b[0]=-1b[n]=m-1t[i]=b[i]=b[i-1]+s,i=1,2,…,n-1插入新元素時的棧滿處理StackFull()templatevoidPush(constinti,constType&item){if(t[i]==b[i+1])StackFull(i);elseV[++t[i]]=item;//第i個棧進(jìn)棧}templateType*Pop(consti){if

6、(t[i]==b[i]){StackEmpty(i);return0;}elsereturn&V[t[i]--];//第i個棧出棧}棧的鏈接表示—鏈?zhǔn)綏ｆ準(zhǔn)綏o棧滿問題，空間可擴(kuò)充插入與刪除僅在棧頂處執(zhí)行鏈?zhǔn)綏５臈ｍ斣阪滎^適合于多棧操作templateclassStack;templateclassStackNode{friendclassStack;private:Typedata;//結(jié)點數(shù)據(jù)StackNode*link;//結(jié)點鏈指針StackNode(Typed=0,StackNode

7、pe>*l=NULL):data(d),link(l){}};鏈?zhǔn)綏?LinkedStack)類的定義templateclassStack{public:Stack():top(NULL){}~Stack();voidPush(constType&item);TypePop();TypeGetTop();voidMakeEmpty();//實現(xiàn)與~Stack()同intIsEmpty()const{returntop==NULL;}private:StackNode*top;//棧頂指針}templateS