栈Stack队列Queue优先队列PriorityQueue.ppt
《栈Stack队列Queue优先队列PriorityQueue.ppt》由会员分享,可在线阅读,更多相关《栈Stack队列Queue优先队列PriorityQueue.ppt(43页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、n n栈栈(Stack)n n队列队列(Queue)n n优先队列优先队列(Priority Queue)栈栈(Stack)n n只允许在一端插入和删除的顺序表只允许在一端插入和删除的顺序表n n允许插入和删除允许插入和删除 的一端称为的一端称为栈顶栈顶 (top),另一端称另一端称 为为栈底栈底(bottom)n n特点特点 后进先出后进先出 (LIFO)template class Stack public:Stack(int=10);/构造函数构造函数 void Push(const Type&item);/进栈进栈 Type Pop();/出栈出栈 Type GetTop();/取栈顶
2、元素取栈顶元素 void MakeEmpty();/置空栈置空栈 int IsEmpty()const;/判栈空否判栈空否 int IsFull()const;/判栈满否判栈满否栈的抽象数据类型栈的抽象数据类型#include template class Stack public:Stack(int=10);/构造函构造函数数 Stack()delete elements;/析构析构函数函数 void Push(const Type&item);/进栈进栈 Type Pop();/出栈出栈 Type GetTop();/取栈顶元取栈顶元素素 void MakeEmpty()top=-1;/置
3、空置空栈栈 int IsEmpty()const return top=-1;栈的数组表示栈的数组表示 顺序栈顺序栈 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
4、Stack:Push(const Type&item)assert(!IsFull();/先决条件先决条件断言断言 elements+top=item;/加入新元素加入新元素template Type Stack:Pop()assert(!IsEmpty();/先决条件断先决条件断言言 return elementstop-;/退出栈顶元素退出栈顶元素template Type stack:GetTop()assert(!IsEmpty();/先决条件断言先决条件断言 return elementstop;/取出栈顶元素取出栈顶元素双栈共享一个栈空间双栈共享一个栈空间多栈处理多栈处理 栈浮动技
5、术栈浮动技术n nn栈共享一个数组空间栈共享一个数组空间Vmn n设立栈顶指针数组设立栈顶指针数组 t n+1 和和 栈底指针数组栈底指针数组 b n+1n nti和和bi分别指示分别指示第第i个栈个栈的的栈顶栈顶与与栈底栈底 bn作为控制量,指到数组最高下标作为控制量,指到数组最高下标n n各栈初始分配空间各栈初始分配空间 s=m/n n 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
6、tem)if(t i=bi+1)StackFull(i);else V+ti=item;/第i 个栈进栈template Type*Pop(const i)if(ti=bi)StackEmpty(i);return 0;else return&Vti-;/第i 个栈出栈栈的链接表示栈的链接表示 链式链式栈栈n n链式栈无栈满问题,空间可链式栈无栈满问题,空间可扩充扩充n n插入与删除仅在栈顶处执行插入与删除仅在栈顶处执行n n链式栈的栈顶在链头链式栈的栈顶在链头n n适合于多栈操作适合于多栈操作template class Stack;template class StackNode frie
7、nd 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&item);Type Pop();Type GetTop();void MakeEmpty()top=NULL;int IsEmpty()const
8、return top=NULL;private:StackNode*top;/栈顶指针栈顶指针template void Stack:Stack()StackNode*p;while(top!=NULL)/逐结点回收逐结点回收 p=top;top=toplink;delete p;template void Stack:Push(const Type&item)top=new StackNode(item,top);/新结点链入新结点链入top之前之前,并成为新栈顶并成为新栈顶template Type Stack:Pop()assert(!IsEmpty();StackNode*p=top;
9、Type retvalue=pdata;/暂存栈顶数暂存栈顶数据据 top=toplink;/修改栈顶指修改栈顶指针针 delete p;return retvalue;/释放释放,返返回数据回数据template Type Stack:GetTop()assert(!IsEmpty();return topdata;队列队列 (Queue)n n定义定义uu队列是只允许在一端删除,在另一队列是只允许在一端删除,在另一端插入的顺序表端插入的顺序表uu允许删除的一端叫做队头允许删除的一端叫做队头(front),允许插入的一端叫做队尾允许插入的一端叫做队尾(rear)。n n特性特性uu先进先出先
10、进先出(FIFO,First In First Out)template class Queue public:Queue(int=10);/构造函数构造函数 void EnQueue(const Type&item);/进进队队 Type DeQueue();/出队列出队列 Type GetFront();/取队头元素取队头元素值值 void MakeEmpty();/置空队列置空队列 int IsEmpty()const;/判队列判队列空否空否 int IsFull()const;/判队列满否判队列满否队列的抽象数据类型队列的抽象数据类型#include template class Qu
11、eue public:Queue(int=10);Queue()delete elements;void EnQueue(const Type&item);Type DeQueue();Type GetFront();void MakeEmpty()front=rear=0;队列的数组表示队列的数组表示 循环队列的类定义循环队列的类定义 int IsEmpty()const return front=rear;int IsFull()const return(rear+1)%maxSize=front;int Length()const return(front-rear+maxSize)%m
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- Stack 队列 Queue 优先 PriorityQueue
限制150内