栈Stack队列Queue优先队列PriorityQueue.ppt

栈(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(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()assert(!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 个栈出栈,栈的链接表示 链式栈,链式栈无栈满问题，空间可扩充插入与删除仅在栈顶处执行链式栈的栈顶在链头适合于多栈操作,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/栈顶指针,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 Stack: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()delete 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 指示位置加入。出队时队头指针先进一 front=front+1，再将 下标为 front 的元素取出。队满时再进队将溢出出错；队空时再出队将队 空处理。,存储队列的数组被当作首尾相接的表处理。队头、队尾指针加1时从maxSize-1直接进到0，可用语言的取模(余数)运算实现。队头指针进1:front=(front+1)%maxSize;队尾指针进1:rear=(rear+1)%maxSize;队列初始化：front=rear=0;队空条件：front=rear;队满条件：(rear+1)%maxSize=front,循环队列(Circular Queue),循环队列的进队和出队,循环队列部分成员函数的实现template Queue:Queue(int sz):front(0),rear(0),maxSize(sz)elements=new TypemaxSize;assert(elements!=0);template void Queue:EnQueue(const Type,template Type Queue:DeQueue()assert(!IsEmpty();front=(front+1)%MaxSize;return elementsfront;template Type Queue:GetFront()assert(!IsEmpty();return elementsfront;,队列的链接表示 链式队列,队头在链头，队尾在链尾。链式队列在进队时无队满问题，但有队空问题。队空条件为 front=NULL,链式队列类的定义template class Queue;template class QueueNode friend class Queue;private:Type data;/队列结点数据 QueueNode*link;/结点链指针 QueueNode(Type d=0,QueueNode*l=NULL):data(d),link(l);,template class Queue public:Queue():rear(NULL),front(NULL)Queue();void EnQueue(const Type,链式队列成员函数的实现template void Queue:Queue()/队列的析构函数 QueueNode*p;while(front!=NULL)/逐个结点释放 p=front;front=frontlink;delete p;,template void Queue:EnQueue(const Type,template TypeQueue:DeQueue()/删去队头结点，并返回队头元素的值 assert(!IsEmpty();/判队空的断言 QueueNode*p=front;Type retvalue=pdata;/保存队头的值 front=frontlink;delete p;/新队头 return retvalue;,template Type Queue:GetFront()/若队不空，则函数返回队头元素的值;若/队空，则函数返回0。assert(!IsEmpty();return frontdata;,队列的应用举例 逐行打印二项展开式(a+b)i 的系数,杨辉三角形(Pascals triangle),分析第 i 行元素与第 i+1行元素的关系,目的是从前一行的数据可以计算下一行的数据,从第 i 行数据计算并存放第 i+1 行数据,利用队列打印二项展开式系数的程序#include#include#include queue.hvoid YANGVI(int n)Queue q;/队列初始化 q.MakeEmpty();q.EnQueue(1);q.EnQueue(1);int s=0;,for(int i=1;i=n;i+)/逐行计算 cout endl;q.EnQueue(0);for(int j=1;j=i+2;j+)/下一行 int t=q.DeQueue();q.EnQueue(s+t);s=t;if(j!=i+2)cout s;,优先级队列(Priority Queue),优先级队列 是不同于先进先出队列的另一种队列。每次从队列中取出的是具有最高优先权的元素例如下表：任务的优先权及执行顺序的关系,数字越小，优先权越高,优先队列的类定义#include#include$include const int maxPQSize=50;/缺省元素个数template class PQueue public:PQueue();PQueue()delete pqelements;void PQInsert(const Type,void makeEmpty()count=-1;int IsEmpty()const return count=-1;int IsFull()const return count=maxPQSize;int Length()const return count;private:Type*pqelements;/存放数组 int count;/队列元素计数,优先队列部分成员函数的实现template PQueue:PQueue():count(-1)pqelements=new TypemaxPQSize;assert(pqelements!=0);/分配断言template void PQueue:PQInsert(const Type,template Type PQueue:PQRemove()assert(!IsEmpty();/判队空断言 Type min=pqelements0;int minindex=0;for(int i=1;icount;i+)/寻找最小元素 if(pqelementsi min)/存于min min=pqelementsi;minindex=i;pqelementsminindex=pqelementscount-1;count-;/删除 return min;,