栈（Stack）队列（Queue）优先队列（PriorityQueue）小结

《栈（Stack）队列（Queue）优先队列（PriorityQueue）小结》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、栈(Stack)队列(Queue)优先队列(PriorityQueue)小结第四章栈和队列栈(Stack)只允许在一端插入和删除的顺序表允许插入和删除的一端称为栈顶(top)，另一端称为栈底(bottom)特点后进先出(LIFO)templateclassStack{public:Stack(int=10);//构造函数voidPush(constType&item);//进栈TypePop();//出栈TypeGetTop();//取栈顶元素voidMakeEmpty();//置空栈intIsEmpty()const;//判栈空否intIsF

2、ull()const;//判栈满否}栈的抽象数据类型#includetemplateclassStack{public:Stack(int=10);//构造函数~Stack(){delete[]elements;}//析构函数voidPush(constType&item);//进栈TypePop();//出栈TypeGetTop();//取栈顶voidMakeEmpty(){top=-1;}//置空栈intIsEmpty()const{returntop==-1;}栈的数组表示—顺序栈intIsFull()const{re

3、turntop==maxSize-1;}private:inttop;//栈顶数组指针Type*elements;//栈数组intmaxSize;//栈最大容量}templateStack::Stack(ints):top(-1),maxSize(s){elements=newType[maxSize];assert(elements!=0);//断言}进栈示例退栈示例templatevoidStack::Push(constType&item){assert(!IsFull());//先决条件断言

4、elements[++top]=item;//加入新元素}templateTypeStack::Pop(){assert(!IsEmpty());//先决条件断言returnelements[top--];//退出栈顶元素}templateTypestack::GetTop(){assert(!IsEmpty());//先决条件断言returnelements[top];//取出栈顶元素}双栈共享一个栈空间多栈处理栈浮动技术n个栈共享一个数组空间V[m]设立栈顶指针数组t[n+1]和栈底指针数组b[

5、n+1]t[i]和b[i]分别指示第i个栈的栈顶与栈底b[n]作为控制量，指到数组最高下标各栈初始分配空间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个栈进栈}templateType*Pop(consti){if

6、(t[i]==b[i]){StackEmpty(i);return0;}elsereturn&V[t[i]--];//第i个栈出栈}栈的链接表示—链式栈链式栈无栈满问题，空间可扩充插入与删除仅在栈顶处执行链式栈的栈顶在链头适合于多栈操作templateclassStack;templateclassStackNode{friendclassStack;private:Typedata;//结点数据StackNode*link;//结点链指针StackNode(Typed=0,StackNode

7、pe>*l=NULL):data(d),link(l){}};链式栈(LinkedStack)类的定义templateclassStack{public:Stack():top(NULL){}~Stack();voidPush(constType&item);TypePop();TypeGetTop();voidMakeEmpty();//实现与~Stack()同intIsEmpty()const{returntop==NULL;}private:StackNode*top;//栈顶指针}templateS