栈Stack队列Queue优先队列PriorityQueue.ppt
《栈Stack队列Queue优先队列PriorityQueue.ppt》由会员分享,可在线阅读,更多相关《栈Stack队列Queue优先队列PriorityQueue.ppt(43页珍藏版)》请在三一办公上搜索。
1、栈(Stack)队列(Queue)优先队列(Priority Queue),第四章 栈与队列,栈(Stack),只允许在一端插入和删除的顺序表允许插入和删除 的一端称为栈顶(top),另一端称 为栈底(bottom)特点 后进先出(LIFO),template class Stack public:Stack(int=10);/构造函数 void Push(const Type/判栈满否,栈的抽象数据类型,#include template class Stack public:Stack(int=10);/构造函数 Stack()delete elements;/析构函数 void Push
2、(const Type,栈的数组表示 顺序栈,int IsFull()const return top=maxSize-1;private:int top;/栈顶数组指针 Type*elements;/栈数组 int maxSize;/栈最大容量template Stack:Stack(int s):top(-1),maxSize(s)elements=new TypemaxSize;assert(elements!=0);/断言,进栈示例,退栈示例,template void Stack:Push(const Type/退出栈顶元素,template Type stack:GetTop()a
3、ssert(!IsEmpty();/先决条件断言 return elementstop;/取出栈顶元素双栈共享一个栈空间,多栈处理 栈浮动技术,n栈共享一个数组空间Vm设立栈顶指针数组 t n+1 和 栈底指针数组 b n+1ti和bi分别指示第i个栈的栈顶与栈底 bn作为控制量,指到数组最高下标各栈初始分配空间 s=m/n指针初始值 t0=b0=-1 bn=m-1 ti=bi=bi-1+s,i=1,2,n-1,插入新元素时的栈满处理 StackFull(),template void Push(const int i,const Type/第i 个栈出栈,栈的链接表示 链式栈,链式栈无栈满问
4、题,空间可扩充插入与删除仅在栈顶处执行链式栈的栈顶在链头适合于多栈操作,template class Stack;template class StackNode friend class Stack;private:Type data;/结点数据 StackNode*link;/结点链指针 StackNode(Type d=0,StackNode*l=NULL):data(d),link(l);,链式栈(LinkedStack)类的定义,template class Stack public:Stack():top(NULL)Stack();void Push(const Type/栈顶指针
5、,template void Stack:Stack()StackNode*p;while(top!=NULL)/逐结点回收 p=top;top=toplink;delete p;template void Stack:Push(const Type/新结点链入top之前,并成为新栈顶,template Type Stack:Pop()assert(!IsEmpty();StackNode*p=top;Type retvalue=pdata;/暂存栈顶数据 top=toplink;/修改栈顶指针 delete p;return retvalue;/释放,返回数据template Type St
6、ack:GetTop()assert(!IsEmpty();return topdata;,队列(Queue),定义队列是只允许在一端删除,在另一端插入的顺序表允许删除的一端叫做队头(front),允许插入的一端叫做队尾(rear)。特性先进先出(FIFO,First In First Out),template class Queue public:Queue(int=10);/构造函数 void EnQueue(const Type/判队列满否,队列的抽象数据类型,#include template class Queue public:Queue(int=10);Queue()delet
7、e elements;void EnQueue(const Type,队列的数组表示 循环队列的类定义,int IsEmpty()const return front=rear;int IsFull()const return(rear+1)%maxSize=front;int Length()const return(front-rear+maxSize)%maxSize;private:int rear,front;Type*elements;int maxSize;,队列的进队和出队,进队时队尾指针先进一 rear=rear+1,再将新 元素按 rear 指示位置加入。出队时队头指针先进
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- Stack 队列 Queue 优先 PriorityQueue
链接地址:https://www.31ppt.com/p-5811670.html