优先级队列和队列有什么区别？

优先级队列和队列有什么区别？

优先级队列 是不同于先进先出队列的另一种队列。每次从队列中取出的是具有最高优先权的元素

　　优先队列的类定义

　　#include <assert.h>

　　#include <iostream.h>

　　$include <stdlib.h>

　　const int maxPQSize = 50; //缺省元素个数

　　template <class Type> class PQueue {

　　public:

　　PQueue ( );

　　~PQueue ( ) { delete [ ] pqelements; }

　　void PQInsert ( const Type & item );

　　Type PQRemove ( );

　　void makeEmpty ( ) { count = 0; }

　　int IsEmpty ( ) const

　　{ return count == 0; }

　　int IsFull ( ) const

　　{ return count == maxPQSize; }

　　int Length ( ) const { return count; }

　　private:

　　Type *pqelements; //存放数组

　　int count; //队列元素计数

　　}

　　优先队列是0个或多个元素的集合,每个元素都有一个优先权或值,对优先队列执行的操作有1) 查找;2) 插入一个新元素;3) 删除.在最小优先队列(min priorityq u e u e)中,查找操作用来搜索优先权最小的元素,删除操作用来删除该元素;对于最大优先队列(max priority queue),查找操作用来搜索优先权最大的元素,删除操作用来删除该元素.优先权队列中的元素可以有相同的优先权,查找与删除操作可根据任意优先权进行.

　　最大优先权队列的抽象数据类型描述如ADT 9-1所示,最小优先队列的抽象数据类型描述与之类似,只需将最大改为最小即可.

　　ADT 最大优先队列的抽象数据类型描述抽象数据类型

　　M a x P r i o r i t y Q u e u e{

　　实例 有限的元素集合,每个元素都有一个优先权

　　操作

　　Create ( ):创建一个空的优先队列

　　Size ( ):返回队列中的元素数目

　　Max ( ):返回具有最大优先权的元素

　　I n s e rt (x):将x插入队列

　　DeleteMax (x):从队列中删除具有最大优先权的元素,并将该元素返回至x

　　}

　　优先队列插入和删除元素的复杂度都是O(lgn)，所以很快。

　　另一种描述方法是采用有序线性表,当元素按递增次序排列,使用链表时则按递减次序排列,这两种描述方法的删除时间均为( 1 ),插入操作所需时间为(n).

　　例：

　　假设我们对机器服务进行收费.每个用户每次使用机器所付费用都是相同的,但每个

　　用户所需要服务时间都不同.为获得最大利润,假设只要有用户机器就不会空闲,我们可以把

　　等待使用该机器的用户组织成一个最小优先队列,优先权即为用户所需服务时间.当一个新的

　　用户需要使用机器时,将他/她的请求加入优先队列.一旦机器可用,则为需要最少服务时间

　　(即具有最高优先权)的用户提供服务.

　　如果每个用户所需时间相同,但用户愿意支付的费用不同,则可以用支付费用作为优先权,

　　一旦机器可用,所交费用最多的用户可最先得到服务,这时就要选择最大优先队列.

卡拉曼达，为什么要一离开队列